Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels

B.M.P. Jansen, D. Marx

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

17 Citations (Scopus)

Abstract

We study two fundamental problems related to finding subgraphs: (1) given graphs G and H, Subgraph Test asks if H is isomorphic to a subgraph of G, (2) given graphs G, H, and an integer t, PACKING asks if G contains t vertex-disjoint subgraphs isomorphic to H. For every graph class F, let F-Subgraph Test and F-Packing be the special cases of the two problems where H is restricted to be in F. Our goal is to study which classes F make the two problems tractable in one of the following senses: - (randomized) polynomial-time solvable, - admits a polynomial (many-one) kernel (that is, has a polynomial-time preprocessing procedure that creates an equivalent instance whose size is polynomially bounded by the size of the solution), or - admits a polynomial Turing kernel (that is, has an adaptive polynomial-time procedure that reduces the problem to a polynomial number of instances, each of which has size bounded polynomially by the size of the solution). To obtain a more robust setting, we restrict our attention to hereditary classes F. It is known that if every component of every graph in F has at most two vertices, then F-Packing is polynomial-time solvable, and NP-hard otherwise. We identify a simple combinatorial property (every component of every graph in F either has bounded size or is a bipartite graph with one of the sides having bounded size) such that if a hereditary class F has this property, then F-Packing admits a polynomial kernel, and has no polynomial (many-one) kernel otherwise, unless the polynomial hierarchy collapses. Furthermore, if F does not have this property, then F-Packing is either WK[1]-hard, W[1]-hard, or Long Path-hard, giving evidence that it does not admit polynomial Turing kernels either. For F-Subgraph Test, we show that if every graph of a hereditary class F satisfies the property that it is possible to delete a bounded number of vertices such that every remaining component has size at most two, then F-Subgraph Test is solvable in randomized polynomial time and it is NP-hard otherwise. We introduce a combinatorial property called (a, b, c, d)-splittability and show that if every graph in a hereditary class F has this property, then F-Subgraph Test admits a polynomial Turing kernel and it is WK[1]-hard, W[1]-hard, or Long Path-hard otherwise. We do not give a complete characterization of the cases when F-Subgraph Test admits polynomial many-one kernels, but show examples that this question is much more fragile than the characterization for Turing kernels.
Original languageEnglish
Title of host publicationTwenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15, San Diego CA, USA, January 4-6, 2015)
Place of PublicationPhiladelphia
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Pages616-629
ISBN (Print)978-1-61197-374-7
DOIs
Publication statusPublished - 2015
Event26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015) - Westin San Diego Gaslamp Quarter, San Diego, United States
Duration: 4 Jan 20156 Jan 2015
Conference number: 26
http://www.siam.org/meetings/da15/

Conference

Conference26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015)
Abbreviated titleSODA '15
CountryUnited States
CitySan Diego
Period4/01/156/01/15
OtherEvent co-located with the 17th Workshop on Algorithm Engineering and Experiments (ALENEX '15) and the 12th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '15)
Internet address

Fingerprint Dive into the research topics of 'Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels'. Together they form a unique fingerprint.

Cite this