Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width

DOI10.1137/130910932zbMath1306.05181OpenAlexW1999145171WikidataQ60488400 ScholiaQ60488400MaRDI QIDQ5173247

Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh

Publication date: 9 February 2015

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/c03e94ded9e205867e041aec76b06cf3e724df34

zbMATH Keywords

clique-widthexponential time hypothesismax-cutedge dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (23)

Unnamed Item ⋮ Known Algorithms for Edge Clique Cover are Probably Optimal ⋮ Computing the largest bond and the maximum connected cut of a graph ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Integer programming in parameterized complexity: five miniatures ⋮ On the minimum cycle cover problem on graphs with bounded co-degeneracy ⋮ Fast exact algorithms for some connectivity problems parameterized by clique-width ⋮ Unnamed Item ⋮ Complexity of maximum cut on interval graphs ⋮ Integer Programming in Parameterized Complexity: Three Miniatures. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. ⋮ \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited ⋮ Unnamed Item ⋮ Digraphs of Bounded Width ⋮ Optimal centrality computations within bounded clique-width graphs ⋮ Maximum matching in almost linear time on graphs of bounded clique-width ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints

This page was built for publication: Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width