article

Kernel bounds for disjoint cycles and disjoint paths

Authors:

Hans L. Bodlaender,

Stéphan Thomassé,

Anders YeoAuthors Info & Claims

Theoretical Computer Science, Volume 412, Issue 35

Pages 4570 - 4578

https://doi.org/10.1016/j.tcs.2011.04.039

Published: 01 August 2011 Publication History

Abstract

In this paper, we show that the problems Disjoint Cycles and Disjoint Paths do not have polynomial kernels, unless NP@?coNP/poly. Thus, these problems do not allow polynomial time preprocessing that results in instances whose size is bounded by a polynomial in the parameter at hand. We build upon recent results by Bodlaender et al. [6] and Fortnow and Santhanam [20], that show that NP-complete problems that are 'or-compositional' do not have polynomial kernels, unless NP@?coNP/poly. To this machinery, we add a notion of transformation, and obtain that Disjoint Cycles, and Disjoint Paths do not have polynomial kernels, unless NP@?coNP/poly. For the proof, we introduce a problem on strings, called Disjoint Factors, and first show that this problem has no polynomial kernel unless NP@?coNP/poly. We also show that the related Disjoint Cycles Packing problem has a kernel of size O(klogk).

References

[1]

Alon, N., Hoory, S. and Linial, N., The Moore bound for irregular graphs. Graphs and Combinatorics. v18. 53-57.

[2]

Amir, E., Efficient approximation for triangulation of minimum treewidth. In: Breese, J.S., Koller, D. (Eds.), Proceedings of the 17th Annual Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann. pp. 7-15.

[3]

Amir, E., Approximation algorithms for treewidth. Algorithmica. v56. 448-479.

[4]

Bodlaender, H.L., A cubic kernel for feedback vertex set. In: Thomas, W., Well, P. (Eds.), Lecture Notes in Computer Science, vol. 4393. Springer Verlag. pp. 320-331.

[5]

Bodlaender, H.L., Kernelization: New upper and lower bound techniques. In: Chen, J., Fomin, F.V. (Eds.), Lecture Notes in Computer Science, vol. 5917. Springer Verlag. pp. 17-37.

[6]

Bodlaender, H.L., Downey, R.G., Fellows, M.R. and Hermelin, D., On problems without polynomial kernels. Journal of Computer and System Sciences. v75. 423-434.

[7]

