Skip to Main content Skip to Navigation
Journal articles

On the (Parameterized) Complexity of Recognizing Well-Covered $(r,l)$-graphs

Abstract : An (r,)-partition of a graph G is a partition of its vertex set into r independent sets and cliques. A graph is (r,) if it admits an (r,)-partition. A graph is well-covered if every maximal independent set is also maximum. A graph is (r,)-well-covered if it is both (r,) and well-covered. In this paper we consider two different decision problems. In the (r,)-Well-Covered Graph problem ((r,)wc-g for short), we are given a graph G, and the question is whether G is an (r,)-well-covered graph. In the Well-Covered (r,)-Graph problem (wc-(r,)g for short), we are given an (r,)-graph G together with an (r,)partition, and the question is whether G is well-covered. This generates two infinite families of problems, for any fixed non-negative integers r and , which we classify as being P, coNP-complete, NP-complete, NP-hard, or coNP-hard. Only the cases wc-(r, 0)g for r ≥ 3 remain open. In addition, we consider the parameterized complexity of these problems for several choices of parameters, such as the size α of a maximum independent set of the input graph, its neighborhood diversity, its clique-width, or the number of cliques in an (r,)-partition. In particular, we show that the parameterized problem of determining whether every maximal independent set of an input graph G has cardinality equal to k can be reduced to the wc-(0,)g problem parameterized by. In addition, we prove that both problems are coW[2]-hard but can be solved in XP-time.
Document type :
Journal articles
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03110090
Contributor : Isabelle Gouat <>
Submitted on : Friday, January 15, 2021 - 4:34:09 PM
Last modification on : Saturday, January 16, 2021 - 11:17:14 AM
Long-term archiving on: : Friday, April 16, 2021 - 6:54:56 PM

File

Well-covered-TCS-final.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Sancrey Rodrigues Alves, Konrad Dabrowski, Luerbio Faria, Sulamita Klein, Ignasi Sau Valls, et al.. On the (Parameterized) Complexity of Recognizing Well-Covered $(r,l)$-graphs. Theoretical Computer Science, Elsevier, 2018, 746, pp.36-48. ⟨10.1016/j.tcs.2018.06.024⟩. ⟨lirmm-03110090⟩

Share

Metrics

Record views

52

Files downloads

17