Tight integral duality gap in the Chinese postman problem (Q1196167): Difference between revisions

Let \(G=(V,E)\) be a graph and let \(w\) be a weight function \(w:E\to Z^ +\). Let \(T\subseteq V\) be an even subset of the vertices of \(G\). A \(T\)- cut is an edge-cutset of the graph which divides \(T\) into two odd sets. A \(T\)-join is a minimal subset of edges that meets every \(T\)-cut (a generalization of solutions to the Chinese Postman problem). The main theorem of this paper gives a tight upper bound on the difference between the minimum weight \(T\)-join and the maximum weight integral packing of \(T\)-cuts. This difference is called the \((T\)-join) integral duality gap. Let \(\tau_ w\) be the minimum weight of a \(T\)-join, and let \(\nu_ w\) be the maximum weight of an integral packing of \(T\)-cuts. If \(F\) is a non-empty minimum weight \(T\)-join, and \(n_ F\) is the number of components of \(F\), then we prove that \(\tau_ w-\nu_ w\leq n_ F- 1\). This result unifies and generalizes Fulkerson's result for \(| T|=2\) and Seymour's result for \(| T|=4\). For a certain integral multicommodity flow problem in the plane, which was recently proved to be \(NP\)-complete, the above result gives a solution such that for every commodity the flow is less than the demand by at most one unit.