2015/02/26 by Luis Pedro Montejano, Montejano, Luis Pedro, Ignasi Sau +1
Computer Science · #05C85 #68R10 #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.2 #acm:05C85 #acm:68R10 #cs.DM #cs.DS #msc:05C85 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1502.07659
16 pages, 4 figures
arxiv created 2016/09/17 · arxiv updated 2016/09/20
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.