Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2022.5
URN: urn:nbn:de:0030-drops-173979
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17397/
Babu, Jasine ; Krithika, R. ; Rajendraprasad, Deepak
Packing Arc-Disjoint 4-Cycles in Oriented Graphs
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{babu_et_al:LIPIcs.FSTTCS.2022.5,
author = {Babu, Jasine and Krithika, R. and Rajendraprasad, Deepak},
title = {{Packing Arc-Disjoint 4-Cycles in Oriented Graphs}},
booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
pages = {5:1--5:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-261-7},
ISSN = {1868-8969},
year = {2022},
volume = {250},
editor = {Dawar, Anuj and Guruswami, Venkatesan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17397},
URN = {urn:nbn:de:0030-drops-173979},
doi = {10.4230/LIPIcs.FSTTCS.2022.5},
annote = {Keywords: arc-disjoint cycles, bipartite digraphs, oriented graphs, parameterized complexity}
}
| Keywords: | arc-disjoint cycles, bipartite digraphs, oriented graphs, parameterized complexity | |
| Seminar: | 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 14.12.2022 |
