Intractability of clique-width parameterizations

DOI10.1137/080742270zbMATH Open1207.68161OpenAlexW2089158353MaRDI QIDQ3053155FDOQ3053155

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

Publication date: 4 November 2010

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

Full work available at URL: https://doi.org/10.1137/080742270

Recommendations

• Clique-width: on the price of generality
• Algorithmic lower bounds for problems parameterized by clique-width
• Clique-width. III: Hamiltonian cycle and the odd case of graph coloring
• Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width

zbMATH Keywords

Hamiltonian cyclechromatic numbergraph coloringclique-widthparameterized complexitytree-widthedge dominationedge dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (50)

• Efficient parallel algorithms for parameterized problems
• Acyclic coloring parameterized by directed clique-width
• Finer tight bounds for coloring on clique-width
• Finer tight bounds for coloring on clique-width
• Spanning trees with few branch vertices in graphs of bounded neighborhood diversity
• A basic parameterized complexity primer
• Clique-width minimization is NP-hard
• Computing the clique-width of cactus graphs
• Efficient computation of the oriented chromatic number of recursively defined digraphs
• Computing directed Steiner path covers
• Cliquewidth III: the odd case of graph coloring parameterized by cliquewidth
• Clique-width. III: Hamiltonian cycle and the odd case of graph coloring
• Between treewidth and clique-width
• Clique-width: on the price of generality
• Computing the chromatic number using graph decompositions via matrix rank
• On the minimum cycle cover problem on graphs with bounded co-degeneracy
• On structural parameterizations of star coloring
• Algorithmic meta-theorems for restrictions of treewidth
• Clique-width is NP-complete
• Title not available (Why is that?)
• Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity
• \(b\)-coloring parameterized by clique-width
• Digraph coloring and distance to acyclicity
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Fast evaluation of interlace polynomials on graphs of bounded treewidth
• Data reduction for graph coloring problems
• Data reduction for graph coloring problems
• Maximum matching in almost linear time on graphs of bounded clique-width
• Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems
• Digraph width measures in parameterized algorithmics
• Approximation algorithms for digraph width parameters
• Algorithmic lower bounds for problems parameterized by clique-width
• Iterated Type Partitions
• Title not available (Why is that?)
• On the complexity of some colorful problems parameterized by treewidth
• Clique-width: when hard does not mean impossible
• On the complexity of finding large odd induced subgraphs and odd colorings
• Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
• Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter
• Structural parameterizations of clique coloring
• Digraphs of bounded width
• Between treewidth and clique-width
• Latency-bounded target set selection in social networks
• Parameterized complexity of distance labeling and uniform channel assignment problems
• Induced tree covering and the generalized Yutsis property
• Optimal centrality computations within bounded clique-width graphs
• A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• Parameterized complexity for iterated type partitions and modular-width

This page was built for publication: Intractability of clique-width parameterizations

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