On a composition of independence systems by circuit identification

AbstractThe 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(J), the convex hull of the incidence vectors of members of J