arXiv preprint ·
Orienting mixed graphs for reachability pairs: When the all pairs setting is easier than the general one
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Given a mixed graph $G$ and an ordered pair $(u,v)$ of vertices in $V(G)$, we say that an orientation $\vec{G}$ of $G$ satisfies $(u,v)$ if $v$ is reachable from $u$ in $\vec{G}$. We consider problems in which we seek orientations that satisfy a maximum number of pairs. We distinguish between two different problems. In the most general problem called Fixed Pairs Maximum Mixed Reachability Orientation (FPRO), a multiset $P$ of ordered pairs of vertices in $V(G)$ comes with the input. In the more restricted problem All Pairs Maximum Mixed Reachability Orientation (APRO), $P$ contains exactly one copy of every ordered pair of distinct vertices in $V(G)$. We compare the computational complexity of FPRO and APRO in two ways: First, we show that both FPRO and APRO behave similarly when it comes to approximation. Namely, they both admit an asymptotic approximation, but are unlikely to admit a constant factor approximation. Then, we consider the parameterization with respect to the treewidth of the underlying graph of the input mixed graph. We show that here the complexities of FPRO and APRO differ significantly. While it is well-known that FPRO is NP-hard even when this parameter is 1, we show that APRO is XP with respect to this parameter. On the other hand, we give a $W[1]$-hardness result for APRO.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Internalizing Chain-of-thought into Looped Transformers
A 55-Addition Rank-23 Scheme for $3\times3$ Matrix Multiplication via Exact Two-Sided Minimization
Bidirectionality is Necessary in Cellular Machines for Exact-Arrival Multi-Agent Path Finding
Fixed Sets and the Hardness of Computing Correlated Equilibria
Subjective Valuations Make It Hard to be Fair: The Complexity of Resource Allocation to Groups of Agents
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.