Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

On the (parameterized) complexity of recognizing well-covered ( r , ℓ )-graph.

Alves, Sancrey Rodrigues and Dabrowski, Konrad K. and Faria, Luerbio and Klein, Sulamita and Sau, Ignasi and Souza, Uéverton S. (2018) 'On the (parameterized) complexity of recognizing well-covered ( r , ℓ )-graph.', Theoretical computer science., 746 . pp. 36-48.

Abstract

An (r,ℓ)(r,ℓ)-partition of a graph G is a partition of its vertex set into r independent sets and ℓ cliques. A graph is (r,ℓ)(r,ℓ) if it admits an (r,ℓ)(r,ℓ)-partition. A graph is well-covered if every maximal independent set is also maximum. A graph is (r,ℓ)(r,ℓ)-well-covered if it is both (r,ℓ)(r,ℓ) and well-covered. In this paper we consider two different decision problems. In the (r,ℓ)(r,ℓ)-Well-Covered Graph problem ((r,ℓ)(r,ℓ)wc-g for short), we are given a graph G, and the question is whether G is an (r,ℓ)(r,ℓ)-well-covered graph. In the Well-Covered(r,ℓ)(r,ℓ)-Graph problem (wc-(r,ℓ)(r,ℓ)g for short), we are given an (r,ℓ)(r,ℓ)-graph G together with an (r,ℓ)(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)(r,0)g for r≥3r≥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,ℓ)(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,ℓ)(0,ℓ)g problem parameterized by ℓ. In addition, we prove that both problems are coW[2]-hard but can be solved in XP-time.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
(433Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1016/j.tcs.2018.06.024
Publisher statement:© 2018 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
Date accepted:12 June 2018
Date deposited:26 June 2018
Date of first online publication:22 June 2018
Date first made open access:22 June 2019

Save or Share this output

Export:
Export
Look up in GoogleScholar