On the 2-club polytope of graphs

Foad Mahdavi Pajouh, Balabhaskar Balasundaram, Illya V. Hicks

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

A κ-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 κ-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.

Original languageEnglish
Pages (from-to)1466-1481
Number of pages16
JournalOper Res
Volume64
Issue number6
DOIs
StatePublished - 1 Nov 2016

Keywords

  • 2-club polytope
  • Clique relaxations
  • Social network analysis
  • κ-club

Fingerprint

Dive into the research topics of 'On the 2-club polytope of graphs'. Together they form a unique fingerprint.

Cite this