Kernel Bounds for Disjoint Cycles and Disjoint Paths

DOI10.1007/978-3-642-04128-0_57zbMath1256.68081WikidataQ59567697 ScholiaQ59567697MaRDI QIDQ3639278

Anders Yeo, Hans L. Bodlaender, Steéphan Thomassé

Publication date: 29 October 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C38: Paths and cycles

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Parameterized complexity of Min-power multicast problems in wireless ad hoc networks, On the parameterized complexity of the repetition free longest common subsequence problem, Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables, Parameterized Eulerian strong component arc deletion problem on tournaments, Lower bounds on kernelization, Guarantees and limits of preprocessing in constraint satisfaction and reasoning, On the parameterized complexity of vertex cover and edge cover with connectivity constraints, Solving MAX-\(r\)-SAT above a tight lower bound, Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems, Kernelization complexity of possible winner and coalitional manipulation problems in voting, Note on maximal bisection above tight lower bound, A parameterized perspective on protecting elections, Facility location problems: a parameterized view, Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP, Parameterized algorithms for load coloring problem, Satisfying more than half of a system of linear equations over GF(2): a multivariate approach, Hitting Forbidden Minors: Approximation and Kernelization, Kernel Bounds for Path and Cycle Problems, On the Hardness of Losing Width, On the Kernelization Complexity of Colorful Motifs, On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems, Data Reduction for Graph Coloring Problems, Parameterized Complexity of Vertex Deletion into Perfect Graph Classes, Kernelization: New Upper and Lower Bound Techniques, Two Edge Modification Problems without Polynomial Kernels