On a composition of independence systems by circuits identification
Euler, Reinhardt; Mahjoub, Ali Ridha (1991), On a composition of independence systems by circuits identification, Journal of Combinatorial Theory , Series B, 53, 2, p. 235-259. http://dx.doi.org/10.1016/0095-8956(91)90076-V
TypeArticle accepté pour publication ou publié
Journal nameJournal of Combinatorial Theory , Series B
MetadataShow full item record
Abstract (EN)The composition of general bipartite subgraph respectively 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 recent papers. We generalize this kind of composition within the framework of independence systems having a certain exchange property with respect to one of their circuits, and extend it to the case of independence systems associated with K3-covers of a graph. We discuss its implications for associated polyhedra, totally dual integral linear systems describing these as well as related optimization problems. As a special result we obtain that the K3-cover problem is polynomially solvable in graphs not contractible to K5−e. Particular attention is also given to independence systems, which are linearly relaxable (with respect to their circuits), i.e., for which the circuit inequalities x(C)≤|C|−1 together with the trivial inequalities O≤xe≤1 are sufficient to describe P(Image ), the convex hull of the incidence vectors of members of Image .
Subjects / KeywordsPolyhedra; Graph
Showing items related by title and author.