Fedor V. Fomin
Skip Abstract Section
Abstract
We give the first linear kernels for the Dominating Set and Connected Dominating Set problems on graphs excluding a fixed graph H as a topological minor. In other words, we prove the existence of polynomial time algorithms that, for a given H-topological-minor-free graph G and a positive integer k, output an H-topological-minor-free graph G′ on O(k) vertices such that G has a (connected) dominating set of size k if and only if G′ has one.
Our results extend the known classes of graphs on which the Dominating Set and Connected Dominating Set problems admit linear kernels. Prior to our work, it was known that these problems admit linear kernels on graphs excluding a fixed apex graph H as a minor. Moreover, for Dominating Set, a kernel of size kc(H), where c(H) is a constant depending on the size of H, follows from a more general result on the kernelization of Dominating Set on graphs of bounded degeneracy. Alon and Gutner explicitly asked whether one can obtain a linear kernel for Dominating Set on H-minor-free graphs. We answer this question in the affirmative and in fact prove a more general result. For Connected Dominating Set no polynomial kernel even on H-minor-free graphs was known prior to our work. On the negative side, it is known that Connected Dominating Set on 2-degenerated graphs does not admit a polynomial kernel unless coNP ⊆ NP/poly.
Our kernelization algorithm is based on a non-trivial combination of the following ingredients
• The structural theorem of Grohe and Marx [STOC 2012] for graphs excluding a fixed graph H as a topological minor;
• A novel notion of protrusions, different than the one defined in [FOCS 2009];
• Our results are based on a generic reduction rule that produces an equivalent instance (in case the input graph is H-minor-free) of the problem, with treewidth O(√ k). The application of this rule in a divide-and-conquer fashion, together with the new notion of protrusions, gives us the linear kernels.
A protrusion in a graph [FOCS 2009] is a subgraph of constant treewidth which is separated from the rest of the graph by at most a constant number of vertices. In our variant of protrusions, instead of stipulating that the subgraph be of constant treewidth, we ask that it contains a constant number of vertices from a solution. We believe that this new take on protrusions would be useful for other graph problems and in different algorithmic settings.
- Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. 2017. Irrelevant vertices for the planar disjoint paths problem. J. Comb. Theor. Ser. B 122 (2017), 815--843.Google Scholar
Cross Ref
- J. Alber, H. L. Bodlaender, H. Fernau, T. Kloks, and R. Niedermeier. 2002. Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica 33, 4 (2002), 461--493.Google ScholarCross Ref
- Jochen Alber, Michael R. Fellows, and Rolf Niedermeier. 2004. Polynomial-time data reduction for dominating sets. J. ACM 51 (2004), 363--384. Google ScholarDigital Library
- Noga Alon and Shai Gutner. 2008. Kernels for the Dominating Set Problem on Graphs with an Excluded Minor. Technical Report TR08-066. ECCC.Google Scholar
- Noga Alon and Shai Gutner. 2009. Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica 54, 4 (2009), 544--556. Google ScholarDigital Library
- Noga Alon, Paul Seymour, and Robin Thomas. 1990. A separator theorem for nonplanar graphs. J. Am. Math. Soc. 3, 4 (1990), 801--808.Google ScholarCross Ref
- Stefan Arnborg, Bruno Courcelle, Andrzej Proskurowski, and Detlef Seese. 1993. An algebraic theory of graph reduction. J. ACM 40 (1993), 1134--1164. Google ScholarDigital Library
- Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. 2007. Fourier meets Möbious: Fast subset convolution. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC’07). ACM Press, 67--74. Google ScholarDigital Library
- Hans L. Bodlaender. 1998. A partial -arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209, 1-2 (1998), 1--45. Google ScholarDigital Library
- Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. 2015. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243 (2015), 86--111. Google ScholarDigital Library
- Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. 2009. On problems without polynomial kernels. J. Comput. Syst. Sci. 75, 8 (2009), 423--434. Google ScholarDigital Library
- Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. 2016. (Meta) kernelization. J. ACM 63, 5 (2016), 44:1--44:69. Google ScholarDigital Library
- Hans L. Bodlaender and Torben Hagerup. 1998. Parallel algorithms with optimal speedup for bounded treewidth. SIAM J. Comput. 27 (1998), 1725--1746. Google ScholarDigital Library
- Hans L. Bodlaender and Babette van Antwerpen-de Fluiter. 2001. Reduction algorithms for graphs of small treewidth. Inf. Comput. 167 (2001), 86--119. Google ScholarDigital Library
- Jianer Chen, Henning Fernau, Iyad A. Kanj, and Ge Xia. 2007. Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. SIAM J. Comput. 37 (2007), 1077--1106. Google ScholarDigital Library
- Marek Cygan, Fabrizio Grandoni, and Danny Hermelin. 2017. Tight kernel bounds for problems on graphs with small degeneracy. ACM Trans. Algorithms 13, 3 (2017), 43:1--43:22. Google ScholarDigital Library
- Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. 2012. Kernelization hardness of connectivity problems in d-degenerate graphs. Discr. Appl. Math. 160, 15 (2012), 2131--2141. Google ScholarDigital Library
- Babette de Fluiter. 1997. Algorithms for Graphs of Small Treewidth. Ph.D. Dissertation. Utrecht University.Google Scholar
- Holger Dell and Dieter van Melkebeek. 2014. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM 61, 4 (2014), 23:1--23:27. Google ScholarDigital Library
- Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. 2005. Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs. ACM Trans. Algor. 1, 1 (2005), 33--47. Google ScholarDigital Library
- Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. 2005. Subexponential parameterized algorithms on bounded-genus graphs and -minor-free graphs. J. ACM 52, 6 (2005), 866--893. Google ScholarDigital Library
- Erik D. Demaine and Mohammad Taghi Hajiaghayi. 2005. Bidimensionality: New connections between FPT algorithms and PTASs. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’05). ACM-SIAM, New York, NY, 590--601. Google ScholarDigital Library
- Erik D. Demaine and Mohammad Taghi Hajiaghayi. 2007. The bidimensionality theory and its algorithmic applications. Comput. J. 51, 3 (2007), 332--337. Google ScholarDigital Library
- Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Ken-ichi Kawarabayashi. 2009. Approximation algorithms via structural results for apex-minor-free graphs. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP’09), Lecture Notes in Comput. Sci., Vol. 5555. Springer, 316--327. Google ScholarDigital Library
- Reinhard Diestel. 2012. Graph Theory (4th ed). Graduate Texts in Mathematics, Vol. 173. Springer.Google Scholar
- Frederic Dorn, Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. 2013. Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs. Inf. Comput. 233 (2013), 60--70. Google ScholarDigital Library
- Rodney G. Downey and Michael R. Fellows. 1998. Parameterized Complexity. Springer.Google Scholar
- Feodor F. Dragan, Fedor V. Fomin, and Petr A. Golovach. 2011. Spanners in sparse graphs. J. Comput. Syst. Sci. 77, 6 (2011), 1108--1119. Google ScholarDigital Library
- Pål Grønås Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. 2016. Kernelization and sparseness: The case of dominating set. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS’16), Vol. 47. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 31:1--31:14.Google Scholar
- Andrew Drucker. 2012. New limits to classical and quantum instance compression. In Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS’12). IEEE, 609--618. Google ScholarDigital Library
- P. Duchet and H. Meyniel. 1982. On Hadwiger’s number and the stability number. In Graph Theory (Cambridge, 1981). North-Holland Math. Stud., Vol. 62. North-Holland, Amsterdam, 71--73.Google Scholar
- Zdenek Dvorak. 2012. A stronger structure theorem for excluded topological minors. CoRR abs/1209.0129 (2012).Google Scholar
- Zdenek Dvorak. 2013. Constant-factor approximation of the domination number in sparse graphs. Eur. J. Comb. 34, 5 (2013), 833--840. Google ScholarDigital Library
- Uriel Feige, Mohammad Taghi Hajiaghayi, and James R. Lee. 2008. Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput. 38, 2 (2008), 629--657. Google ScholarDigital Library
- Michael R. Fellows and Michael A. Langston. 1989. An analogue of the myhill-nerode theorem and its use in computing finite-basis characterizations (extended abstract). In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS’89). IEEE, 520--525. Google ScholarDigital Library
- Jörg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag, Berlin. Google ScholarDigital Library
- Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos. 2011. Contraction obstructions for treewidth. J. Comb. Theor. Ser. B 101, 5 (2011), 302--314. Google ScholarDigital Library
- Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, and Saket Saurabh. 2016. Hitting forbidden minors: Approximation and kernelization. SIAM J. Discr. Math. 30, 1 (2016), 383--410.Google ScholarDigital Library
- Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. 2010. Bidimensionality and EPTAS. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’11). SIAM, 748--759. Google ScholarDigital Library
- Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. 2012. Bidimensionality and geometric graphs. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12). SIAM, 1563--1575. Google ScholarDigital Library
- F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. 2010. Bidimensionality and kernels. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’10). ACM-SIAM, 503--510. Google ScholarDigital Library
- F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos. 2010. Linear kernels for (connected) dominating set on H-minor-free graphs. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12). ACM-SIAM, 82--93. Google ScholarDigital Library
- Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. 2013. Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs. In Proceedings of 30th International Symposium on Theoretical Aspects of Computer Science (STACS’13), Vol. 20. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 92--103.Google Scholar
- Fedor V. Fomin and Dimitrios M. Thilikos. 2006. Dominating sets in planar graphs: Branch-width and exponential speed-up. SIAM J. Comput. 36 (2006), 281--309. Google ScholarDigital Library
- Petr A. Golovach and Yngve Villanger. 2008. Parameterized complexity for domination problems on degenerate graphs. In Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Scienc (WG’08). Lecture Notes in Comput. Sci., Vol. 5344. Springer, Berlin, 195--205. Google ScholarDigital Library
- Martin Grohe. 2003. Local tree-width, excluded minors, and approximation algorithms. Combinatorica 23 (2003), 613--632. Google ScholarDigital Library
- Martin Grohe and Dániel Marx. 2015. Structure theorem and isomorphism test for graphs with excluded topological subgraphs. SIAM J. Comput. 44, 1 (2015), 114--159. Google ScholarDigital Library
- Shai Gutner. 2009. Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor. In Proceedings of the 4th Workshop on Parameterized and Exact Computation (IWPEC’09), Lecture Notes in Computer Science. Springer, 246--257. Google ScholarDigital Library
- Teresa W. Haynes, Stephen T. Hedetniemi, and Peter J. Slater. 1998. Fundamentals of Domination in Graphs. Marcel Dekker Inc., New York, NY.Google Scholar
- Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001. Which problems have strongly exponential complexity?J. Comput. Syst. Sci. 63, 4 (2001), 512--530. Google ScholarDigital Library
- Ken-ichi Kawarabayashi and Yusuke Kobayashi. 2008. The induced disjoint path problem. In Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization (IPCO’08). Lecture Notes in Computer Science, Vol. 5035. Springer, Berlin, 47--61. Google ScholarDigital Library
- Ken-ichi Kawarabayashi and Bruce Reed. 2010. Odd cycle packing. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC’10). ACM, New York, NY, 695--704. Google ScholarDigital Library
- Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar. 2016. Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Trans. Algor. 12, 2 (2016), 21. Google ScholarDigital Library
- Yusuke Kobayashi and Ken-ichi Kawarabayashi. 2009. Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’09). ACM-SIAM, 1146--1155. Google ScholarDigital Library
- Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, Vol. 31. Oxford University Press, Oxford.Google Scholar
- Geevarghese Philip, Venkatesh Raman, and Somnath Sikdar. 2012. Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Trans. Algor. 9, 1 (2012), 11. Google ScholarDigital Library
- Neil Robertson and P. D. Seymour. 1995. Graph minors. XIII. The disjoint paths problem. J. Comb. Theor. Ser. B 63, 1 (1995), 65--110. JCBTB Google ScholarDigital Library
- Neil Robertson and P. D. Seymour. 2003. Graph minors. XVI. Excluding a non-planar graph. J. Combin. Theor. Ser. B 89, 1 (2003), 43--76. JCBTB Google ScholarDigital Library
- Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. 2009. Dynamic programming on tree decompositions using generalised fast subset convolution. In Proceedings of the 17th Annual European Symposium on Algorithms (ESA’09), Lecture Notes in Computer Science, Vol. 5757. Springer, 566--577.Google ScholarCross Ref
Index Terms
- Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors
Recommendations
Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
We show that for every fixed j ≥ i ≥ 1, the k-Dominating Set problem restricted to graphs that do not have Kij (the complete bipartite graph on (i + j) vertices, where the two parts have i and j vertices, respectively) as a subgraph is fixed parameter ...
Linear kernels for (connected) dominating set on H-minor-free graphs
SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithmsWe give the first linear kernels for Dominating Set and Connected Dominating Set problems on graphs excluding a fixed graph H as a minor. In other words, we give polynomial time algorithms that, for a given H-minor free graph G and positive integer k, ...
Dominating set is fixed parameter tractable in claw-free graphs
We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K"1","3, the complete bipartite graph on four vertices where the two parts have one and three vertices, ...
Comments