Sparsification upper and lower bounds for graph problems and not-all-equal SAT
From MaRDI portal
Publication:2408194
DOI10.1007/s00453-016-0189-9zbMath1372.68129OpenAlexW1909439116WikidataQ59513964 ScholiaQ59513964MaRDI QIDQ2408194
Astrid Pieterse, Bart M. P. Jansen
Publication date: 10 October 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-016-0189-9
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Optimal data reduction for graph coloring using low-degree polynomials ⋮ Sparsification lower bound for linear spanners in directed graphs ⋮ Polynomial kernels for vertex cover parameterized by small degree modulators ⋮ Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials ⋮ Best-case and worst-case sparsifiability of Boolean CSPs ⋮ Parameterized Pre-Coloring Extension and List Coloring Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Kernel bounds for path and cycle problems
- Data reduction for graph coloring problems
- Infeasibility of instance compression and succinct PCPs for NP
- Kernel bounds for disjoint cycles and disjoint paths
- On problems without polynomial kernels
- Which problems have strongly exponential complexity?
- On sparsification for computing treewidth
- FPT is characterized by useful obstruction sets
- Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
- Vertex packings: Structural properties and algorithms
- Sparsification—a technique for speeding up dynamic graph algorithms
- Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials
- Kernelization Lower Bounds Through Colors and IDs
- Kernelization Lower Bounds by Cross-Composition
- Reducibility among Combinatorial Problems
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- SOFSEM 2006: Theory and Practice of Computer Science
