Complexity of computing a v-reduced divisor in multigraphs

Is there a polynomial algorithm for computing a $$v_0$$ -reduced divisor equivalent to a given divisor of an undirected multigraph?

Remarks

• For simple undirected graphs, there are polynomial algorithms to find a $$v_0$$ -reduced divisor equivalent to a given divisor, see Section 5 in .
• It is easy to check that a divisor $$D$$ is linearly equivalent to an effective divisor if and only if $$D'(v_0) \geq 0$$ in the unique $$v_0$$ -reduced divisor $$D' \sim D$$ . As a corollary, by the duality between chip-firing games and graph divisor theory, a positive answer for this open question would imply a positive answer for the complexity of the halting problem for Eulerian multigraphs.