×

Clique family inequalities for the stable set polytope of quasi-line graphs. (English) Zbl 1052.90108

Summary: In one of fundamental works in combinatorial optimization, Edmonds gave a complete linear description of the matching polytope. Matchings in a graph are equivalent to stable sets in its line graph. Also the neighborhood of any vertex in a line graph partitions into two cliques: graphs with this latter property are called quasi-line graphs. Quasi-line graphs are a subclass of claw-free graphs, and as for claw-free graphs, there exists a polynomial algorithm for finding a maximum weighted stable set in such graphs, but we do not have a complete characterization of their Stable Set Polytope (SSP). In the paper, we introduce a class of inequalities, called clique-family inequalities, which are valid for the SSP of any graph and match the odd set inequalities defined by Edmonds for the matching polytope. This class of inequalities unifies all the known (non-trivial) facet inducing inequalities for the SSP of a quasi-line graph. We, therefore, conjecture that all the non-trivial facets of the SSP of a quasi-line graph belong to this class. We show that the conjecture is indeed correct for the subclasses of quasi-line graphs for which we have a complete description of the SSP. We discuss some approaches for solving the conjecture and a related problem.

MSC:

90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Ben Rebea, Etude des stables dans le graphs quasi-adjoints, Ph.D. Thesis, Univ. de Grenoble, 1981.; A. Ben Rebea, Etude des stables dans le graphs quasi-adjoints, Ph.D. Thesis, Univ. de Grenoble, 1981.
[2] Berge, C., Graphs and Hypergraphs (1973), Dunod: Dunod Paris · Zbl 0483.05029
[3] Bermond, J. C.; Meyer, J. C., Graphs representatif des aretes d’un multigraphe, J. Math. Pures. Appl., 52, 299-308 (1973) · Zbl 0219.05078
[4] Cao, D.; Nemhauser, G., Polyhedral characterization and perfection of line graphs, Discrete Appl. Math., 81, 141-154 (1998) · Zbl 0903.05041
[5] Chvátal, V., Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Math., 4, 305-337 (1973) · Zbl 0253.05131
[6] Chvátal, V., On certain polytopes associated with graphs, J. Combin. Theory Ser. B, 18, 138-154 (1975) · Zbl 0277.05139
[7] Dahl, G., Stable set polytopes for a class of circulant graphs, SIAM J. Optim., 9, 2, 493-503 (1999) · Zbl 0953.90051
[8] Edmonds, J., Maximum matching and a polyhedron with (0,1) vertices, J. Res. Nat. Bur. Standards, 69B, 125-130 (1965) · Zbl 0141.21802
[9] Edmonds, J.; Pulleyblank, W. R., Facets of 1-matching polyhedra, (Berge, C.; Ray-Chauduri, D., Hypergraph Seminar, Proceeding of the First Working Seminar (1974), Ohio State University: Ohio State University Springer, Berlin), 214-242 · Zbl 0317.05119
[10] Galluccio, A.; Sassano, A., The rank facets of the stable polytope for claw-free graphs, J. Combin. Theory Ser. B, 69, 1-38 (1997) · Zbl 0867.05034
[11] Giles, R.; Trotter, L. E., On stable set polyhedra for \(K_{1,3}\)-free graphs, J. Combin. Theory Ser. B, 31, 313-326 (1981) · Zbl 0494.05032
[12] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric Algorithms and Combinatorial Optimization (1988), Springer: Springer Berlin · Zbl 0634.05001
[13] Hemminger, R. L., Characterization of the line graph of a multigraph, Notices Amer. Math. Soc., 18, 934 (1971)
[14] Hsu, W.-L.; Nemhauser, G., Algorithms for minimum coverings by cliques and maximum cliques on claw-free perfect graphs, Discrete Math., 37, 181-191 (1981) · Zbl 0473.05049
[15] J. Kind, Mobilitätsmodelle für zellulare Mobilfunknetze: Produktformen und Blockierung, Ph.D. Thesis, RWTH Aachen, 2000.; J. Kind, Mobilitätsmodelle für zellulare Mobilfunknetze: Produktformen und Blockierung, Ph.D. Thesis, RWTH Aachen, 2000. · Zbl 0974.90004
[16] Krausz, J., Demonstration nouvelle d’un theoreme de Whitney sur le reseaux, Mat. Fix. Lapok, 50, 75-85 (1943) · Zbl 0061.41401
[17] Lai, H.-J.; Solthes, L., Line graphs and forbidden induced subgraphs, J. Combin. Theory Ser. B, 82, 38-55 (2001) · Zbl 1026.05093
[18] Lovász, L.; Plummer, M. D., Matching Theory (1986), North-Holland: North-Holland Amsterdam · Zbl 0618.05001
[19] Minty, G. J., On maximal independent sets of vertices in claw-free graphs, J. Combin. Theory Ser. B, 28, 284-304 (1980) · Zbl 0434.05043
[20] Nakamura, D.; Tamura, A., A revision of Minty’s algorithm for finding a maximum weighted stable set of a claw-free graph, J. Oper. Res. Soc. Japan, 44, 2, 194-204 (2001) · Zbl 1128.05318
[21] Padberg, M., On the facial structure of set packing polyhedra, Math. Programming, 5, 199-215 (1973) · Zbl 0272.90041
[22] Partasarathy, K. R.; Ravindra, G., The strong perfect graph conjecture is true for \(K_{1,3}\)-free graphs, J. Combin. Theory Ser. B, 21, 212-223 (1976) · Zbl 0297.05109
[23] W.R. Pulleyblank, F.B. Shepherd, Formulations for the stable set polytope of a claw-free graph, in: G. Rinaldi, L. Wolsey (Eds.), Proceedings of the Third IPCO Conference, Springer, Berlin, 1993, pp. 267-279.; W.R. Pulleyblank, F.B. Shepherd, Formulations for the stable set polytope of a claw-free graph, in: G. Rinaldi, L. Wolsey (Eds.), Proceedings of the Third IPCO Conference, Springer, Berlin, 1993, pp. 267-279. · Zbl 0945.68524
[24] Roussopoulos, N. D., A \(max{m, n}\) algorithm for determining the graph \(H\) from its line graph \(G\), J. Inform. Process. Lett., 2, 108-112 (1973) · Zbl 0274.05116
[25] N. Sbihi, Etude des Stables dans les Graphes sans Etoile, Ph.D. Thesis, Univ. de Grenoble, 1978.; N. Sbihi, Etude des Stables dans les Graphes sans Etoile, Ph.D. Thesis, Univ. de Grenoble, 1978.
[26] Sbihi, N., Algorithme de recherche d’un stable de cardinalite maximum dans un graphe sans etoile, Discrete Math., 29, 53-76 (1980) · Zbl 0444.05049
[27] Shepherd, F. B., Applying Lehman’s theorems to packing problems, Math. Programming, 71, 353-367 (1995) · Zbl 0863.05052
[28] Trotter, L. E., A class of facet producing graphs for vertex packing polyhedra, Discrete Math., 12, 373-388 (1975) · Zbl 0314.05111
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.