Abstract
In this paper, we give evidence for the problems Disjoint Cycles and Disjoint Paths that they cannot be preprocessed in polynomial time such that resulting instances always have a size bounded by a polynomial in a specified parameter (or, in short: do not have a polynomial kernel); these results are assuming the validity of certain complexity theoretic assumptions. We build upon recent results by Bodlaender et al. [3] and Fortnow and Santhanam [13], 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 thus obtain that Disjoint Cycles and Disjoint Paths do not have polynomial kernels, unless NP ⊆ coNP/poly. We also show that the related Disjoint Cycles Packing problem has a kernel of size O(k logk).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Hoory, S., Linial, N.: The Moore bound for irregular graphs. Graphs and Combinatorics 18, 53–57 (2002)
Bodlaender, H.L.: A cubic kernel for feedback vertex set. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 320–331. Springer, Heidelberg (2007)
Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels (extended abstract). In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 563–574. Springer, Heidelberg (2008)
Bodlaender, H.L., Penninkx, E.: A linear kernel for planar feedback vertex set. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 160–171. Springer, Heidelberg (2008)
Bodlaender, H.L., Penninkx, E., Tan, R.B.: A linear kernel for the k-disjoint cycle problem on planar graphs. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 306–317. Springer, Heidelberg (2008)
Bodlaender, H.L., Thomassé, S., Yeo, A.: Analysis of data reduction: Transformations give evidence for non-existence of polynomial kernels. Technical Report CS-UU-2008-030, Department of Information and Computer Sciences, Utrecht University, Utrecht, The Netherlands (2008)
Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: Advice classes of parameterized tractability. Annals of Pure and Applied Logic 84, 119–138 (1997)
Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and IDs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. Part I. LNCS, vol. 5555, pp. 378–389. Springer, Heidelberg (2009)
Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: Basic results. SIAM J. Comput. 24, 873–921 (1995)
Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: On completeness for W[1]. Theor. Comp. Sc. 141, 109–131 (1995)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Fernau, H., Fomin, F.V., Lokshtanov, D., Raible, D., Saurabh, S., Villanger, Y.: Kernel(s) for problems with no kernel: On out-trees with many leaves. In: Albers, S., Marion, J.-Y. (eds.) Proceedings 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, pp. 421–432. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany (2009)
Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: Proceedings of the 40th Annual Symposium on Theory of Computing, STOC 2008, pp. 133–142. ACM Press, New York (2008)
Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)
Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. ACM SIGACT News 38, 31–45 (2007)
Karp, R.M.: On the complexity of combinatorial problems. Networks 5, 45–68 (1975)
Kloks, T., Lee, C.M., Liu, J.: New algorithms for k-face cover, k-feedback vertex set, and k-disjoint cycles on plane and planar graphs. In: Kučera, L. (ed.) WG 2002. LNCS, vol. 2573, pp. 282–295. Springer, Heidelberg (2002)
Mathieson, L., Prieto, E., Shaw, P.: Packing edge disjoint triangles: A parameterized view. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol. 3162, pp. 127–137. Springer, Heidelberg (2004)
Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theory Series B 63, 65–110 (1995)
Saurabh, S.: Personal communication (2009)
Thomassé, S.: A quadratic kernel for feedback vertex set. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pp. 115–119 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bodlaender, H.L., Thomassé, S., Yeo, A. (2009). Kernel Bounds for Disjoint Cycles and Disjoint Paths. In: Fiat, A., Sanders, P. (eds) Algorithms - ESA 2009. ESA 2009. Lecture Notes in Computer Science, vol 5757. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04128-0_57
Download citation
DOI: https://doi.org/10.1007/978-3-642-04128-0_57
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04127-3
Online ISBN: 978-3-642-04128-0
eBook Packages: Computer ScienceComputer Science (R0)