Kernelization: New Upper and Lower Bound Techniques

DOI10.1007/978-3-642-11269-0_2zbMath1273.68158DBLPconf/iwpec/Bodlaender09OpenAlexW1606657688WikidataQ59567698 ScholiaQ59567698MaRDI QIDQ3656848

Hans L. Bodlaender

Publication date: 14 January 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-11269-0_2

zbMATH Keywords

algorithmsdata reductioncombinatorial problemsfixed parameter tractabilitykernelkernelizationpreprocessing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Advice classes of parametrized tractability
• Graph minors. XX: Wagner's conjecture
• Graph minors. III. Planar tree-width
• Strong computational lower bounds via parameterized complexity
• Experiments on data reduction for optimal domination in networks
• A cubic kernel for feedback vertex set and loop cutset
• A more effective linear kernelization for cluster editing
• The parameterized complexity of the induced matching problem
• Fixed-parameter algorithms for Kemeny rankings
• Minimum leaf out-branching and related problems
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Every planar map is four colorable. I: Discharging
• A partial k-arboretum of graphs with bounded treewidth
• On fixed-parameter tractability and approximability of NP optimization problems
• Reduction algorithms for graphs of small treewidth
• On the existence of subexponential parameterized algorithms
• Graph minors. XIII: The disjoint paths problem
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• Parameterized complexity of Vertex Cover variants
• Crown structures for vertex cover kernelization
• Parametrized complexity theory.
• On the computational hardness based on linear fpt-reductions
• Tight lower bounds for certain parameterized NP-hard problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Kernels for Feedback Arc Set In Tournaments
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
• A Linear Kernel for Planar Feedback Vertex Set
• Exact Algorithms for Cluster Editing: Evaluation and Experiments
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• On Problems without Polynomial Kernels (Extended Abstract)
• Polynomial-time data reduction for dominating set
• A Problem Kernelization for Graph Packing
• Quadratic Kernelization for Convex Recoloring of Trees
• Linear Kernel for Planar Connected Dominating Set
• Incompressibility through Colors and IDs
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
• Planar Capacitated Dominating Set Is W[1-Hard]
• On Finding Directed Trees with Many Leaves
• Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor
• Two Edge Modification Problems without Polynomial Kernels
• Vertex packings: Structural properties and algorithms
• Nondeterminism within $P^ * $
• An algebraic theory of graph reduction
• Approximation algorithms for NP-complete problems on planar graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• (Meta) Kernelization
• Data Reduction, Exact, and Heuristic Algorithms for Clique Cover
• Mathematical Foundations of Computer Science 2004
• A POLYNOMIAL KERNEL FOR MULTICUT IN TREES
• Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
• Bidimensionality and Geometric Graphs
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Automata, Languages and Programming
• Mathematical Foundations of Computer Science 2005
• SOFSEM 2006: Theory and Practice of Computer Science

Related Items (61)

Possible winner problems on partial tournaments: a parameterized study ⋮ Improved Parameterized Algorithms for above Average Constraint Satisfaction ⋮ Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs ⋮ Studies in Computational Aspects of Voting ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Planar graph vertex partition for linear problem kernels ⋮ A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion ⋮ The parameterized complexity of local search for TSP, more refined ⋮ Tractability, hardness, and kernelization lower bound for and/or graph solution ⋮ Clique Cover and Graph Separation ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ Change-making problems revisited: a parameterized point of view ⋮ Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ Two-layer planarization parameterized by feedback edge set ⋮ Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints ⋮ Improved linear problem kernel for planar connected dominating set ⋮ Data reduction for graph coloring problems ⋮ Polynomial kernels for proper interval completion and related problems ⋮ Knapsack problems: a parameterized point of view ⋮ Recognizing k -Leaf Powers in Polynomial Time, for Constant k ⋮ Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables ⋮ On making directed graphs transitive ⋮ Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP ⋮ Polynomial kernels for hitting forbidden minors under structural parameterizations ⋮ Kernel bounds for disjoint cycles and disjoint paths ⋮ Solving MAX-\(r\)-SAT above a tight lower bound ⋮ A cubic-vertex kernel for flip consensus tree ⋮ Graph-based data clustering with overlaps ⋮ Towards optimal kernel for edge-disjoint triangle packing ⋮ A generalization of Nemhauser and Trotter's local optimization theorem ⋮ Towards optimal and expressive kernelization for \(d\)-hitting set ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ An Improved Kernel for Planar Connected Dominating Set ⋮ Fixed-parameter algorithms for DAG partitioning ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ On parameterized independent feedback vertex set ⋮ On making a distinguished vertex of minimum degree by vertex deletion ⋮ Constant thresholds can make target set selection tractable ⋮ Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring ⋮ Multivariate complexity analysis of Swap Bribery ⋮ Average parameterization and partial kernelization for computing medians ⋮ Measuring Indifference: Unit Interval Vertex Deletion ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ Turing kernelization for finding long paths and cycles in restricted graph classes ⋮ Faster Existential FO Model Checking on Posets ⋮ The role of twins in computing planar supports of hypergraphs ⋮ On Making a Distinguished Vertex Minimum Degree by Vertex Deletion ⋮ Polynomial Kernels for Proper Interval Completion and Related Problems ⋮ FPT is characterized by useful obstruction sets ⋮ On bounded-degree vertex deletion parameterized by treewidth ⋮ Unnamed Item ⋮ On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments ⋮ Parameterized Complexity of Control and Bribery for d-Approval Elections ⋮ Using patterns to form homogeneous teams ⋮ A refined complexity analysis of degree anonymization in graphs ⋮ A complete parameterized complexity analysis of bounded planning ⋮ Parameterized complexity of control and bribery for \(d\)-approval elections ⋮ A refined branching algorithm for the maximum satisfiability problem

This page was built for publication: Kernelization: New Upper and Lower Bound Techniques