Clique-circulants and the stable set polytope of fuzzy circular interval graphs
Tóm tắt
In this paper, we give a complete and explicit description of the rank facets of the stable set polytope for a class of claw-free graphs, recently introduced by Chudnovsky and Seymour (Proceedings of the Bristish Combinatorial Conference, 2005), called fuzzy circular interval graphs. The result builds upon the characterization of minimal rank facets for claw-free graphs by Galluccio and Sassano (J. Combinatorial Theory 69:1–38, 2005) and upon the introduction of a superclass of circulant graphs that are called clique-circulants. The new class of graphs is invetigated in depth. We characterize which clique-circulants C are facet producing, i.e. are such that
$$\sum_{v\in V(C)} x_v\leq\alpha(C)$$
is a facet of STAB(C), thus extending a result of Trotter (Discrete Math. 12:373–388, 1975) for circulants. We show that a simple clique family inequality (Oriolo, Discrete Appl. Math. 132(2):185–201, 2004) may be associated with each clique-circulant
$$C\subseteq G$$
, when G is fuzzy circular interval. We show that these inequalities provide all the rank facets of STAB(G), if G is a fuzzy circular interval graph. Moreover we conjecture that, in this case, they also provide all the non-rank facets of STAB(G) and offer evidences for this conjecture.
Tài liệu tham khảo
Cheng E., de Vries S. (2001). Antiweb inequalities: strength and intractability. Congressus Numerantium 152: 5–19
Cheng E., Vries S. (2002). Antiweb inequalities: strength and intractability. Math. Program. 92(1): 153–175
Chudnovsky, M., Seymour, P.: The structure of claw-free graphs. In: Proceedings of the Bristish Combinatorial Conference, Durham (2005 to appear)
Chvatal V. (1975). On certain polytopes associated with graphs. J. Comb. Theory 18: 138–154
Edmonds J. (1965). Maximum matching and a polyhedron with (0,1) vertices. J. Res. Nat. Bur. Standards 69: 125–130
Edmonds J. (1965). Paths, trees and flowers. Can. J. Math. 17: 449–467
Eisenbrand, F., Oriolo, G., Stauffer, G., Ventura, P.: Circular one matrices and the stable set polytope of quasi-line graphs. In: Proceedings of IPCO, pp. 291–305 (2005)
Galluccio A., Sassano A. (1997). The rank facets of the stable set polytope for claw-free graphs. J. Comb. Theory 69: 1–38
Giles R., Trotter L.E. (1981). On stable set polyhedra for k (1,3)-free graphs. J. Comb. Theory 31: 313–326
Grötschel M., Lovász L., Schrijver A. (1988). Geometric Algorithms and Combinatorial Optimization. Springer, Heidelberg
Liebling T.M., Oriolo G., Spille G., Stauffer G. (2004). On the non-rank facets of the stable set polytope of claw-free graphs and circulant graphs. Math. Methods Oper. Res. 59: 25–35
Lovász L., Plummer M. (1986). Matching Theory. North Holland, Amsterdam
Maurras J. (1983). Convex hull of the edges of a graph and near bipartite graphs. Discrete Math. 46(3): 257–265
Minty G.J. (1980). On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory 28: 284–304
Nakamura D., Tamura A. (2001). A revision of minty’s algorithm for finding a maximum weighted stable set of a claw-free graph. J. Oper. Res. Soc. Jpn. 44(2): 194–2004
Oriolo G. (2004). Clique family inequalities for the stable set polytope for quasi-line graphs. Discrete Appl. Math. 132(3): 185–201
Padberg M. (1973). On the facial structure of set packing polyhedra. Math. Program. 5: 199–215
Pulleyblank, W., Shepherd, F.: Formulations for the stable set polytope of a claw-free graph. In: Rinaldi, L.W.G. (ed.) Proceedings Third IPCO conference, pp. 267–279 (1993)
Rebea, A.B.: Étude des stables dans les graphes quasi-adjoints. PhD thesis, Université de Grenoble (1981)
Sbihi N. (1980). Algorithme de recherche d’un stable de cardinalité maximum dans un graphe sans étoile. Discrete Math. 29: 53–76
Schrijver A. (2003). Combinatorial Optimization. Polyhedra and efficiency (3 volumes). Springer, Heidelberg
Shepherd F. (1995). Applying lehman’s theorems to packing problems. Math. Program. 71: 353–367
Trotter L. (1975). A class of facet producing graphs for vertex packing polyhedra. Discrete Math. 12: 373–388