arXiv Analytics

Sign in

arXiv:1911.10912 [cs.DM]AbstractReferencesReviewsResources

Minimum-cost integer circulations in given homology classes

Ina Seidel, Stefan Weltge

Published 2019-11-25Version 1

Let $ D $ be a directed graph cellularly embedded on a surface together with costs and capacities on its arcs. Given any integer circulation in $ D $, we study the problem of finding a minimum-cost integer circulation in $ D $ that is homologous (over the integers) to the given circulation and respects the capacities. It has been recently shown that the stable set problem for graphs with bounded genus and bounded odd cycle packing number can be efficiently reduced to this problem, in which the surface is non-orientable. For orientable surfaces, polynomial-time algorithms have been obtained for different variants of this problem. We complement these findings by showing that the convex hull of feasible solutions has a very simple polyhedral description. In contrast, only little seems to be known about the case of non-orientable surfaces. We show that the problem is strongly NP-hard in this case. For surfaces of fixed genus, we obtain that the problem can be recast as an integer linear program with a coefficient matrix of bounded sub-determinants, which yields a polynomial-time algorithm for the projective plane. Moreover, we describe a pseudo-polynomial time algorithm for the case in which the surface has fixed genus and the circulation is only restricted to be non-negative.

Related articles: Most relevant | Search more
arXiv:1908.06300 [cs.DM] (Published 2019-08-17)
The stable set problem in graphs with bounded genus and bounded odd cycle packing number
arXiv:1406.6576 [cs.DM] (Published 2014-06-25, updated 2014-09-01)
Linear-Time Algorithm for Sliding Tokens on Trees
arXiv:1806.10697 [cs.DM] (Published 2018-06-27)
A new Integer Linear Program for the Steiner Tree Problem with Revenues, Budget and Hop Constraints