Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width

DOI10.1007/978-3-642-28050-4_17zbMath1352.68095OpenAlexW1882421805MaRDI QIDQ2891349

Viresh Patel, Petr A. Golovach, Hajo J. Broersma

Publication date: 15 June 2012

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-28050-4_17

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Strong computational lower bounds via parameterized complexity
• The complexity of regular subgraph recognition
• Parameterized complexity of finding regular induced subgraphs
• Clustering and domination in perfect graphs
• Deciding whether a planar graph has a cubic subgraph is NP-complete
• \(k\)-NLC graphs and polynomial algorithms
• On locating cubic subgraphs in bounded-degree connected bipartite graphs
• Which problems have strongly exponential complexity?
• On the existence of subexponential parameterized algorithms
• Finding regular subgraphs in both arbitrary and planar graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Approximating clique-width and branch-width
• On the computational hardness based on linear fpt-reductions
• Tight lower bounds for certain parameterized NP-hard problems
• Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
• Capacitated Domination and Covering: A Parameterized Perspective
• Clique-Width is NP-Complete
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• Planar Capacitated Dominating Set Is W[1-Hard]
• Greedily Finding a Dense Subgraph
• Finding Branch-Decompositions and Rank-Decompositions
• Three‐regular subgraphs of four‐regular graphs
• The dense \(k\)-subgraph problem

This page was built for publication: Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width