Abstract
Many graph problems were first shown to be fixed-parameter tractable using the results of Robertson and Seymour on graph minors. We show that the combination of finite, computable, obstruction sets and efficient order tests is not just one way of obtaining strongly uniform FPT algorithms, but that all of FPT may be captured in this way. Our new characterization of FPT has a strong connection to the theory of kernelization, as we prove that problems with polynomial kernels can be characterized by obstruction sets whose elements have polynomial size. Consequently we investigate the interplay between the sizes of problem kernels and the sizes of the elements of such obstruction sets, obtaining several examples of how results in one area yield new insights in the other. We show how exponential-size minor-minimal obstructions for pathwidth k form the crucial ingredient in a novel OR-cross-composition for -̨Pathwidth, complementing the trivial AND-composition that is known for this problem. In the other direction, we show that OR-cross-compositions into a parameterized problem can be used to rule out the existence of efficiently generated quasi-orders on its instances that characterize the NO-instances by polynomial-size obstructions.
This work was supported by the Netherlands Organization for Scientific Research (NWO), project “KERNELS: Combinatorial Analysis of Data Reduction”.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bodlaender, H.L.: Kernelization: New upper and lower bound techniques. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 17–37. Springer, Heidelberg (2009)
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)
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)
Cattell, K., Dinneen, M.J., Downey, R.G., Fellows, M.R., Langston, M.A.: On computing graph minor obstruction sets. Theor. Comput. Sci. 233, 107–127 (2000)
Dinneen, M.J.: Too many minor order obstructions. J. UCS 3, 1199–1206 (1997)
Dinneen, M.J., Cattell, K., Fellows, M.R.: Forbidden minors to graphs with small feedback sets. Discrete Math. 230(1-3), 215–252 (2001)
Dinneen, M.J., Lai, R.: Properties of vertex cover obstructions. Discrete Math. 307(21), 2484–2500 (2007)
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)
Fellows, M.R., Langston, M.A.: Nonconstructive tools for proving polynomial-time decidability. J. ACM 35(3), 727–739 (1988)
Fellows, M.R., Langston, M.A.: An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations (extended abstract). In: Proc. 30th FOCS, pp. 520–525 (1989)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer-Verlag New York, Inc. (2006)
Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar \(\mathcal{F}\)-Deletion: Approximation, kernelization and optimal FPT algorithms. In: Proc. 53rd FOCS, pp. 470–479 (2012)
Jansen, B.M.P., Kratsch, S.: Data reduction for graph coloring problems. In: Owe, O., Steffen, M., Telle, J.A. (eds.) FCT 2011. LNCS, vol. 6914, pp. 90–101. Springer, Heidelberg (2011)
Kinnersley, N.G.: The vertex separation number of a graph equals its path-width. Inf. Process. Lett. 42(6), 345–350 (1992)
Kratsch, S.: Co-nondeterminism in compositions: a kernelization lower bound for a ramsey-type problem. In: Proc. 23rd SODA, pp. 114–122 (2012)
Kratsch, S., Pilipczuk, M., Rai, A., Raman, V.: Kernel lower bounds using co-nondeterminism: Finding induced hereditary subgraphs. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol. 7357, pp. 364–375. Springer, Heidelberg (2012)
Kratsch, S., Wahlström, M.: The AND-conjecture may be necessary. In: Parameterized Complexity Newsletter. FPT Wiki (November 2011)
Lagergren, J.: Upper bounds on the size of obstructions and intertwines. J. Comb. Theory, Ser. B 73(1), 7–40 (1998)
Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J. Comb. Theory, Ser. B 63(1), 65–110 (1995)
Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner’s conjecture. J. Comb. Theory, Ser. B 92(2), 325–357 (2004)
Rué, J., Stavropoulos, K.S., Thilikos, D.M.: Outerplanar obstructions for a feedback vertex set. Eur. J. Comb. 33(5), 948–968 (2012)
Takahashi, A., Ueno, S., Kajitani, Y.: Minimal acyclic forbidden minors for the family of graphs with bounded path-width. Discrete Math. 127, 293–304 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fellows, M.R., Jansen, B.M.P. (2013). FPT Is Characterized by Useful Obstruction Sets. In: Brandstädt, A., Jansen, K., Reischuk, R. (eds) Graph-Theoretic Concepts in Computer Science. WG 2013. Lecture Notes in Computer Science, vol 8165. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45043-3_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-45043-3_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45042-6
Online ISBN: 978-3-642-45043-3
eBook Packages: Computer ScienceComputer Science (R0)