# Finding maximum subgraphs with relatively large vertex connectivity

*Alexander Veremyev*,
*Oleg A. Prokopyev*,
*Vladimir Boginski* and
*Eduardo L. Pasiliao*

*European Journal of Operational Research*, 2014, vol. 239, issue 2, 349-362

**Abstract:**
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)

**Date:** 2014

**References:** View references in EconPapers View complete reference list from CitEc

**Citations:** View citations in EconPapers (3) Track citations by RSS feed

**Downloads:** (external link)

http://www.sciencedirect.com/science/article/pii/S0377221714004640

Full text for ScienceDirect subscribers only

**Related works:**

This item may be available elsewhere in EconPapers: Search for items with the same title.

**Export reference:** BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text

**Persistent link:** https://EconPapers.repec.org/RePEc:eee:ejores:v:239:y:2014:i:2:p:349-362

**DOI:** 10.1016/j.ejor.2014.05.041

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

Bibliographic data for series maintained by Haili He ().