article

Kernel bounds for path and cycle problems

Authors:

Hans L. Bodlaender,

Bart M. P. Jansen,

Stefan KratschAuthors Info & Claims

Theoretical Computer Science, Volume 511

Pages 117 - 136

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

Published: 01 November 2013 Publication History

Abstract

Connectivity problems like k-Path and k-Disjoint Paths relate to many important milestones in parameterized complexity, namely the Graph Minors Project, color coding, and the recent development of techniques for obtaining kernelization lower bounds. This work explores the existence of polynomial kernels for various path and cycle problems, by considering nonstandard parameterizations. We show polynomial kernels when the parameters are a given vertex cover, a modulator to a cluster graph, or a (promised) max leaf number. We obtain lower bounds via cross-composition, e.g., for Hamiltonian Cycle and related problems when parameterized by a modulator to an outerplanar graph.

References

[1]

Adler, I., Kolliopoulos, S.G., Krause, P.K., Lokshtanov, D., Saurabh, S. and Thilikos, D.M., Tight bounds for linkages in planar graphs. In: Aceto, L., Henzinger, M., Sgall, J. (Eds.), Lecture Notes in Computer Science, vol. 6755. Springer. pp. 110-121.

[2]

Alon, N., Yuster, R. and Zwick, U., Color-coding. J. ACM. v42 i4. 844-856.

[3]

Arnborg, S., Lagergren, J. and Seese, D., Easy problems for tree-decomposable graphs. J. Algorithms. v12 i2. 308-340.

[4]

Berman, P. and Schnitger, G., On the complexity of approximating the independent set problem. Inf. Comput. v96 i1. 77-94.

[5]

Björklund, A., Determinant sums for undirected hamiltonicity. In: FOCS, IEEE Computer Society. pp. 173-182.

[6]

A. Björklund, T. Husfeldt, P. Kaski, M. Koivisto, Narrow sieves for parameterized paths and packings, CoRR, 2010, abs/1007.1161.

[7]

Bodlaender, H.L., A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. v25 i6. 1305-1317.

[8]

Bodlaender, H.L., Downey, R.G., Fellows, M.R. and Hermelin, D., On problems without polynomial kernels. J. Comput. Syst. Sci. v75 i8. 423-434.

[9]

H.L. Bodlaender, B.M.P. Jansen, S. Kratsch, Cross-composition: A new technique for kernelization lower bounds, in: Proc. 28th STACS, 2011, pp. 165-176.

[10]

Bodlaender, H.L., Thomassé, S. and Yeo, A., Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. v412 i35. 4570-4578.

[11]

Borie, R.B., Parker, R.G. and Tovey, C.A., Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica. v7 i5&6. 555-581.

[12]

J. Chen, S. Lu, S.-H. Sze, F. Zhang, Improved algorithms for path, matching, and packing problems, in: Proc. 18th SODA, 2007, pp. 298-307.

[13]

Y. Chen, J. Flum, On parameterized path and chordless path problems, in: 22nd IEEE Conference on Computational Complexity, 2007, pp. 250-263.

[14]

Chen, Y., Flum, J. and Müller, M., Lower bounds for kernelizations and other preprocessing procedures. Theory Comput. Syst. v48 i4. 803-839.

[15]

Courcelle, B., The monadic second-order logic of graphs I: recognizable sets of finite graphs. Inf. Comput. v85 i1. 12-75.

[16]

Courcelle, B. and Mosbah, M., Monadic second-order evaluations on tree-decomposable graphs. Theor. Comput. Sci. v109 i1&2. 49-82.

[17]

M. Cygan, M. Pilipczuk, M. Pilipczuk, J.O. Wojtaszczyk, Kernelization hardness of connectivity problems in 2-degenerate graphs, in: Proc. 36th WG, 2010, pp. 147-158.

[18]

H. Dell, D. Marx, Kernelization of packing problems, in: Rabani {35}, pp. 68-81.

[19]

H. Dell, D. van Melkebeek, Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses, in: Proc. 42nd STOC, 2010, pp. 251-260.

[20]

Diestel, R., Graph Theory. 2010. fourth ed. Springer-Verlag, Heidelberg.

[21]

M. Dom, D. Lokshtanov, S. Saurabh, Incompressibility through colors and IDs, in: Proc. 36th ICALP, 2009, pp. 378-389.

[22]

Downey, R. and Fellows, M.R., . In: Monographs in Computer Science, Springer, New York.

Digital Library

[23]

Fellows, M.R., Hermelin, D., Rosamond, F.A. and Vialette, S., On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. v410 i1. 53-61.

[24]

Fellows, M.R., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F.A. and Saurabh, S., The complexity ecology of parameters: An illustration using bounded max leaf number. Theory Comput. Syst. v45 i4. 822-848.

[25]

Fortnow, L. and Santhanam, R., Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. v77 i1. 91-106.

[26]

Gabow, H.N., Maheswari, S.N. and Osterweil, L.J., On two problems in the generation of program test paths. IEEE Trans. Software Eng. v2 i3. 227-231.

[27]

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.

[28]

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

[29]

