Document Open Access Logo

Packing Arc-Disjoint 4-Cycles in Oriented Graphs

Authors Jasine Babu, R. Krithika, Deepak Rajendraprasad

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2022.5.pdf
  • Filesize: 0.88 MB
  • 16 pages

Document Identifiers

Author Details

Jasine Babu
  • Indian Institute of Technology Palakkad, India
R. Krithika
  • Indian Institute of Technology Palakkad, India
Deepak Rajendraprasad
  • Indian Institute of Technology Palakkad, India

Cite AsGet BibTex

Jasine Babu, R. Krithika, and Deepak Rajendraprasad. Packing Arc-Disjoint 4-Cycles in Oriented Graphs. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FSTTCS.2022.5

Abstract

Given a directed graph G and a positive integer k, the Arc Disjoint r-Cycle Packing problem asks whether G has k arc-disjoint r-cycles. We show that, for each integer r ≥ 3, Arc Disjoint r-Cycle Packing is NP-complete on oriented graphs with girth r. When r is even, the same result holds even when the input class is further restricted to be bipartite. On the positive side, focusing on r = 4 in oriented graphs, we study the complexity of the problem with respect to two parameterizations: solution size and vertex cover size. For the former, we give a cubic kernel with quadratic number of vertices. This is smaller than the compression size guaranteed by a reduction to the well-known 4-Set Packing. For the latter, we show fixed-parameter tractability using an unapparent integer linear programming formulation of an equivalent problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Mathematics of computing → Graph algorithms
Keywords
  • arc-disjoint cycles
  • bipartite digraphs
  • oriented graphs
  • parameterized complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Faisal N. Abu-Khzam. An improved kernelization algorithm for r-set packing. Inf. Process. Lett., 110(16):621-624, 2010. URL: https://doi.org/10.1016/j.ipl.2010.04.020.
  2. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. URL: https://doi.org/10.1145/210332.210337.
  3. Jørgen Bang-Jensen and Gregory Z. Gutin. Digraphs - Theory, Algorithms and Applications, Second Edition. Springer Monographs in Mathematics. Springer, 2009. Google Scholar
  4. Claude Berge. Graphs and hypergraphs. North-Holland Pub. Co., 1973. Google Scholar
  5. Stéphane Bessy, Marin Bougeret, R. Krithika, Abhishek Sahu, Saket Saurabh, Jocelyn Thiebaut, and Meirav Zehavi. Packing arc-disjoint cycles in tournaments. Algorithmica, 83(5):1393-1420, 2021. URL: https://doi.org/10.1007/s00453-020-00788-2.
  6. Stéphane Bessy, Marin Bougeret, and Jocelyn Thiebaut. Triangle packing in (sparse) tournaments: Approximation and kernelization. In Kirk Pruhs and Christian Sohler, editors, 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, volume 87 of LIPIcs, pages 14:1-14:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.14.
  7. Hans L. Bodlaender. On disjoint cycles. Int. J. Found. Comput. Sci., 5(1):59-68, 1994. URL: https://doi.org/10.1142/S0129054194000049.
  8. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernel bounds for path and cycle problems. Theor. Comput. Sci., 511:117-136, 2013. URL: https://doi.org/10.1016/j.tcs.2012.09.006.
  9. Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci., 412(35):4570-4578, 2011. URL: https://doi.org/10.1016/j.tcs.2011.04.039.
  10. Richard A. Brualdi and Jian Shen. Disjoint cycles in eulerian digraphs and the diameter of interchange graphs. J. Comb. Theory, Ser. B, 85(2):189-196, 2002. URL: https://doi.org/10.1006/jctb.2001.2094.
  11. Leizhen Cai. Parameterized complexity of vertex colouring. Discret. Appl. Math., 127(3):415-429, 2003. URL: https://doi.org/10.1016/S0166-218X(02)00242-1.
  12. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  13. Dorit Dor and Michael Tarsi. Graph decomposition is NPC - A complete proof of Holyer’s conjecture. In S. Rao Kosaraju, Mike Fellows, Avi Wigderson, and John A. Ellis, editors, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pages 252-263. ACM, 1992. URL: https://doi.org/10.1145/129712.129737.
  14. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  15. Paul Erdős and Richard Rado. Intersection theorems for systems of sets. Journal of the London Mathematical Society, s1-35(1):85-90, 1960. URL: https://doi.org/10.1112/jlms/s1-35.1.85.
  16. Michael R. Fellows, Bart M. P. Jansen, and Frances A. Rosamond. Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. Eur. J. Comb., 34(3):541-566, 2013. URL: https://doi.org/10.1016/j.ejc.2012.04.008.
  17. Michael R. Fellows, Christian Knauer, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Ulrike Stege, Dimitrios M. Thilikos, and Sue Whitesides. Faster fixed-parameter tractable algorithms for matching and packing problems. Algorithmica, 52(2):167-176, 2008. URL: https://doi.org/10.1007/s00453-007-9146-y.
  18. Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Frances A. Rosamond, and Saket Saurabh. The complexity ecology of parameters: An illustration using bounded max leaf number. Theory Comput. Syst., 45(4):822-848, 2009. URL: https://doi.org/10.1007/s00224-009-9167-9.
  19. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. URL: https://doi.org/10.1007/3-540-29953-X.
  20. Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, and Meirav Zehavi. Subquadratic kernels for implicit 3-hitting set and 3-set packing problems. ACM Trans. Algorithms, 15(1):13:1-13:44, 2019. URL: https://doi.org/10.1145/3293466.
  21. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2019. Google Scholar
  22. András Frank and Éva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Comb., 7(1):49-65, 1987. URL: https://doi.org/10.1007/BF02579200.
  23. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  24. Bart M. P. Jansen. The Power of Data Reduction: Kernels for Fundamental Graph Problems. PhD thesis, Utrecht University, The Netherlands, 2013. Google Scholar
  25. Hendrik W. Lenstra Jr. Integer programming with a fixed number of variables. Math. Oper. Res., 8(4):538-548, 1983. URL: https://doi.org/10.1287/moor.8.4.538.
  26. Ravi Kannan. Minkowski’s convex body theorem and integer programming. Math. Oper. Res., 12(3):415-440, 1987. URL: https://doi.org/10.1287/moor.12.3.415.
  27. Thomas P. Kirkman. On a Problem in Combinations. Cambridge and Dublin Mathematical Journal, 2:191-204, 1847. Google Scholar
  28. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 224-237. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055456.
  29. Hannes Moser. Finding optimal solutions for covering and matching problems. PhD thesis, Friedrich Schiller University of Jena, 2010. URL: https://d-nb.info/999819399.
  30. Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and near-optimal derandomization. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 182-191. IEEE Computer Society, 1995. URL: https://doi.org/10.1109/SFCS.1995.492475.
  31. Aleksandrs Slivkins. Parameterized tractability of edge-disjoint paths on directed acyclic graphs. SIAM J. Discret. Math., 24(1):146-157, 2010. URL: https://doi.org/10.1137/070697781.
  32. Craig A. Tovey. A simplified NP-complete satisfiability problem. Discret. Appl. Math., 8(1):85-89, 1984. URL: https://doi.org/10.1016/0166-218X(84)90081-7.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact