How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs
From MaRDI portal
Publication:5111869
DOI10.4230/LIPIcs.IPEC.2017.10zbMath1443.68071OpenAlexW2936634590MaRDI QIDQ5111869
Publication date: 27 May 2020
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8556/pdf/LIPIcs-IPEC-2017-10.pdf/
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (4)
Grid recognition: classical and parameterized computational perspectives ⋮ Optimal data reduction for graph coloring using low-degree polynomials ⋮ Hitting minors on bounded treewidth graphs. III. Lower bounds ⋮ Polynomial kernels for vertex cover parameterized by small degree modulators
Cites Work
- Unnamed Item
- Unnamed Item
- Kernelization using structural parameters on sparse graph classes
- Sparsity. Graphs, structures, and algorithms
- Infeasibility of instance compression and succinct PCPs for NP
- On problems without polynomial kernels
- On the hardness of losing width
- Crown structures for vertex cover kernelization
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Reflections on Multivariate Algorithmics and Problem Parameterization
- Vertex Cover Structural Parameterization Revisited
- Explicit Linear Kernels via Dynamic Programming
- Incompressibility through Colors and IDs
- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- A Faster Parameterized Algorithm for Treedepth
- (Meta) Kernelization
- Parameterized and Exact Computation
- Bidimensionality and Geometric Graphs
This page was built for publication: How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs
