07-33
On cardinality constrained cycle and path polytopes
Preprint series: 07-33, Preprints
- MSC:
- 90C27 Combinatorial optimization
- 90C10 Integer programming
Abstract: Given a directed graph D = (N, A) and a sequence of positive integers 1 <= c_1 < c_2 < ... < c_m <= |N|, we consider those path and cycle polytopes that are defined as the convex hulls of simple paths and cycles of D of cardinality c_p for some p, respectively. We present integer characterizations of these polytopes by facet defining linear inequalities for which the separation problem can be solved in polynomial time. These inequalities can simply be transformed into inequalities that characterize the integer points of the undirected counterparts of cardinality constrained path and cycle polytopes. Beyond we investigate some further inequalities, in particular inequalities that are specific to odd/even paths and cycles.
Keywords: cycle, path, cardinality restriction, polytope
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.