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. 235259.
Abstract
Call an independence system (E,I) linearly relaxable, if the circuitinequalities x(C) <= C1 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, IMAGArtemis (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, IMAGArtemis (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 3cycles, resp. 2dicycles 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 circuitexchange 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.
Item Type:  Article 

Citations:  11 (Google Scholar)  8 (Web of Science) 
Uncontrolled Keywords:  convex hull incidence vectors independence systems independent set problem polytope 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
ZAIK Number:  zpr85013 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  09 Jan 2012 11:55 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/13 