T-perfect and h-perfect graphs
t-perfect and strongly t-perfect graphs
A graph G=(V, E) is t-perfect if its stable set polytope is determined by the system
[math]\begin{array}{rll} x(v) & \geq 0 & \text{ for each } v \in V,\\ x(u) + x(v) & \leq 1 & \text{ for each } uv \in E,\\ x(V(C)) & \leq \lfloor |V(C)|/2 \rfloor & \text{ for each odd circuit } C. \end{array} [/math]
A graph is strongly t-perfect if the above system is TDI.
A motivation for defining t-perfectness is that the third condition can be checked in polynomial time. Eisenbrand et al. [1] gave a combinatorial, polynomial-time algorithm for finding a maximum weight stable set in a t-perfect graph. For a detailed description, see Chapter 68 of Schrijver's book [2]. Polynomial-time recognition of t-perfect graphs is open, but it is solved for claw-free t-perfect graphs [3].
h-perfect graphs
A graph G=(V, E) is h-perfect if its stable set polytope is determined by the system
[math]\begin{array}{rll} x(v) & \geq 0 & \text{ for each } v \in V,\\ x(Q) & \leq 1 & \text{ for each clique } Q,\\ x(V(C)) & \leq \lfloor |V(C)|/2 \rfloor & \text{ for each odd circuit } C. \end{array} [/math]
The class of h-perfect graphs was introduced by Sbihi and Uhry [4]; it is a superclass of perfect and t-perfect graphs. The maximum weight stable set can be found in polynomial time in h-perfect graphs using semidefinite programming [5]; however, no combinatorial algorithm is known.
References
- ↑ F. Eisenbrand, S. Funke, N. Garg, J. Könemann, A combinatorial algorithm for computing a maximum independent set in a t-perfect graph, ACM link, author link
- ↑ A. Schrijver, Combinatorial Optimization - Polyhedra and Efficiency, Springer, google books link
- ↑ H. Bruhn, O. Schaudt, Claw-free t-perfect graphs can be recognised in polynomial time, DOI link, author link
- ↑ N. Sbihi, J.P. Uhry, A class of h-perfect graphs, DOI link
- ↑ L. Lovász, A. Schrijver, Cones of matrices and setfunctions, and 0-1 optimization, DOI link, author link
