Abstract
We investigate whether an n-vertex instance (G,k) of Treewidth, asking whether the graph G has treewidth at most k, can efficiently be made sparse without changing its answer. By giving a special form of OR-cross-composition, we prove that this is unlikely: if there is an ε > 0 and a polynomial-time algorithm that reduces n-vertex Treewidth instances to equivalent instances, of an arbitrary problem, with \(\mathcal{O}(n^{2 - \epsilon})\) bits, then NP ⊆ coNP/poly and the polynomial hierarchy collapses to its third level.
Our sparsification lower bound has implications for structural parameterizations of Treewidth: parameterizations by measures that do not exceed the vertex count, cannot have kernels with \(\mathcal{O}(k^{2 - \epsilon})\) bits for any ε > 0, unless NP ⊆ coNP/poly. Motivated by the question of determining the optimal kernel size for Treewidth parameterized by vertex cover, we improve the \(\mathcal{O}(k^3)\)-vertex kernel from Bodlaender et al. (STACS 2011) to a kernel with \(\mathcal{O}(k^2)\) vertices. Our improved kernel is based on a novel form of treewidth-invariant set. We use the q-expansion lemma of Fomin et al. (STACS 2011) to find such sets efficiently in graphs whose vertex count is superquadratic in their vertex cover number.
This work was supported by ERC Starting Grant 306992 “Parameterized Approximation”.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebra. Discr. 8, 277–284 (1987), doi:10.1137/0608024
Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1-2), 1–45 (1998), doi:10.1016/S0304-3975(97)00228-4
Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423–434 (2009), doi:10.1016/j.jcss.2009.04.001
Bodlaender, H.L., Fomin, F.V., Koster, A.M.C.A., Kratsch, D., Thilikos, D.M.: On exact algorithms for treewidth. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 672–683. Springer, Heidelberg (2006)
Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M. (Meta) Kernelization. In: Proc. 50th FOCS, pp. 629–638 (2009), doi:10.1109/FOCS.2009.46
Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: A new technique for kernelization lower bounds. In: Proc. 28th STACS, pp. 165–176 (2011), doi:10.4230/LIPIcs.STACS.2011.165
Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Preprocessing for treewidth: A combinatorial analysis through kernelization. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 437–448. Springer, Heidelberg (2011)
Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernel bounds for structural parameterizations of pathwidth. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 352–363. Springer, Heidelberg (2012)
Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. CoRR, abs/1206.5941, arXiv:1206.5941 (2012)
Bodlaender, H.L., Koster, A.M.C.A.: Safe separators for treewidth. Discrete Math. 306(3), 337–350 (2006), doi:10.1016/j.disc.2005.12.017
Bodlaender, H.L., Koster, A.M.C.A., van den Eijkhof, F.: Preprocessing rules for triangulation of probabilistic networks. Comput. Intell. 21(3), 286–305 (2005), doi:10.1111/j.1467-8640.2005.00274.x
Buss, J.F., Goldsmith, J.: Nondeterminism within P. SIAM J. Comput. 22(3), 560–572 (1993), doi:10.1137/0222038
Cygan, M., Grandoni, F., Hermelin, D.: Tight kernel bounds for problems on graphs with small degeneracy. CoRR, abs/1305.4914, arXiv:1305.4914 (2013)
Dell, H., Marx, D.: Kernelization of packing problems. In: Proc. 23rd SODA, pp. 68–81 (2012)
Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: Proc. 42nd STOC, pp. 251–260 (2010), doi:10.1145/1806689.1806725
Downey, R., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)
Drucker, A.: New limits to classical and quantum instance compression. In: Proc. 53rd FOCS, pp. 609–618 (2012), doi:10.1109/FOCS.2012.71
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer-Verlag New York, Inc. (2006)
Fomin, F.V., Lokshtanov, D., Misra, N., Philip, G., Saurabh, S.: Hitting forbidden minors: Approximation and kernelization. In: Proc. 28th STACS, pp. 189–200 (2011), doi:10.4230/LIPIcs.STACS.2011.189
Hermelin, D., Wu, X.: Weak compositions and their applications to polynomial lower bounds for kernelization. In: Proc. 23rd SODA, pp. 104–113 (2012)
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512–530 (2001), doi:10.1006/jcss.2001.1774
Jansen, B.M.P.: On sparsification for computing treewidth. CoRR, abs/1308.3665, arXiv:1308.3665 (2013)
Jansen, B.M.P.: The Power of Data Reduction: Kernels for Fundamental Graph Problems. PhD thesis, Utrecht University, The Netherlands (2013)
Möhring, R.H.: Triangulating graphs without asteroidal triples. Discrete Appl. Math. 64(3), 281–287 (1996), doi:10.1016/0166-218X(95)00095-9
Thomassé, S.: A 4k 2 kernel for feedback vertex set. ACM Trans. Algorithms 6(2) (2010), doi:10.1145/1721837.1721848
van den Eijkhof, F., Bodlaender, H.L., Koster, A.M.C.A.: Safe reduction rules for weighted treewidth. Algorithmica 47(2), 139–158 (2007), doi:10.1007/s00453-006-1226-x
Yap, C.-K.: Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci. 26, 287–300 (1983), doi:10.1016/0304-3975(83)90020-8
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Jansen, B.M.P. (2013). On Sparsification for Computing Treewidth. In: Gutin, G., Szeider, S. (eds) Parameterized and Exact Computation. IPEC 2013. Lecture Notes in Computer Science, vol 8246. Springer, Cham. https://doi.org/10.1007/978-3-319-03898-8_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-03898-8_19
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03897-1
Online ISBN: 978-3-319-03898-8
eBook Packages: Computer ScienceComputer Science (R0)