Kernel Bounds for Disjoint Cycles and Disjoint Paths

DOI10.1007/978-3-642-04128-0_57zbMath1256.68081OpenAlexW1947666077WikidataQ59567697 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

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Kernel Bounds for Path and Cycle Problems, On the Hardness of Losing Width, Satisfying more than half of a system of linear equations over GF(2): a multivariate approach, Note on maximal bisection above tight lower bound, 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, Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP, Kernelization complexity of possible winner and coalitional manipulation problems in voting, Parameterized Eulerian strong component arc deletion problem on tournaments, Solving MAX-\(r\)-SAT above a tight lower bound, Lower bounds on kernelization, Guarantees and limits of preprocessing in constraint satisfaction and reasoning, Parameterized algorithms for load coloring problem, On the parameterized complexity of vertex cover and edge cover with connectivity constraints, Facility location problems: a parameterized view, Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems, Hitting Forbidden Minors: Approximation and Kernelization, On the Kernelization Complexity of Colorful Motifs, On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems, A parameterized perspective on protecting elections, 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, Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item