Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
From MaRDI portal
Publication:388791
DOI10.1016/j.tcs.2013.03.008zbMath1297.05163OpenAlexW2164428079MaRDI QIDQ388791
Petr A. Golovach, Viresh Patel, Hajo J. Broersma
Publication date: 7 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2013.03.008
Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
Complexity and approximability of the happy set problem ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Computing densest \(k\)-subgraph with structural parameters ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized algorithms for the happy set problem ⋮ Slightly Superexponential Parameterized Problems ⋮ Graph classes and approximability of the happy set problem ⋮ Computations by fly-automata beyond monadic second-order logic
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized complexity of finding small degree-constrained subgraphs
- Editing graphs to satisfy degree constraints: a parameterized approach
- On the approximability of some degree-constrained subgraph problems
- 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
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- 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?
- 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
- Parametrized complexity theory.
- Approximating clique-width and branch-width
- On the computational hardness based on linear fpt-reductions
- Tight lower bounds for certain parameterized NP-hard problems
- Capacitated Domination and Covering: A Parameterized Perspective
- Clique-Width is NP-Complete
- 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
