Abstract
A 0, 1 matrixA isnear-perfect if the integer hull of the polyhedron {x⩾0: Ax⩽\(\bar 1\)} can be obtained by adding one extra (rank) constraint. We show that in general, such matrices arise as the cliquenode incidence matrices of graphs. We give a colouring-like characterization of the corresponding class of near-perfect graphs which shows that one need only check integrality of a certain linear program for each 0, 1, 2-valued objective function. This in contrast with perfect matrices where it is sufficient to check 0, 1-valued objective functions. We also make the following conjecture: a graph is near-perfect if and only if sequentially lifting any rank inequality associated with a minimally imperfect graph results in the rank inequality for the whole graph. We show that the conjecture is implied by the Strong Perfect Graph Conjecture. (It is also shown to hold for graphs with no stable set of size eleven.) Our results are used to strengthen (and give a new proof of) a theorem of Padberg. This results in a new characterization of minimally imperfect graphs: a graph is minimally imperfect if and only if both the graph and its complement are near-perfect.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
S. Baum and L.E. Trotter Jr., “Integer rounding for polymatroid and branching optimization problems,”SIAM Journal on Algebraic and Discrete Methods 2 (1981) 416–425.
C. Berge, “Farbung von Graphen, deren samtliche bzw. deren ugerade Kreise starr sind,”Wissenschaftliche Zeitschrift, Martin Luther Universität Halle-Wittenberg (1961) 114.
R.G. Bland, H.C. Huang and L.E. Trotter Jr., Graphical properties related to minimal imperfection.Discrete Mathematics 27 (1979) 11–22.
J.A. Bondy and U.S.R. Murty,Graph Theory and Applications (McMillan, London, 1976).
K. Cameron, Polyhedral and algorithmic ramifications of antichains, Ph.D. Thesis, University of Waterloo (1982).
V. Chvátal, On certain polytopes associated with graphs,Journal on Combinatorial Theory B 18 (1975) 138–154.
V. Chvátal, On the strong perfect graph conjecture,Journal on Combinatorial Theory B 20 (1976) 139–141.
V. Chvátal, R.L. Graham, A.F. Perold and S.H. Whitesides, Combinatorial designs related to the strong perfect graph conjecture,Discrete Mathematics 26 (1979) 83–92.
V. Chvátal, An equivalent version of the Strong Perfect Graph Conjecture,Annals of Discrete Mathematics 21 (1984) 193–195.
W.J. Cook, personal communication (1987).
W.H. Cunningham, Polyhedra for composed independence systems, in: A. Bachem, M. Grötschel and B. Korte, eds., Bonn Workshop on Combinatorial Optimization,Annals of Discrete Mathematics 16 (1982) 57–67.
D.R. Fulkerson, “On the perfect graph theorem,” in: T.C. Hu and S. Robinson, eds.,Mathematical Programming (Academic Press, New York, 1973) 69–76.
M. Grötschel, L. Lovász and A. Schrijver, The ellipsoid algorithm and its consequences in combinatorial optimization,Combinatorica 1 (1981) 169–197.
L. Lovász, A characterization of perfect graphs,Journal on Combinatorial Theory B 13 (1972) 95–98.
L. Lovász, Normal hypergraphs and the perfect graph conjecture,Discrete Mathematics 2 (1972) 253–267.
L. Lovász, “Perfect Graphs,” in:Graph Theory, 2 (Academic Press Inc., London, 1983) 55–87.
M.W. Padberg, On the facial structure of set packing polyhedra,Mathematical Programming 5 (1973) 199–215.
M.W. Padberg, Perfect zero-one matrices,Mathematical Programming 6 (1974) 180–196.
M.W. Padberg, Almost integral polyhedra related to certain combinatorial optimization problems,Linear Algebra and its Applications 15 (1976) 339–342.
W.R. Pulleyblank, “Polyhedral combinatorics,” in: G.L Nemhauser, A.H.G. Rinnoy and M.J. Todd, eds.,Optimization, Handbooks in Operations Research and Management Science, Vol. 1 (North-Holland, Amsterdam, 1989).
B. Reed, private communication (1990).
A. Schrijver,Theory of Linear and Integer Programming (Wiley, New York, 1986).
F.B. Shepherd, Near-perfection and stable set polyhedra, PhD Thesis, University of Waterloo (1990).
A. Tucker, Critical perfect graphs and perfect 3-chromatic graphs,Journal on Combinatorial Theory B 23 (1977) 143–149.
Author information
Authors and Affiliations
Additional information
The research has partially been done when the author visited Mathematic Centrum, CWI, Amsterdam, The Netherlands.
Rights and permissions
About this article
Cite this article
Shepherd, F.B. Near-perfect matrices. Mathematical Programming 64, 295–323 (1994). https://doi.org/10.1007/BF01582578
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582578