Bodlaender, H.L., Jansen, B.M.P. and Kratsch, S., Cross-composition: a new technique for kernelization lower bounds. In: Schwentick, T., Dürr, C. (Eds.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 9. Schloss Dagstuhl'Leibnitz-Zentrum fuer Informatik. pp. 165-176.

[8]

Bodlaender, H.L. and Penninkx, E., A linear kernel for planar feedback vertex set. In: Grohe, M., Niedermeier, R. (Eds.), Lecture Notes in Computer Science, vol. 5018. Springer Verlag. pp. 160-171.

[9]

Bodlaender, H.L., Penninkx, E. and Tan, R.B., A linear kernel for the k-disjoint cycle problem on planar graphs. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (Eds.), Lecture Notes in Computer Science, vol. 5369. Springer Verlag. pp. 294-305.

[10]

Bodlaender, H.L. and van Dijk, T.C., A cubic kernel for feedback vertex set and loop cutset. Theory of Computing Systems. v46. 566-597.

[11]

Bouchitté, V., Kratsch, D., Müller, H. and Todinca, I., On treewidth approximations. Discrete Applied Mathematics. v136. 183-196.

[12]

Burrage, K., Estivill-Castro, V., Fellows, M.R., Langston, M.A., Mac, S. and Rosamond, F.A., The undirected feedback vertex set problem has a poly(k) kernel. In: Bodlaender, H.L., Langston, M.A. (Eds.), Lecture Notes in Computer Science, vol. 4169. Springer Verlag. pp. 192-202.

[13]

Chen, Y., Flum, J. and Müller, M., Lower bounds for kernelizations and other preprocessing procedures. Theory of Computing Systems. v48 i4.

[14]

H. Dell, D. van Melkebeek, Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses, in: L.J. Schulman (Ed.), Proceedings of the 42nd Annual Symposium on Theory of Computing, STOC 2010, 2010, pp. 251-260.

[15]

Dom, M., Lokshtanov, D. and Saurabh, S., Incompressibility through colors and IDs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (Eds.), Lecture Notes in Computer Science, vol. 5555. Springer Verlag. pp. 378-389.

[16]

Downey, R.G. and Fellows, M.R., Fixed-parameter tractability and completeness I: basic results. SIAM Journal on Computing. v24. 873-921.

[17]

Downey, R.G. and Fellows, M.R., Fixed-parameter tractability and completeness II: on completeness for W{1}. Theoretical Computer Science. v141. 109-131.

[18]

Downey, R.G. and Fellows, M.R., Parameterized Complexity. 1999. Springer.

[19]

Fernau, H., Fomin, F.V., Lokshtanov, D., Raible, D., Saurabh, S. and Villanger, Y., Kernel(s) for problems with no kernel: on out-trees with many leaves (extended abstract). In: Albers, S., Marion, J.-Y. (Eds.), Dagstuhl Seminar Proceedings, vol. 09001. Schloss Dagstuhl, Germany. pp. 421-432.

[20]

Fortnow, L. and Santhanam, R., Infeasibility of instance compression and succinct PCPs for NP. Journal of Computer and System Sciences. v77. 91-106.

[21]

Garey, M.R. and Johnson, D.S., Computers and Intractability, A Guide to the Theory of NP-Completeness. 1979. W.H. Freeman and Company, New York.

[22]

Guo, J. and Niedermeier, R., Invitation to data reduction and problem kernelization. ACM SIGACT News. v38. 31-45.

[23]

Karp, R.M., On the complexity of combinatorial problems. Networks. v5. 45-68.

[24]

Kloks, T., Lee, C.M. and Liu, J., New algorithms for k-face cover, k-feedback vertex set, and k-disjoint cycles on plane and planar graphs. In: Kuc¿era, L. (Ed.), Lecture Notes in Computer Science, vol. 2573. Springer Verlag. pp. 282-295.

[25]

Kratsch, S. and Wahlström, M., Two edge modification problems without polynomial kernels. In: Chen, J., Fomin, F.V. (Eds.), Lecture Notes in Computer Science, vol. 5917. Springer Verlag. pp. 264-275.

[26]

Mathieson, L., Prieto, E. and Shaw, P., Packing edge disjoint triangles: A parameterized view. In: Downey, R.G., Fellows, M.R. (Eds.), Lecture Notes in Computer Science, vol. 3162. Springer Verlag. pp. 127-137.

[27]

Robertson, N. and Seymour, P.D., Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B. v63. 65-110.

[28]

S. Saurabh, 2009. Personal communication.

[29]

Thomassé, S., A 4k2 kernel for feedback vertex set. ACM Transactions on Algorithms. v6 i2.

Cited By

Babu JJacob AKrithika RRajendraprasad D(2024)Packing arc-disjoint cycles in oriented graphsJournal of Computer and System Sciences10.1016/j.jcss.2024.103530143:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.jcss.2024.103530
Aravind NSaxena R(2023)Perfectly matched sets in graphsTheoretical Computer Science10.1016/j.tcs.2023.113797954:COnline publication date: 18-Apr-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.113797
Lafond MLuo W(2023)Preprocessing complexity for some graph problems parameterized by structural parametersProcedia Computer Science10.1016/j.procs.2023.08.222223:C(130-139)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1016/j.procs.2023.08.222
Show More Cited By

Kernel bounds for disjoint cycles and disjoint paths
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
    2. Graph theory
2. Theory of computation

Recommendations

Kernelization Lower Bounds Through Colors and IDs

In parameterized complexity, each problem instance comes with a parameter k, and a parameterized problem is said to admit a polynomial kernel if there are polynomial time preprocessing rules that reduce the input instance to an instance with size ...
Lower bounds on kernelization

Preprocessing (data reduction or kernelization) to reduce instance size is one of the most commonly deployed heuristics in the implementation practice to tackle computationally hard problems. However, a systematic theoretical study of them has remained ...
Kernel(s) for problems with no kernel: On out-trees with many leaves

The k-Leaf Out-Branching problem is to find an out-branching, that is a rooted oriented spanning tree, with at least k leaves in a given digraph. The problem has recently received much attention from the viewpoint of parameterized algorithms. Here, we ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 412, Issue 35

August, 2011

291 pages

ISSN:0304-3975

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2011.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 August 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

73
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Babu JJacob AKrithika RRajendraprasad D(2024)Packing arc-disjoint cycles in oriented graphsJournal of Computer and System Sciences10.1016/j.jcss.2024.103530143:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.jcss.2024.103530
Aravind NSaxena R(2023)Perfectly matched sets in graphsTheoretical Computer Science10.1016/j.tcs.2023.113797954:COnline publication date: 18-Apr-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.113797
Lafond MLuo W(2023)Preprocessing complexity for some graph problems parameterized by structural parametersProcedia Computer Science10.1016/j.procs.2023.08.222223:C(130-139)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1016/j.procs.2023.08.222
Einarson CGutin GJansen BMajumdar DWahlström M(2023) p-Edge/vertex-connected vertex coverJournal of Computer and System Sciences10.1016/j.jcss.2022.11.002133:C(23-40)Online publication date: 13-Feb-2023
https://dl.acm.org/doi/10.1016/j.jcss.2022.11.002
Sahu ASaurabh S(2023)Kernelization of Arc Disjoint Cycle Packing in α-Bounded DigraphsTheory of Computing Systems10.1007/s00224-022-10114-867:2(221-233)Online publication date: 26-Jan-2023
https://dl.acm.org/doi/10.1007/s00224-022-10114-8
Bentert MKellerhals LNiedermeier R(2022)The structural complexity landscape of finding balance-fair shortest pathsTheoretical Computer Science10.1016/j.tcs.2022.08.023933:C(149-162)Online publication date: 14-Oct-2022
https://dl.acm.org/doi/10.1016/j.tcs.2022.08.023
Sheng ZXiao M(2022)An improved kernel for planar vertex-disjoint triangle packingTheoretical Computer Science10.1016/j.tcs.2022.04.017922:C(122-130)Online publication date: 24-Jun-2022
https://dl.acm.org/doi/10.1016/j.tcs.2022.04.017
Araújo JBougeret MCampos VSau I(2022)Introducing lop-Kernels: A Framework for Kernelization Lower BoundsAlgorithmica10.1007/s00453-022-00979-z84:11(3365-3406)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s00453-022-00979-z
Kobayashi YOtachi Y(2022)Parameterized Complexity of Graph BurningAlgorithmica10.1007/s00453-022-00962-884:8(2379-2393)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s00453-022-00962-8
Böckenhauer HBurjons ERaszyk MRossmanith P(2022)Reoptimization of parameterized problemsActa Informatica10.1007/s00236-022-00428-y59:4(427-450)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s00236-022-00428-y
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents