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

Alves, Sancrey Rodrigues; Dabrowski, Konrad K.; Faria, Luerbio; Klein, Sulamita; Sau, Ignasi; dos Santos Souza, Uéverton; Chan, T.-H. Hubert; Li, Minming; Wang, Lusheng

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,ℓ) wcg 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 of V(G) into r independent sets and ℓℓ cliques, and the question is whether G is well-covered. We classify most of these problems into P, coNP-complete, NP-complete, NP-hard, or coNP-hard. Only the cases wc(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, or the number ℓℓ of cliques in an (r,ℓ)(r,ℓ)-partition. In particular, we show that the parameterized problem of deciding whether a general graph is well-covered parameterized by αα can be reduced to the wc (0,ℓ)(0,ℓ) g problem parameterized by ℓℓ, and we prove that this latter problem is in XP but does not admit polynomial kernels unless coNP⊆NP/polycoNP⊆NP/poly.

Citation

Alves, S. R., Dabrowski, K. K., Faria, L., Klein, S., Sau, I., dos Santos Souza, U., Chan, T.-H. H., Li, M., & Wang, L. (2016, December). On the (Parameterized) Complexity of Recognizing Well-covered (r,l)-graphs. Presented at 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2016), Hong Kong, China

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2016)
• Start Date: Dec 16, 2016
• End Date: Dec 18, 2016
• Acceptance Date: Sep 2, 2016
• Online Publication Date: Oct 31, 2016
• Publication Date: Oct 31, 2016
• Deposit Date: Nov 26, 2016
• Publicly Available Date: Oct 31, 2017
• Print ISSN: 0302-9743
• Pages: 423-437
• Series Title: Lecture notes in computer science
• Series Number: 10043
• Series ISSN: 0302-9743,1611-3349
• Book Title: Combinatorial optimization and applications : 10th International Conference, COCOA 2016, Hong Kong, China, December 16–18, 2016 ; proceedings.
• ISBN: 9783319487489
• DOI: https://doi.org/10.1007/978-3-319-48749-6_31
• Public URL: https://durham-repository.worktribe.com/output/1149318