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: | |

Look up in GoogleScholar |