2007/10/16 by Volker Kaibel, Kaibel, Volker, Ruediger Stephan +1
Computer Science · Engineering · Mathematics · #90C27 #90C57 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems #VLSI and FPGA Design Techniques #math.CO #math.OC #msc:90C27 #msc:90C57
paper · pdf · doi:10.48550/arxiv.0710.3036
24 pages
arxiv created 2007/10/16 · openalex publication_date 2007/10/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a directed graph D = (N, A) and a sequence of positive integers 1 <= c1 < c2 < ... < cm <= |N|, we consider those path and cycle polytopes that are defined as the convex hulls of simple paths and cycles of D of cardinality cp 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.