Math-1857 · mathematics · Combinatorics

Math-1857

Are t-perfect graphs strongly t-perfect?

Status Open · unsolvedmath.comLLM status Open unverified

Top Open Problems Not reported cataloguedOpenOpen

Statement

Definitions and mathematical statement

For a finite simple graph $G=(V,E)$, a stable set contains no adjacent pair. Its stable-set polytope is the convex hull of the vectors $\mathbf1_I\in\{0,1\}^V$ of stable sets $I$. For $U\subseteq V$, write $x(U)=\sum_{v\in U}x_v$. Consider the system \[ 0\le x_v\le1\ (v\in V),\qquad x_u+x_v\le1\ (uv\in E), \qquad x(V(C))\le (|V(C)|-1)/2 \] for every odd simple cycle $C$ of $G$. Call its feasible polytope $Q(G)$. The graph is $t$-perfect when $Q(G)$ equals its stable-set polytope.

For a rational system $Ax\le b$, total dual integrality means that, for every integral objective vector $c$ whose primal maximum is finite, the dual program \[ \min\{b^Ty:A^Ty=c,\ y\ge0\} \] has an integral optimal solution. A graph is strongly $t$-perfect when the displayed defining system for $Q(G)$ is totally dual integral. Does $t$-perfection always imply strong $t$-perfection?

The defining rows and their normalization matter: total dual integrality is a property of a system, not merely of its feasible set. Vertex upper bounds explicitly handle isolated vertices; for other vertices they follow from an incident edge inequality and nonnegativity. The question asks for integral dual certificates for every integral objective, not just integral vertices of the primal polytope.

Short English statement

Does the usual odd-cycle description of a $t$-perfect graph's stable-set polytope always provide integral optimal dual certificates?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 0

No attempts yet. Significant partial results and substantial reductions are welcome. Contribute an attempt.