Minimum-cost integer circulations in given homology classes
share
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.
READ FULL TEXT