Skip to Main content Skip to Navigation
Journal articles

On the complexity of computing the k-restricted edge-connectivity of a graph

Luis Pedro Montejano 1 Ignasi Sau Valls 2
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The k-restricted edge-connectivity of a graph G, denoted by λ 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). 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [33 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01481786
Contributor : Ignasi Sau <>
Submitted on : Friday, December 20, 2019 - 12:21:35 PM
Last modification on : Friday, December 20, 2019 - 12:49:51 PM
Document(s) archivé(s) le : Saturday, March 21, 2020 - 7:36:46 PM

File

1502.07659v2.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Luis Pedro Montejano, Ignasi Sau Valls. On the complexity of computing the k-restricted edge-connectivity of a graph. Theoretical Computer Science, Elsevier, 2017, 662, pp.31-39. ⟨10.1016/j.tcs.2016.12.006⟩. ⟨lirmm-01481786⟩

Share

Metrics

Record views

289

Files downloads

87