Abstract
For two positive integers k and \(\ell \), a \((k \times \ell )\) -spindle is the union of k pairwise internally vertex-disjoint directed paths with \(\ell \) arcs each between two vertices u and v. We are interested in the (parameterized) complexity of several problems consisting in deciding whether a given digraph contains a subdivision of a spindle, which generalize both the Maximum Flow and Longest Path problems. We obtain the following complexity dichotomy: for a fixed \(\ell \ge 1\), finding the largest k such that an input digraph G contains a subdivision of a \((k \times \ell )\)-spindle is polynomial-time solvable if \(\ell \le 3\), and NP-hard otherwise. We place special emphasis on finding spindles with exactly two paths and present FPT algorithms that are asymptotically optimal under the ETH. These algorithms are based on the technique of representative families in matroids, and use also color-coding as a subroutine. Finally, we study the case where the input graph is acyclic, and present several algorithmic and hardness results.
Work supported by DE-MO-GRAPH grant ANR-16-CE40-0028 and CNPq grant 306262/2014-2.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844–856 (1995)
Araújo, J., Campos, V.A., Maia, A.K., Sau, I., Silva, A.: On the complexity of finding internally vertex-disjoint long directed paths. CoRR, abs/1706.09066 (2017)
Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer, London (2008). https://doi.org/10.1007/978-1-84800-998-1
Bang-Jensen, J., Havet, F., Maia, A.K.: Finding a subdivision of a digraph. Theoret. Comput. Sci. 562, 283–303 (2015)
Benhocine, A., Wojda, A.P.: On the existence of specified cycles in a tournament. J. Graph Theory 7(4), 469–473 (1983)
Brewster, R.C., Hell, P., Pantel, S.H., Rizzi, R., Yeo, A.: Packing paths in digraphs. J. Graph Theory 44(2), 81–94 (2003)
Cohen, N., Havet, F., Lochet, W., Nisse, N.: Subdivisions of oriented cycles in digraphs with large chromatic number. CoRR, abs/1605.07762 (2016)
Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21275-3
Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-662-53622-3
Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 29:1–29:60 (2016)
Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York (1979)
Grohe, M., Kawarabayashi, K., Marx, D., Wollan, P.: Finding topological subgraphs is fixed-parameter tractable. In: Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pp. 479–488 (2011)
Havet, F., Maia, A.K., Mohar, B.: Finding a subdivision of a prescribed digraph of order 4. J. Graph Theory (to appear). https://doi.org/10.1002/jgt.22174
Itai, A., Perl, Y., Shiloach, Y.: The complexity of finding maximum disjoint paths with length constraints. Networks 12(3), 277–286 (1982)
Kim, R., Kim, S.-J., Ma, J., Park, B.: Cycles with two blocks in \(k\)-chromatic digraphs. CoRR, abs/1610.05839 (2016)
Kriesell, M.: Disjoint \(A\)-paths in digraphs. J. Comb. Theory Ser. B 95(1), 168–172 (2005)
Metzlar, A.: Disjoint paths in acyclic digraphs. J. Comb. Theory Ser. B 57(2), 228–238 (1993)
Monien, B.: How to find long paths efficiently. Ann. Discret. Math. 25, 239–254 (1985)
Schrijver, A.: A short proof of Mader’s \(\cal{S}\)-paths theorem. J. Comb. Theory Ser. B 82(2), 319–321 (2001)
Sedgewick, R., Wayne, K.: Algorithms, 4th edn. Addison-Wesley, Boston (2011)
Shachnai, H., Zehavi, M.: Representative families: a unified tradeoff-based approach. J. Comput. Syst. Sci. 82(3), 488–502 (2016)
Zehavi, M.: A randomized algorithm for long directed cycle. Inf. Process. Lett. 116(6), 419–422 (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Araújo, J., Campos, V.A., Maia, A.K., Sau, I., Silva, A. (2018). On the Complexity of Finding Internally Vertex-Disjoint Long Directed Paths. In: Bender, M., Farach-Colton, M., Mosteiro, M. (eds) LATIN 2018: Theoretical Informatics. LATIN 2018. Lecture Notes in Computer Science(), vol 10807. Springer, Cham. https://doi.org/10.1007/978-3-319-77404-6_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-77404-6_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-77403-9
Online ISBN: 978-3-319-77404-6
eBook Packages: Computer ScienceComputer Science (R0)