Held, M. and Karp, R.M., A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. v10 i1. 196-210.

[30]

D. Hermelin, X. Wu, Weak compositions and their applications to polynomial lower bounds for kernelization, in: Rabani {35}, pp. 104-113.

[31]

Kann, V., Polynomially bounded minimization problems that are hard to approximate. Nord. J. Comput. v1 i3. 317-331.

[32]

Kleitman, D.J. and West, D.B., Spanning trees with many leaves. SIAM J. Discret. Math. v4 i1. 99-106.

[33]

J. Kneis, D. Mölle, S. Richter, P. Rossmanith, Divide-and-color, in: Proc. 32nd WG, 2006, pp. 58-67.

[34]

Kolman, P. and Pangrác, O., On the complexity of paths avoiding forbidden pairs. Discrete Appl. Math. v157 i13. 2871-2876.

[35]

. In: Rabani, Y. (Ed.), Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM.

[36]

Robertson, N. and Seymour, P.D., Graph minors. XIII. The disjoint paths problem. J. Comb. Theory, Ser. B. v63 i1. 65-110.

[37]

Scott, J., Ideker, T., Karp, R.M. and Sharan, R., Efficient algorithms for detecting signaling pathways in protein interaction networks. J. Comput. Biol. v13 i2. 133-144.

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
Golovach PKrithika RSahu ASaurabh SZehavi M(2021)Graph Hamiltonicity Parameterized by Proper Interval Deletion SetLATIN 2020: Theoretical Informatics10.1007/978-3-030-61792-9_9(104-115)Online publication date: 5-Jan-2021
https://dl.acm.org/doi/10.1007/978-3-030-61792-9_9
Dondi RMauri GZoppis I(2020)Complexity Issues of String to Graph Approximate MatchingLanguage and Automata Theory and Applications10.1007/978-3-030-40608-0_17(248-259)Online publication date: 4-Mar-2020
https://dl.acm.org/doi/10.1007/978-3-030-40608-0_17
Show More Cited By

Kernel bounds for path and cycle problems
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
    2. Graph theory
2. Theory of computation

Recommendations

Tight Kernel Bounds for Problems on Graphs with Small Degeneracy

Kernelization is a strong and widely applied technique in parameterized complexity. In a nutshell, a kernelization algorithm for a parameterized problem transforms in polynomial time a given instance of the problem into an equivalent instance whose size ...
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 ...
Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion

Given a graph G and a parameter k, the Chordal Vertex Deletion (CVD) problem asks whether there exists a subset U⊆ V(G) of size at most k that hits all induced cycles of size at least 4. The existence of a polynomial kernel for CVD was a well-known open ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 511, Issue

November, 2013

186 pages

ISSN:0304-3975

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2012.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 November 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 01 Jan 2025

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
Golovach PKrithika RSahu ASaurabh SZehavi M(2021)Graph Hamiltonicity Parameterized by Proper Interval Deletion SetLATIN 2020: Theoretical Informatics10.1007/978-3-030-61792-9_9(104-115)Online publication date: 5-Jan-2021
https://dl.acm.org/doi/10.1007/978-3-030-61792-9_9
Dondi RMauri GZoppis I(2020)Complexity Issues of String to Graph Approximate MatchingLanguage and Automata Theory and Applications10.1007/978-3-030-40608-0_17(248-259)Online publication date: 4-Mar-2020
https://dl.acm.org/doi/10.1007/978-3-030-40608-0_17
Krithika RSahu ASaurabh SZehavi M(2019)The Parameterized Complexity of Cycle Packing: Indifference is Not an IssueAlgorithmica10.1007/s00453-019-00599-081:9(3803-3841)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1007/s00453-019-00599-0
Chaplick SFomin FGolovach PKnop DZeman P(2019)Kernelization of Graph Hamiltonicity: Proper H-GraphsAlgorithms and Data Structures10.1007/978-3-030-24766-9_22(296-310)Online publication date: 5-Aug-2019
https://dl.acm.org/doi/10.1007/978-3-030-24766-9_22
Jansen B(2017)Turing kernelization for finding long paths and cycles in restricted graph classesJournal of Computer and System Sciences10.1016/j.jcss.2016.10.00885:C(18-37)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1016/j.jcss.2016.10.008
dos Santos Souza UProtti F(2017)Tractability, hardness, and kernelization lower bound for and/or graph solutionDiscrete Applied Mathematics10.1016/j.dam.2017.07.029232:C(125-133)Online publication date: 11-Dec-2017
https://dl.acm.org/doi/10.1016/j.dam.2017.07.029
Jansen BPieterse A(2017)Sparsification Upper and Lower Bounds for Graph Problems and Not-All-Equal SATAlgorithmica10.1007/s00453-016-0189-979:1(3-28)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1007/s00453-016-0189-9
Jansen BMarx DIndyk P(2015)Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernelsProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722171(616-629)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722171
Hermelin DKratsch SSołtys KWahlström MWu X(2015)A Completeness Theory for Polynomial (Turing) KernelizationAlgorithmica10.1007/s00453-014-9910-871:3(702-730)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1007/s00453-014-9910-8

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents