Improved kernel results for some FPT problems based on simple observations

DOI10.1016/j.tcs.2016.06.012zbMath1356.68102OpenAlexW2425261484MaRDI QIDQ507431

Qilong Feng, Shuai Hu, Wenjun Li, Jian'er Chen

Publication date: 6 February 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.06.012

zbMATH Keywords

NP-hardfixed-parameter tractabilitykernelization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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 (10)

Dealing with several parameterized problems by random methods ⋮ Parameterized algorithms for edge biclique and related problems ⋮ Faster deterministic algorithm for \textsc{Co-Path Set} ⋮ Improved PTAS for the constrained \(k\)-means problem ⋮ An improved FPT algorithm for almost forest deletion problem ⋮ On the parameterized complexity of contraction to generalization of trees ⋮ An improved linear kernel for the cycle contraction problem ⋮ An approximation algorithm for the \(l\)-pseudoforest deletion problem ⋮ An improved linear kernel for complementary maximal strip recovery: simpler and smaller ⋮ On the Parameterized Complexity of Contraction to Generalization of Trees.

Cites Work

• Unnamed Item
• Unnamed Item
• Planar graph vertex partition for linear problem kernels
• Improved linear problem kernel for planar connected dominating set
• Matching and weighted \(P_2\)-packing: algorithms and kernels
• The kernelization complexity of connected domination in graphs with (no) small cycles
• Improved parameterized algorithms for minimum link-length rectilinear spanning path problem
• A linear kernel for a planar connected dominating set
• Complexity and parameterized algorithms for cograph editing
• Finding odd cycle transversals.
• Edge-contraction problems
• Graph-modeled data clustering: Exact algorithms for clique generation
• A practical exact algorithm for the individual haplotyping problem MEC/GI
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Chordal deletion is fixed-parameter tractable
• Parameterized algorithmics for linear arrangement problems
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Cluster editing: kernelization based on edge cuts
• Parameterized computational complexity of Dodgson and Young elections
• Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems
• Parameterized complexity of control and bribery for \(d\)-approval elections
• Radiation hybrid map construction problem parameterized
• Contracting graphs to paths and trees
• Crown structures for vertex cover kernelization
• Domination Problems in Nowhere-Dense Classes
• Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set
• Contractibility and NP-completeness
• Color-coding
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• (Meta) Kernelization
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• Bidimensionality and Geometric Graphs

This page was built for publication: Improved kernel results for some FPT problems based on simple observations