On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph

DOI10.1016/j.tcs.2018.06.024zbMath1400.68078OpenAlexW2995257617MaRDI QIDQ1784741

Uéverton S. Souza, Konrad K. Dabrowski, Ignasi Sau, Sancrey Rodrigues Alves, Sulamita Klein, Luérbio Faria

Publication date: 27 September 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.06.024

zbMATH Keywords

coNP-completenessparameterized complexitywell-covered graphFPT-algorithm\((r, \ell)\)-graphcoW[2-hardness]

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity ⋮ Recognizing well-dominated graphs is coNP-complete ⋮ On the complexity of coloring ‐graphs ⋮ Computing well-covered vector spaces of graphs using modular decomposition ⋮ Three remarks on \(\mathbf{W}_{\mathbf{2}}\) graphs ⋮ On the probe problem for \((r,\ell )\)-well-coveredness ⋮ Mind the independence gap ⋮ Partitions and well-coveredness: the graph sandwich problem

Cites Work

• A generalization of Villarreal's result for unmixed tripartite graphs
• Fundamentals of parameterized complexity
• Monadic second-order evaluations on tree-decomposable graphs
• New graph classes of bounded clique-width
• List matrix partitions of chordal graphs
• Recent developments on graphs of bounded clique-width
• Graph minors. X: Obstructions to tree-decomposition
• Well-covered graphs and extendability
• Algorithmic meta-theorems for restrictions of treewidth
• Very well covered graphs
• Partitions of graphs into one or two independent sets and cliques
• Well-covered claw-free graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Parametrized complexity theory.
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• On the (Parameterized) Complexity of Recognizing Well-Covered $$(r,\ell )$$ -graphs
• Complexity results for well‐covered graphs
• List Partitions
• Parameterized Algorithms on Perfect Graphs for Deletion to (r,l)-Graphs
• Unmixed r-partite graphs
• Reducibility among Combinatorial Problems
• Machine Characterizations for Parameterized Complexity Classes Beyond Para-NP
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Paths, Trees, and Flowers
• Parameterized Algorithms
• Some covering concepts in graphs
• Graph-Theoretic Concepts in Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph