Finding \(k\) partially disjoint paths in a directed planar graph. (English) Zbl 1443.05048
Bárány, Imre (ed.) et al., Building bridges II. Mathematics of László Lovász. Conference in celebration of László Lovász’ 70th birthday, Budapest, Hungary, July 2–6, 2018. Berlin: Springer. Bolyai Soc. Math. Stud. 28, 417-444 (2019).
Summary: The partially disjoint paths problem is: given a directed graph, vertices \(r_1,s_1,\dots,r_k,s_k\), and a set \(F\) of pairs \(\{i,j\}\) from \(\{1,\dots,k\}\), find for each \(i=1,\dots ,k\) a directed \(r_i-s_i\) path \(P_i\) such that if \(\{i,j\}\in F\) then \(P_i\) and \(P_j\) are disjoint. We show that for fixed \(k\), this problem is solvable in polynomial time if the directed graph is planar. More generally, the problem is solvable in polynomial time for directed graphs embedded on a fixed compact surface. Moreover, one may specify for each edge a subset of \(\{1,\dots ,k\}\) prescribing which of the \(r_i-s_i\) paths are allowed to traverse this edge.
For the entire collection see [Zbl 1443.05002].
For the entire collection see [Zbl 1443.05002].
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C20 | Directed graphs (digraphs), tournaments |
| 68W32 | Algorithms on strings |
| 90C27 | Combinatorial optimization |
Keywords:
disjoint paths; partially disjoint paths; directed graph; planar graph; free partially commutative group; graph groupReferences:
| [1] | A.V. Anisimov, D.E. Knuth, Inhomogeneous sorting, International Journal of Computer and Information Sciences 8 (1979) 255-260. · Zbl 0423.68027 · doi:10.1007/BF00993053 |
| [2] | A. Baudisch, Kommutationsgleichungen in semifreien Gruppen, Acta Mathematica Academiae Scientiarum Hungaricae 29 (1977) 235-249. · Zbl 0381.20027 · doi:10.1007/BF01895842 |
| [3] | M. Cygan, D. Marx, M. Pilipczuk, M. Pilipczuk, The planar directed \(k\)-vertex-disjoint paths problem is fixed-parameter tractable, in: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, IEEE, 2013, pp. 197-206. |
| [4] | V. Diekert, On the Knuth-Bendix completion for concurrent processes, Theoretical Computer Science 66 (1989) 117-136. · Zbl 0686.68023 · doi:10.1016/0304-3975(89)90131-X |
| [5] | V. Diekert, Combinatorics on Traces, Lecture Notes in Computer Science 454, Springer, Berlin, 1990. · Zbl 0717.68002 |
| [6] | C. Droms, Isomorphisms of graph groups, Proceedings of the American Mathematical Society 100 (1987) 407-408. · Zbl 0619.20015 · doi:10.1090/S0002-9939-1987-0891135-1 |
| [7] | E.S. Esyp, I.V. Kazachkov, V.N. Remeslennikov, Divisibility theory and complexity of algorithms for free partially commutative groups, in: Groups, Languages, Algorithms, Contemporary Mathematics 378, American Mathematical Society, Providence, R.I., 2005, pp. 319-348. · Zbl 1160.20306 |
| [8] | S. Fortune, J. Hopcroft, J. Wyllie, The directed subgraph homeomorphism problem, Theoretical Computer Science 10 (1980) 111-121. · Zbl 0419.05028 · doi:10.1016/0304-3975(80)90009-2 |
| [9] | K. Kawarabayashi, Y. Kobayashi, B. Reed, The disjoint paths problem in quadratic time, Journal of Combinatorial Theory, Series B 102 (2012) 424-435. · Zbl 1298.05296 · doi:10.1016/j.jctb.2011.07.004 |
| [10] | J.F. Lynch, The equivalence of theorem proving and the interconnection problem, (ACM) SIGDA Newsletter 5:3 (1975) 31-36. |
| [11] | R.C. Lyndon, P.E. Schupp, Combinatorial Group Theory, Springer, Berlin, 1977. · Zbl 0368.20023 |
| [12] | W. Magnus, A. Karrass, D. Solitar, Combinatorial Group Theory, Wiley-Interscience, New York, 1966. · Zbl 0138.25604 |
| [13] | B.A. Reed, N. Robertson, A. Schrijver, P.D. Seymour, Finding disjoint trees in planar graphs in linear time, in: Graph Structure Theory (N. Robertson, P. Seymour, eds.), Contemporary Mathematics 147, American Mathematical Society, Providence, R.I., 1993, pp. 295-301. · Zbl 0791.05092 |
| [14] | N. Robertson, P.D. Seymour, Graph minors. XIII. The disjoint paths problem, Journal of Combinatorial Theory, Series B 63 (1995) 65-110. · Zbl 0823.05038 |
| [15] | A. Schrijver, Finding \(k\) disjoint paths in a directed planar graph, SIAM Journal on Computing 23 (1994) 780-788. · Zbl 0810.05061 · doi:10.1137/S0097539792224061 |
| [16] | A. Schrijver, Combinatorial Optimization - Polyhedra and Efficiency, Springer, Berlin, 2003. · Zbl 1041.90001 |
| [17] | H. Servatius, Automorphisms of graph groups, Journal of Algebra 126 (1989) 34-60. · Zbl 0682.20022 · doi:10.1016/0021-8693(89)90319-0 |
| [18] | C. · Zbl 0655.20027 · doi:10.1016/S0747-7171(88)80024-5 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
