On the (parameterized) complexity of recognizing well-covered (r,l)-graph
On the (parameterized) complexity of recognizing well-covered (r,l)-graph
复制标题
关于识别良好覆盖的 (r,l) 图的（参数化）复杂性
DOI：
10.1016/j.tcs.2018.06.024
复制
发表时间：
2018
影响因子：
1.1
通讯作者：
Alves S
中科院分区：
文献类型：
--
作者：
Alves S
图G的一个（r，n）-划分是指将图G的顶点集划分为r个独立集和r个团。一个图是（r，n），如果它允许一个（r，n）-划分.一个图是好覆盖的，如果每个极大独立集也是极大的。一个图是（r，n）-好覆盖的，如果它既是（r，n）又是好覆盖的。在本文中，我们考虑两个不同的决策问题。在（r，n）-良好覆盖图问题（简称（r，n）wc-g）中，给定一个图G，问题是G是否是（r，n）-良好覆盖图。在Well-Covered（r，n）-图问题（简称wc-（r，n）g）中，给定一个（r，n）-图G和一个（r，n）-划分，问题是G是否是Well-Covered的.这就产生了两个无限族的问题，对于任何固定的非负整数r和r，我们将其分类为P、coNP-完全、NP-完全、NP-困难或coNP-困难。只有当r≥ 3时wc-（r，0）g的情形仍然是开放的。此外，我们考虑了这些问题的参数化复杂性的几个参数的选择，如输入图的最大独立集的大小α，它的邻域多样性，它的团宽度，或在（r，n）-划分的团的数量。特别地，我们证明了确定输入图G的每个极大独立集是否具有基数等于k的参数化问题可以归结为由k参数化的wc-（0，n）g问题.此外，我们还证明了这两个问题都是coW [2]-困难的，但都可以在XP-时间内求解。
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.