Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs. (English) Zbl 1357.68073
Fomin, Fedor V. (ed.) et al., Algorithm theory – SWAT 2012. 13th Scandinavian symposium and workshops, Helsinki, Finland, July 4–6, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-31154-3/pbk). Lecture Notes in Computer Science 7357, 364-375 (2012).
Summary: This work further explores the applications of co-nondeterminism for showing kernelization lower bounds. The only known example excludes polynomial kernelizations for the Ramsey problem of finding an independent set or a clique of at least \(k\) vertices in a given graph [the first author, “Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem”, in: Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA’12. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 114–122 (2012; doi:10.1137/1.9781611973099.10)]. We study the more general problem of finding induced subgraphs on \(k\) vertices fulfilling some hereditary property \(\Pi \), called \(\Pi \)-Induced Subgraph. The problem is NP-hard for all non-trivial choices of \(\Pi \) by a classic result of J. M. Lewis and M. Yannakakis [J. Comput. Syst. Sci. 20, 219–230 (1980; Zbl 0436.68029)]. The parameterized complexity of this problem was classified by S. Khot and V. Raman [Theor. Comput. Sci. 289, No. 2, 997–1008 (2002; Zbl 1061.68061)] depending on the choice of \(\Pi \). The interesting cases for kernelization are for \(\Pi \) containing all independent sets and all cliques, since the problem is trivial or W[1]-hard otherwise.
Our results are twofold. Regarding \(\Pi \)-Induced Subgraph, we show that for a large choice of natural graph properties \(\Pi \), including chordal, perfect, cluster, and cograph, there is no polynomial kernel with respect to \(k\). This is established by two theorems: one using a co-nondeterministic variant of cross-composition and one by a polynomial parameter transformation from Ramsey.
Additionally, we show how to use improvement versions of NP-hard problems as source problems for lower bounds, without requiring their NP-hardness. E.g., for \(\Pi \)-Induced Subgraph our compositions may assume existing solutions of size \(k - 1\). We believe this to be useful for further lower bound proofs, since improvement versions simplify the construction of a disjunction (OR) of instances required in compositions. This adds a second way of using co-nondeterminism for lower bounds.
For the entire collection see [Zbl 1243.68018].
Our results are twofold. Regarding \(\Pi \)-Induced Subgraph, we show that for a large choice of natural graph properties \(\Pi \), including chordal, perfect, cluster, and cograph, there is no polynomial kernel with respect to \(k\). This is established by two theorems: one using a co-nondeterministic variant of cross-composition and one by a polynomial parameter transformation from Ramsey.
Additionally, we show how to use improvement versions of NP-hard problems as source problems for lower bounds, without requiring their NP-hardness. E.g., for \(\Pi \)-Induced Subgraph our compositions may assume existing solutions of size \(k - 1\). We believe this to be useful for further lower bound proofs, since improvement versions simplify the construction of a disjunction (OR) of instances required in compositions. This adds a second way of using co-nondeterminism for lower bounds.
For the entire collection see [Zbl 1243.68018].
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68R10 | Graph theory (including graph drawing) in computer science |
