@misc{Wagler, author = {Wagler, Annegret}, title = {Antiwebs are Rank-Perfect}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6742}, number = {02-07}, abstract = {\We discuss a nested collection of three superclasses of perfect graphs: near-perfect, rank-perfect, and weakly rank-perfect graphs. For that, we start with the description of the stable set polytope for perfect graphs and allow stepwise more general facets for the stable set polytopes of the graphs in each superclass. Membership in those three classes indicates how far a graph is away from being perfect. We investigate for webs and antiwebs to which of the three classes they belong. We provide a complete description of the facets of the stable set polytope for antiwebs (with help of a result due to Shepherd on near-bipartite graphs). The main result is that antiwebs are rankperfect.}, language = {en} } @misc{Wagler, author = {Wagler, Annegret}, title = {Rank-Perfect and Weakly Rank-Perfect Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6448}, number = {01-18}, abstract = {An edge of a perfect graph \$G\$ is critical if \$G-e\$ is imperfect. We would like to decide whether \$G - e\$ is still {\sl almost perfect} or already {\sl very imperfect}. Via relaxations of the stable set polytope of a graph, we define two superclasses of perfect graphs: rank-perfect and weakly rank-perfect graphs. Membership in those two classes indicates how far an imperfect graph is away from being perfect. We study the cases, when a critical edge is removed from the line graph of a bipartite graph or from the complement of such a graph.}, language = {en} } @misc{Wagler, author = {Wagler, Annegret}, title = {Relaxing Perfectness: Which Graphs are 'Almost' Perfect?}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6700}, number = {02-03}, abstract = {For all perfect graphs, the stable set polytope STAB\$(G)\$ coincides with the fractional stable set polytope QSTAB\$(G)\$, whereas STAB\$(G) \subset\$ QSTAB\$(G)\$ holds iff \$G\$ is imperfect. Padberg asked in the early seventies for ``almost'' perfect graphs. He characterized those graphs for which the difference between STAB\$(G)\$ and QSTAB\$(G)\$ is smallest possible. We develop this idea further and define three polytopes between STAB\$(G)\$ and QSTAB\$(G)\$ by allowing certain sets of cutting planes only to cut off all the fractional vertices of QSTAB\$(G)\$. The difference between QSTAB\$(G)\$ and the largest of the three polytopes coinciding with STAB\$(G)\$ gives some information on the stage of imperfectness of the graph~\$G\$. We obtain a nested collection of three superclasses of perfect graphs and survey which graphs are known to belong to one of those three superclasses. This answers the question: which graphs are ``almost'' perfect?}, language = {en} } @misc{KosterZymolka, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Polyhedral Investigations on Stable Multi-Sets}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7324}, number = {03-10}, abstract = {Stable multi-sets are an evident generalization of the well-known stable sets. As integer programs, they constitute a general structure which allows for a wide applicability of the results. Moreover, the study of stable multi-sets provides new insights to well-known properties of stable sets. In this paper, we continue our investigations started in [{\sl Koster and Zymolka 2002}] and present results of three types: on the relation to other combinatorial problems, on the polyhedral structure of the stable multi-set polytope, and on the computational impact of the polyhedral results. First of all, we embed stable multi-sets in a framework of generalized set packing problems and point out several relations. The second part discusses properties of the stable multi-set polytope. We show that the vertices of the linear relaxation are half integer and have a special structure. Moreover, we strengthen the conditions for cycle inequalities to be facet defining, show that the separation problem for these inequalities is polynomial time solvable, and discuss the impact of chords in cycles. The last result allows to interpret cliques as cycles with many chords. The paper is completed with a computational study to the practical importance of the cycle inequalities. The computations show that the performance of state-of-the-art integer programming solvers can be improved significantly by including these inequalities.}, language = {en} } @misc{PecherWagler, author = {Pecher, Arnaud and Wagler, Annegret}, title = {On Non-Rank Facets of Stable Set Polytopes of Webs with Clique Number Four}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7238}, number = {03-01}, abstract = {Graphs with circular symmetry, called webs, are relevant w.r.t. describing the stable set polytopes of two larger graph classes, quasi-line graphs and claw-free graphs. Providing a decent linear description of the stable set polytopes of claw-free graphs is a long-standing problem. However, even the problem of finding all facets of stable set polytopes of webs is open. So far, it is only known that stable set polytopes of webs with clique number \$\leq 3\$ have rank facets only while there are examples with clique number \$>4\$ having non-rank facets.}, language = {en} } @misc{PecherWagler, author = {P{\^e}cher, Arnaud and Wagler, Annegret}, title = {A construction for non-rank facets of stable set polytopes of webs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7437}, number = {03-21}, abstract = {Graphs with circular symmetry, called webs, are relevant for describing the stable set polytopes of two larger graph classes, quasi-line graphs [{\sl Giles and Trotter 1981, Oriolo 2001}] and claw-free graphs [{\sl Galluccio and Sassano 1997, Giles and Trotter 1981}]. Providing a decent linear description of the stable set polytopes of claw-free graphs is a long-standing problem [{\sl Gr{\"o}tschel, Lov\'asz, and Schrijver 1988}]. However, even the problem of finding all facets of stable set polytopes of webs is open. So far, it is only known that stable set polytopes of webs with clique number \$\leq 3\$ have rank facets only [{\sl Dahl 1999, Trotter 1975}] while there are examples with clique number \$\geq 4\$ having non-rank facets [{\sl e.g. Liebling et al. 2003, Oriolo 2001, P\^echer and Wagler 2003}]. In this paper, we provide a construction for non-rank facets of stable set polytopes of webs. We use this construction to prove, for several fixed values of \$\omega\$ including all odd values at least 5, that there are only finitely many webs with clique number \$\omega\$ whose stable set polytopes admit rank facets only.}, language = {en} } @misc{Wagler, author = {Wagler, Annegret}, title = {The Normal Graph Conjecture is true for Circulants}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7813}, number = {04-06}, abstract = {Normal graphs are defined in terms of cross-intersecting set families: a graph is normal if it admits a clique cover \$\cal Q\$ and a stable set cover \$\cal S\$ s.t.~every clique in \$\cal Q\$ intersects every stable set in \$\cal S\$. Normal graphs can be considered as closure of perfect graphs by means of co-normal products (K{\"o}rner 1973) and graph entropy (Czisz\'ar et al. 1990). Perfect graphs have been recently characterized as those graphs without odd holes and odd antiholes as induced subgraphs (Strong Perfect Graph Theorem, Chudnovsky et al. 2002). K{\"o}rner and de Simone observed that \$C_5\$, \$C_7\$, and \$\overline C_7\$ are minimal not normal and conjectured, as generalization of the Strong Perfect Graph Theorem, that every \$C_5\$, \$C_7\$, \$\overline C_7\$- free graph is normal (Normal Graph Conjecture, K{\"o}rner and de Simone 1999). We prove this conjecture for a first class of graphs that generalize both odd holes and odd antiholes, the circulants, by characterizing all the normal circulants.}, language = {en} } @misc{KosterWagler, author = {Koster, Arie M.C.A. and Wagler, Annegret}, title = {The extreme points of QSTAB(G) and its implications}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9249}, number = {06-30}, abstract = {Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations w.r.t different concepts. Perfect graphs are, e.g., characterized as precisely those graphs \$G\$ where the stable set polytope STAB\$(G)\$ coincides with the clique constraint stable set polytope QSTAB\$(G)\$. For all imperfect graphs STAB\$(G) \subset\$ QSTAB\$(G)\$ holds and, therefore, it is natural to measure imperfection in terms of the difference between STAB\$(G)\$ and QSTAB\$(G)\$. Several concepts have been developed in this direction, for instance the dilation ratio of STAB\$(G)\$ and QSTAB\$(G)\$ which is equivalent to the imperfection ratio imp\$(G)\$ of \$G\$. To determine imp\$(G)\$, both knowledge on the facets of STAB\$(G)\$ and the extreme points of QSTAB\$(G)\$ is required. The anti-blocking theory of polyhedra yields all {\em dominating} extreme points of QSTAB\$(G)\$, provided a complete description of the facets of STAB\$(\overline G)\$ is known. As this is typically not the case, we extend the result on anti-blocking polyhedra to a {\em complete} characterization of the extreme points of QSTAB\$(G)\$ by establishing a 1-1 correspondence to the facet-defining subgraphs of \$\overline G\$. We discuss several consequences, in particular, we give alternative proofs of several famous results.}, language = {en} } @misc{KosterWagler, author = {Koster, Arie M.C.A. and Wagler, Annegret}, title = {Comparing Imperfection Ratio and Imperfection Index for Graph Classes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8836}, number = {05-50}, abstract = {Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs \$G\$ where the stable set polytope \$STAB(G)\$ coincides with the fractional stable set polytope \$QSTAB(G)\$. For all imperfect graphs \$G\$ it holds that \$STAB(G) \subset QSTAB(G)\$. It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect; we discuss three different concepts, involving the facet set of \$STAB( G)\$, the disjunctive index of \$QSTAB(G)\$, and the dilation ratio of the two polytopes. Including only certain types of facets for \$STAB(G)\$, we obtain graphs that are in some sense close to perfect graphs, for example minimally immperfect graphs, and certain other classes of so-called rank-perfect graphs. The imperfection ratio has been introduced by (Gerke and McDiarmid, 2001) as the dilation ratio of \$STAB(G)\$ and \$QSTAB(G)\$, whereas (Aguilera et al., 2003) suggest to take the disjunctive index of \$Q STAB(G)\$ as the imperfection index of \$G\$. For both invariants there exist no general upper bounds, but there are bounds known for the imperfection ratio of several graph classes (Coulonges et al. 2005, Gerke and McDiarmid, 2001). Outgoing from a graph-theoretical interpretation of the imperfection index, we conclude that the imperfection index is NP-hard to compute and we prove that there exists no upper bound on the imperfect ion index for those graph classes with a known bounded imperfection ratio. Comparing the two invariants on those classes, it seems that the imperfection index measures imperfection much more roughly than the imperfection ratio; therefoe, discuss possible directions for refinements.}, language = {en} } @misc{KosterZymolka, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Stable Multi-Sets}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6047}, number = {00-36}, abstract = {In this paper we introduce a generalization of stable sets: stable multi-sets. A stable multi-set is an assignment of integers to the vertices of a graph, such that specified bounds on vertices and edges are not exceeded. In case all vertex and edge bounds equal one, stable multi-sets are equivalent to stable sets. For the stable multi-set problem, we derive reduction rules and study the associated polytope. We state necessary and sufficient conditions for the extreme points of the linear relaxation to be integer. These conditions generalize the conditions for the stable set polytope. Moreover, the classes of odd cycle and clique inequalities for stable sets are generalized to stable multi-sets and conditions for them to be facet defining are determined. The study of stable multi-sets is initiated by optimization problems in the field of telecommunication networks. Stable multi-sets emerge as an important substructure in the design of optical networks.}, language = {en} }