On the (Parameterized) Complexity of Recognizing Well-Covered $(r,l)$-graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2018

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

Résumé

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.
Fichier principal
Vignette du fichier
Well-covered-TCS-final.pdf (455.64 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-03110090 , version 1 (15-01-2021)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More