[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

On the Complexity of Finding Internally Vertex-Disjoint Long Directed Paths

  • Published:
Algorithmica Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Notes

  1. The ETH states that there is no algorithm solving 3-SAT on a formula with n variables in time \(2^{o(n)}\).

References

  1. Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844–856 (1995)

    Article  MathSciNet  Google Scholar 

  2. Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer, Berlin (2008)

    MATH  Google Scholar 

  3. Bang-Jensen, J., Havet, F., Maia, A.K.: Finding a subdivision of a digraph. Theor. Comput. Sci. 562, 283–303 (2015)

    Article  MathSciNet  Google Scholar 

  4. Benhocine, A., Wojda, A.P.: On the existence of specified cycles in a tournament. J. Graph Theory 7(4), 469–473 (1983)

    Article  MathSciNet  Google Scholar 

  5. Björklund, A., Husfeldt, T., Khanna, S.: Approximating longest directed paths and cycles. In: Proceeding of the 31st International Colloquium on Automata, Languages and Programming (ICALP). volume 3142 of LNCS. pp. 222–233 (2004)

  6. Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277–305 (2014)

    Article  MathSciNet  Google Scholar 

  7. Brewster, R.C., Hell, P., Pantel, S.H., Rizzi, R., Yeo, A.: Packing paths in digraphs. J. Graph Theory 44(2), 81–94 (2003)

    Article  MathSciNet  Google Scholar 

  8. Cai,L., Ye, J.: Finding two edge-disjoint paths with length constraints. In: Proceeding of the 42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG). volume 9941 of LNCS. pp. 62–73 (2016)

  9. Cohen, N., Havet, F., Lochet, W., Nisse, N.: Subdivisions of oriented cycles in digraphs with large chromatic number. J. Graph Theory 89(4), 439–456 (2018)

    Article  MathSciNet  Google Scholar 

  10. Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)

    Book  Google Scholar 

  11. Diestel, R.: Graph Theory, Graduate Texts in Mathematics, 4th edn. Springer, Berlin (2012)

    Google Scholar 

  12. Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)

    Book  Google Scholar 

  13. Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)

    MATH  Google Scholar 

  14. 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)

    Article  MathSciNet  Google Scholar 

  15. 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)

    MATH  Google Scholar 

  16. Grohe, M., Kawarabayashi, K., Marx, D., Wollan, P.: Finding topological subgraphs is fixed-parameter tractable. In: Proc. of the 43rd ACM Symposium on Theory of Computing (STOC) pp. 479–488 (2011)

  17. Havet, F., Maia, A.K., Mohar, B.: Finding a subdivision of a prescribed digraph of order 4. J. Graph Theory 87(4), 536–560 (2018)

    Article  MathSciNet  Google Scholar 

  18. Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512–530 (2001)

    Article  MathSciNet  Google Scholar 

  19. Itai, A., Perl, Y., Shiloach, Y.: The complexity of finding maximum disjoint paths with length constraints. Networks 12(3), 277–286 (1982)

    Article  MathSciNet  Google Scholar 

  20. Kim, R., Kim, S., Ma, J., Park, B.: Cycles with two blocks in \(k\)-chromatic digraphs. J. Graph Theory 88(4), 592–605 (2018)

    Article  MathSciNet  Google Scholar 

  21. Kneis, J., Mölle, D., Richter, S., Rossmanith, P.: Divide-and-color. In: Proc. of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG). volume 4271 of LNCS pp. 58–67 (2006)

  22. Kriesell, M.: Disjoint \(A\)-paths in digraphs. J. Comb. Theory, Ser. B 95(1), 168–2005 (2005)

    Article  MathSciNet  Google Scholar 

  23. Metzlar, A.: Disjoint paths in acyclic digraphs. J. Comb. Theory, Ser. B 57(2), 228–238 (1993)

    Article  MathSciNet  Google Scholar 

  24. Monien, B.: How to find long paths efficiently. Ann. Discrete Math. 25, 239–254 (1985)

    MathSciNet  MATH  Google Scholar 

  25. Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)

    Book  Google Scholar 

  26. Oxley, J.G.: Matroid Theory. Oxford University Press, Oxford (1992)

    MATH  Google Scholar 

  27. Schrijver, A.: A short proof of Mader’s \({\cal{S}}\)-paths theorem. J. Comb. Theory, Ser. B 82(2), 319–321 (2001)

    Article  MathSciNet  Google Scholar 

  28. Sedgewick, R., Wayne, K.: Algorithms, 4th edn. Addison-Wesley, Boston (2011)

    Google Scholar 

  29. Shachnai, H., Zehavi, M.: Representative families: a unified tradeoff-based approach. J. Comput. Syst. Sci. 82(3), 488–502 (2016)

    Article  MathSciNet  Google Scholar 

  30. Slivkins, A.: Parameterized tractability of edge-disjoint paths on directed acyclic graphs. SIAM J. Discrete Math. 24(1), 146–157 (2010)

    Article  MathSciNet  Google Scholar 

  31. Venkatesan, G., Pandu Rangan, C.: Approximate triclique coloring for register allocation. Inf. Process. Lett. 60, 249–253 (1996)

    Article  MathSciNet  Google Scholar 

  32. Zehavi, M.: A randomized algorithm for long directed cycle. Inf. Process. Lett. 116(6), 419–422 (2016)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Matemática, ParGO Research Group, Universidade Federal do Ceará, Fortaleza, Brazil

    Júlio Araújo, Ignasi Sau & Ana Silva

  2. Departamento de Computação, ParGO Research Group, Universidade Federal do Ceará, Fortaleza, Brazil

    Victor A. Campos & Ana Karolinna Maia

  3. CNRS, AlGCo Project Team, LIRMM, Université de Montpellier, Montpellier, France

    Ignasi Sau

Authors
  1. Júlio Araújo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Victor A. Campos
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ana Karolinna Maia
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ignasi Sau
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Ana Silva
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ignasi Sau.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A conference version of this article appeared in the Proc. of the 13th Latin American Theoretical INformatics Symposium (LATIN), volume 10807 of LNCS, pages 66–79, Buenos Aires, Argentina, April 2018. This article is permanently available at https://arxiv.org/abs/1706.09066.

Work supported by Projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010), CNPq Grants 304576/2017-4 and 304478/2018-0, CNPq Universal Project 401519/2016-3, FUNCAP-PRONEM PNE-0112-00061.01.00/16 and CAPES-PRINT.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Araújo, J., Campos, V.A., Maia, A.K. et al. On the Complexity of Finding Internally Vertex-Disjoint Long Directed Paths. Algorithmica 82, 1616–1639 (2020). https://doi.org/10.1007/s00453-019-00659-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-019-00659-5

Keywords

Mathematics Subject Classification

Search

Navigation