2
$\begingroup$

Given an edge-weighted multigraph $G=(V,E)$ with a positive, rational weight function $(w(e): e \in E)$, the weighted fractional edge coloring problem (WFECP) is to compute ($\min 1^T x$ subject to $Ax \ge w, x \ge 0$), where $A$ is the edge-matching incidence matrix of $G$.

Recently (2019) it was shown that WFECP can be solved in strongly polynomial time. Their algorithm runs in time $O(mn+n^5 \ell^2 \log(n^2\ell))$, where $n, m$ and $\ell$ denote $|V|, |E|$ and number of edges in the underlying graph, respectively. My question is: what exactly are the main new contributions of the above paper for the WFECP problem, compared to the previous literature?

From the complexity standpoint, an earlier paper (1988) already gives a $O(n^5)$ strongly polynomial time algorithm for WFECP. Is the new algorithm more efficient, or better in some other way, than the previous ones?

Also, it's not clear why multigraphs need to be considered - it seems to me that all parallel edges can be replaced with a single edge whose weight is the total of the weights of the parallel edges, so that the multigraphs problem doesn't seem to be strictly more general or difficult than the problem for simple graphs.

I do understand the recent paper makes significant new contributions (such as solving the open problem of computing, in strongly polynomial time, the maximum edge density $\Gamma_w(G)$ in an odd subset of the vertex set). But I was just wondering what the new contributions of this recent paper are regarding the WFECP problem.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.