Are t-perfect graphs strongly t-perfect?
Status Open · unsolvedmath.comLLM status Open unverified
Top Open Problems Not reported cataloguedOpenOpenStatement
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
- S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000004 (AMR-029-0004), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
- S2 Egres Open - List of open problems, Open-problem page: Are t-perfect graphs strongly t-perfect?. Original source indexed by AMR-029-0004. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
- S3 EGRES Open, Are t-perfect graphs strongly t-perfect?. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Are_t-perfect_graphs_strongly_t-perfect%3F.
Statement licence: CC-BY-4.0 · Source file
Contributions 0
No attempts yet. Significant partial results and substantial reductions are welcome. Contribute an attempt.