Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs

DOI10.1007/978-3-642-16926-7_15MaRDI QIDQ3057621zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
• Tight kernel bounds for problems on graphs with small degeneracy
• The kernelization complexity of connected domination in graphs with (no) small cycles
• scientific article; zbMATH DE number 7720021
• Kernelization and Complexity Results for Connectivity Augmentation Problems
• Kernelization and complexity results for connectivity augmentation problems
• On graph kernels: hardness results and efficient alternatives.
• On kernelization and approximation for the vector connectivity problem
• On kernelization and approximation for the vector connectivity problem

Cites work

• (Meta) Kernelization
• \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves
• An extremal function for contractions of graphs
• Bidimensionality and kernels
• Complexity and Approximation Results for the Connected Vertex Cover Problem
• FPT algorithms for connected feedback vertex set
• scientific article; zbMATH DE number 5485524 (Why is no real title available?)
• Incompressibility through Colors and IDs
• Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
• Lower bound of the Hadwiger number of graphs by their average degree
• On Problems without Polynomial Kernels (Extended Abstract)
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
• The extremal function for complete minors
• Vertex cover: Further observations and further improvements

Cited in

(14)

• Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
• The depression of a graph and \(k\)-kernels
• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy
• Kernel bounds for path and cycle problems
• On the Kernelization Complexity of Colorful Motifs
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Parameterized complexity of Min-power multicast problems in wireless ad hoc networks
• Kernel bounds for path and cycle problems
• Tight kernel bounds for problems on graphs with small degeneracy
• Confronting intractability via parameters
• The kernelization complexity of connected domination in graphs with (no) small cycles
• Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
• scientific article; zbMATH DE number 7720021 (Why is no real title available?)
• Kernelization hardness of connectivity problems in \(d\)-degenerate graphs

This page was built for publication: Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3057621)