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

2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The \emph{$k$-restricted edge-connectivity} of a graph $G$, denoted by $\lambda_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 $\lambda_k(G)$. Very recently, in the parameterized complexity community the notion of \emph{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.
Type de document :
Pré-publication, Document de travail
15 pages, 3 figures. 2016
Domaine :

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01272707
Contributeur : Ignasi Sau <>
Soumis le : jeudi 11 février 2016 - 11:58:01
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13

### Identifiants

• HAL Id : lirmm-01272707, version 1
• ARXIV : 1502.07659

### Citation

Luis Pedro Montejano, Ignasi Sau. On the complexity of computing the $k$-restricted edge-connectivity of a graph. 15 pages, 3 figures. 2016. 〈lirmm-01272707〉

### Métriques

Consultations de la notice