Chorded cycle facets of the clique partitioning polytope

Abstract

The $q$-chorded $k$-cycle inequalities are a class of valid inequalities for the clique partitioning polytope. It is known that for $q\in \{2,\frac{k-1}{2}\}$, these inequalities induce facets of the clique partitioning polytope if and only if $k$ is odd. Here, we characterize such facets for arbitrary $k$ and $q$. More specifically, we prove that the $q$-chorded $k$-cycle inequalities induce facets of the clique partitioning polytope if and only if two conditions are satisfied: $k=1$ mod $q$, and if $k=3q+1$ then $q=3$ or $q$ is even. This establishes the existence of many facets induced by $q$-chorded $k$-cycle inequalities beyond those previously known.

12 pages