Finding maximum subgraphs with relatively large vertex connectivity
Oleg A. Prokopyev,
Vladimir Boginski and
Eduardo L. Pasiliao
European Journal of Operational Research, 2014, vol. 239, issue 2, pages 349-362
We consider a clique relaxation model based on the concept of relative vertex connectivity. It extends the classical definition of a k-vertex-connected subgraph by requiring that the minimum number of vertices whose removal results in a disconnected (or a trivial) graph is proportional to the size of this subgraph, rather than fixed at k. Consequently, we further generalize the proposed approach to require vertex-connectivity of a subgraph to be some function f of its size. We discuss connections of the proposed models with other clique relaxation ideas from the literature and demonstrate that our generalized framework, referred to as f-vertex-connectivity, encompasses other known vertex-connectivity-based models, such as s-bundle and k-block. We study related computational complexity issues and show that finding maximum subgraphs with relatively large vertex connectivity is NP-hard. An interesting special case that extends the R-robust 2-club model recently introduced in the literature, is also considered. In terms of solution techniques, we first develop general linear mixed integer programming (MIP) formulations. Then we describe an effective exact algorithm that iteratively solves a series of simpler MIPs, along with some enhancements, in order to obtain an optimal solution for the original problem. Finally, we perform computational experiments on several classes of random and real-life networks to demonstrate performance of the developed solution approaches and illustrate some properties of the proposed clique relaxation models.
Keywords: Vertex connectivity; Clique relaxations; Computational complexity; Mixed integer programming; 2-Club (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations Track citations by RSS feed
Downloads: (external link)
Full text for ScienceDirect subscribers only
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: http://EconPapers.repec.org/RePEc:eee:ejores:v:239:y:2014:i:2:p:349-362
Access Statistics for this article
European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati
More articles in European Journal of Operational Research from Elsevier
Series data maintained by Dana Niculescu ().