On the 2-Club Polytope of Graphs

Foad Mahdavi Pajouh (), Balabhaskar Balasundaram () and Illya V. Hicks ()
Additional contact information
Foad Mahdavi Pajouh: Department of Management Science and Information Systems, University of Massachusetts Boston, Boston, Massachusetts 02125
Balabhaskar Balasundaram: School of Industrial Engineering and Management, Oklahoma State University, Stillwater, Oklahoma 74078
Illya V. Hicks: Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005

Operations Research, 2016, vol. 64, issue 6, 1466-1481

Abstract: A k -club is a subset of vertices of a graph that induces a subgraph of diameter at most k , where k is a positive integer. By definition, 1-clubs are cliques and the model is a distance-based relaxation of the clique definition for larger values of k . The k -club model is particularly interesting to study from a polyhedral perspective as the property is not hereditary on induced subgraphs when k is larger than one. This article introduces a new family of facet-defining inequalities for the 2-club polytope that unifies all previously known facets through a less restrictive combinatorial property, namely, independent (distance) 2-domination. The complexity of separation over this new family of inequalities is shown to be NP-hard. An exact formulation of this separation problem and a greedy separation heuristic are also proposed. The polytope described by the new inequalities (and nonnegativity) is then investigated and shown to be integral for acyclic graphs. An additional family of facets is also demonstrated for cycles of length indivisible by three. The effectiveness of these new facets as cutting planes and the difficulty of solving the separation problem in practice are then investigated via computational experiments on a test bed of benchmark instances.

Keywords: k-club; clique relaxations; 2-club polytope; social network analysis (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2016.1500 (application/pdf)

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:inm:oropre:v:64:y:2016:i:6:p:1466-1481

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().