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

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

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

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-completeness; parameterized complexity; well-covered graph; FPT-algorithm; \((r, \ell)\)-graph; coW[2-hardness]

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)