On the complexity of computing the k-restricted edge-connectivity of a graph
详细信息 查看全文
- 作者：Luis Pedro Montejano<sup>asup><sup> ; sup><sup>lpmontejano@gmail.comsup> ; Ignasi Sau<sup>bsup><sup> ; sup><sup>ignasi.sau@lirmm.frsup>
- 关键词：Graph cut ; k-Restricted edge-connectivity ; Good edge separation ; Parameterized complexity ; FPT-algorithm ; Polynomial kernel
- 刊名：Theoretical Computer Science
- 出版年：2017
- 出版时间：1 February 2017
- 年：2017
- 卷：662
- 期：Complete
- 页码：31-39
- 全文大小：404 K
- 卷排序：662
文摘
The k-restricted edge-connectivity of a graph G , denoted by λk(G)λk(G), is defined as the minimum size of an edge set whose removal leaves exactly two connected components each containing at least k vertices. This graph invariant, which can be seen as a generalization of a minimum edge-cut, has been extensively studied from a combinatorial point of view. However, very little is known about the complexity of computing λk(G)λk(G). Very recently, in the parameterized complexity community the notion of good edge separation of a graph has been defined, which happens to be essentially the same as the k-restricted edge-connectivity. Motivated by the relevance of this invariant from both combinatorial and algorithmic points of view, in this article we initiate a systematic study of its computational complexity, with special emphasis on its parameterized complexity for several choices of the parameters. We provide a number of NP-hardness and W[1]-hardness results, as well as FPT-algorithms.