Kernelization: New Upper and Lower Bound Techniques

DOI10.1007/978-3-642-11269-0_2zbMath1273.68158OpenAlexW1606657688WikidataQ59567698 ScholiaQ59567698MaRDI QIDQ3656848

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

algorithms data reduction combinatorial problems fixed parameter tractability kernel kernelization preprocessing

Mathematics Subject Classification ID

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

Related Items

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, 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

Cites Work