Orienting mixed graphs for reachability pairs: When the all pairs setting is easier than the general one

Overview & Synopsis

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.