Zurück zu den Preprints des Jahres 2007


2007-33

On cardinality constrained cycle and path polytopes

by Kaibel, V., Stephan, R..


Series: 2007-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