Partitioning a bipartite graph into proportional factors
Let G=(V,E) be a bipartite graph, and [math]c_1,\dots c_k[/math] positive reals whose sum is 1. Can E always be partitioned into k parts [math]E_1,\dots,E_k,[/math] so that for every [math]v \in V[/math] and every [math]i \in \{1,\dots,k\}[/math] we have [math]\lfloor c_i d_E(v) \rfloor \leq d_{E_i}(v) \leq \lceil c_i d_E(v) \rceil[/math]?
Remarks
This question was asked by Correa and Goemans [1]. They proved a weaker bound [math]\lfloor c_i d_E(v) \rfloor-2 \leq d_{E_i}(v) \leq \lceil c_i d_E(v) \rceil+2[/math]. An alternative proof was found by Feige and Singh [2], who also showed that if only upper bounds or only lower bounds are considered, then [math]\pm 2[/math] can be replaced by [math]\pm 1[/math].
If [math]c_i=1/k[/math] for every i, then the statement follows from total unimodularity, see de Werra [3]. If k=2, then it follows from the theorem on Orientation with degree bounds. The case when G is regular is also easy, because we can partition E into regular subgraphs satisfying the condition.
References
- ↑ J.R. Correa, M.X. Goemans, Improved bounds on nonblocking 3-stage clos networks, SIAM Journal on Computing 37(3), 870-894 (2007), DOI link, author link
- ↑ U. Feige, M. Singh, Edge coloring and decompositions of weighted graphs, Algorithms-ESA 2008, DOI link, author link
- ↑ D. de Werra, Equitable colorations of graphs, Rev Fran Rech Oper. 5 (1971), 3-8. PDF link.
