Editing Perfect graph (section)

==Matrices, polyhedra, and integer programming==
Perfect graphs are closely connected to the theory of [[linear programming]] and [[integer programming]]. Both linear programs and integer programs are expressed in [[canonical form]] as seeking a [[Vector (mathematics and physics)|vector]] <math>x</math> that maximizes a linear [[objective function]] <math>c\cdot x</math>, subject to the linear constraints <math>x\ge 0</math> and <math>Ax\le b</math>. Here, <math>A</math> is given as a [[Matrix (mathematics)|matrix]], and <math>b</math> and <math>c</math> are given as two vectors. Although linear programs and integer programs are specified in this same way, they differ in that, in a linear program, the solution vector <math>x</math> is allowed to have arbitrary [[real number]]s as its coefficients, whereas in an integer program these unknown coefficients must be integers. This makes a very big difference in the [[computational complexity]] of these problems: linear programming can be solved in [[polynomial time]], but integer programming is [[NP-hard]].{{r|crst-2003}}

When the same given values <math>A</math>, <math>b</math>, and <math>c</math> are used to define both a linear program and an integer program, they commonly have different optimal solutions. The linear program is called an [[Linear programming#Integral linear programs|integral linear program]] if an optimal solution to the integer program is also optimal for the linear program. (Otherwise, the ratio between the two solution values is called the [[integrality gap]], and is important in analyzing [[approximation algorithm]]s for the integer program.) Perfect graphs may be used to characterize the [[Logical matrix|(0, 1) matrices]] <math>A</math> (that is, matrices where all coefficients are 0 or 1) with the following property: if <math>b</math> is the [[all-ones vector]], then for all choices of <math>c</math> the resulting linear program is integral.{{r|crst-2003}}

As [[Václav Chvátal]] proved, every matrix <math>A</math> with this property is (up to removal of irrelevant "dominated" rows) the maximal clique versus vertex incidence matrix of a perfect graph. This matrix has a column for each vertex of the graph, and a row for each [[maximal clique]], with a coefficient that is one in the columns of vertices that belong to the clique and zero in the remaining columns. The integral linear programs encoded by this matrix seek the maximum-weight independent set of the given graph, with weights given by the vector <math>c</math>.{{r|crst-2003|chvatal-1975}}

For a matrix <math>A</math> defined in this way from a perfect graph, the vectors <math>x</math> satisfying the system of inequalities <math>x\ge 0</math>, <math>Ax\le 1</math> form an [[integral polytope]]. It is the [[convex hull]] of the [[indicator vector]]s of independent sets in the graph, with [[Facet (geometry)|facets]] corresponding to the maximal cliques in the graph. The perfect graphs are the only graphs for which the two polytopes defined in this way from independent sets and from maximal cliques coincide.{{r|chvatal-1975}}