On a Composition of Independence Systems by Circuit Identification

Euler, Reinhardt and Mahjoub, Ali R. (1991) On a Composition of Independence Systems by Circuit Identification.
Published in: Journal of combinatorial theory : Series B Vol. 53 (2). pp. 235-259.


Call an independence system (E,I) linearly relaxable, if the circuit-inequalities x(C) <= |C|-1 together with the constraints 0 <= xe <= 1 for all e in E are sufficient to define P(I), the convex hull of the incedence vectors of members of I. Examples are given by independence systems associated with bipartite subgraphs of graphs not contractible to K5, cf. J. Fonlupt et al. [Compositions of graphs and the bipartite subgraph polytope, Tech.Rep. 459, IMAG-Artemis (1984)], or with acyclic subdigraphs of digraphs obtainable from graphs not contractible to K3,3, cf. F. Barahona and A.R. Mahjoub [Compositions in the acyclic subdigraph polytope, Tech.Rep. 500, IMAG-Artemis (1985)]. Further classes are stable set independence systems of bipartite graphs and, as we are going to show here, a generalization of these within the framework of balanced matrices. The composition of bipartite subgraph resp. acyclic subdigraph independence systems and in particular of their associated polyhedra by the identification of a pair of 3-cycles, resp. 2-dicycles together with its implications for an algorithmic treatment has been the central subject of the above mentioned two references. We generalize this kind of composition within the framework of independence systems satisfying a special circuit-exchange property and discuss its implications for the associated polyhedra, totally dual integral linear systems describing these as well as relaxed optimization problems. Special attention is given to the linearly relaxable such independence systems.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr85-013
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 09 Jan 2012 11:55
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/13