Half-integral flows in a planar graph with four holes (Q1842657): Difference between revisions

Let \(G= (V, E)\) be a planar, undirected graph; \(I\), \(J\), \(K\), \(O\) four of its faces (called holes in \(G\)) and \(s_1,\dots, s_r, t_1,\dots, t_r\in V\) such that each pair \((r_i, t_i)\) belongs to the boundary of some hole and such that \((V, E\cup \{(s_1, t_1),\dots, (s_r, t_r)\})\) is eulerian. The author proves that if the multiflow problem in \(G\) with unit demand on the values of flow from \(s_i\) to \(t_i\) \((i= 1,\dots, r)\) has a solution, then it has a half-integral solution as well, i.e., there exist paths \(P^1_1,P^2_1,\dots, P^1_r, P^2_r\) in \(G\) such that each \(P^j_i\) connects \(s_i\) and \(t_i\) and each edge of \(G\) is covered at most twice by these paths.