Kernel Lower Bounds using Co-Nondeterminism: Finding Induced Hereditary Subgraphs (Q2828227): Difference between revisions

@@ Property / full work available at URL @@
+https://doi.org/10.1145/2691321
@@ Property / full work available at URL: https://doi.org/10.1145/2691321 / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2090698092
@@ Property / OpenAlex ID: W2090698092 / rank @@
+Normal rank
@@ Property / cites work @@
+Ramsey-type theorems with forbidden subgraphs
@@ Property / cites work: Ramsey-type theorems with forbidden subgraphs / rank @@
+Normal rank
@@ Property / cites work @@
+On problems without polynomial kernels
@@ Property / cites work: On problems without polynomial kernels / rank @@
+Normal rank
@@ Property / cites work @@
+Kernelization Lower Bounds by Cross-Composition
@@ Property / cites work: Kernelization Lower Bounds by Cross-Composition / rank @@
+Normal rank
@@ Property / cites work @@
+Kernel bounds for disjoint cycles and disjoint paths
+Normal rank
@@ Property / cites work @@
+Fixed-parameter tractability of graph modification problems for hereditary properties
+Normal rank
@@ Property / cites work @@
+Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
+Normal rank
@@ Property / cites work @@
+Q5315023
@@ Property / cites work: Q5315023 / rank @@
+Normal rank
@@ Property / cites work @@
+Incompressibility through Colors and IDs
@@ Property / cites work: Incompressibility through Colors and IDs / rank @@
+Normal rank
@@ Property / cites work @@
+Q5759552
@@ Property / cites work: Q5759552 / rank @@
+Normal rank
@@ Property / cites work @@
+A Polynomial Kernel for Proper Interval Vertex Deletion
+Normal rank
@@ Property / cites work @@
+Infeasibility of instance compression and succinct PCPs for NP
+Normal rank
@@ Property / cites work @@
+Algorithmic graph theory and perfect graphs
@@ Property / cites work: Algorithmic graph theory and perfect graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
+Normal rank
@@ Property / cites work @@
+Parameterized complexity of finding subgraphs with hereditary properties.
+Normal rank
@@ Property / cites work @@
+Kernel Lower Bounds Using Co-nondeterminism: Finding Induced Hereditary Subgraphs
+Normal rank
@@ Property / cites work @@
+The node-deletion problem for hereditary properties is NP-complete
+Normal rank
@@ Property / cites work @@
+Chordal deletion is fixed-parameter tractable
@@ Property / cites work: Chordal deletion is fixed-parameter tractable / rank @@
+Normal rank
@@ Property / cites work @@
+Measuring Indifference: Unit Interval Vertex Deletion
+Normal rank
@@ Property / cites work @@
+Proper interval vertex deletion
@@ Property / cites work: Proper interval vertex deletion / rank @@
+Normal rank