Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs

DOI10.1007/978-3-642-16926-7_15zbMath1309.68079OpenAlexW2143396993MaRDI QIDQ3057621

Michał Pilipczuk, Marcin Pilipczuk, Jakub Onufry Wojtaszczyk, Marek Cygan

Publication date: 16 November 2010

Published in: Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16926-7_15

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)

Related Items

Kernel Bounds for Path and Cycle Problems ⋮ Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter ⋮ Parameterized complexity of Min-power multicast problems in wireless ad hoc networks ⋮ Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity ⋮ Kernel bounds for path and cycle problems ⋮ Confronting intractability via parameters ⋮ The kernelization complexity of connected domination in graphs with (no) small cycles ⋮ On the Kernelization Complexity of Colorful Motifs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Lower bound of the Hadwiger number of graphs by their average degree
• The extremal function for complete minors
• Vertex Cover: Further Observations and Further Improvements
• An extremal function for contractions of graphs
• FPT Algorithms for Connected Feedback Vertex Set
• Complexity and Approximation Results for the Connected Vertex Cover Problem
• On Problems without Polynomial Kernels (Extended Abstract)
• Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
• Incompressibility through Colors and IDs
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
• (Meta) Kernelization
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
• Bidimensionality and Geometric Graphs
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs