Complexity of computing a v-reduced divisor in multigraphs
From Egres Open
Is there a polynomial algorithm for computing a [math]v_0[/math]-reduced divisor equivalent to a given divisor of an undirected multigraph?
Remarks
- For simple undirected graphs, there are polynomial algorithms to find a [math]v_0[/math]-reduced divisor equivalent to a given divisor, see Section 5 in [1].
- It is easy to check that a divisor [math]D[/math] is linearly equivalent to an effective divisor if and only if [math]D'(v_0) \geq 0[/math] in the unique [math]v_0[/math]-reduced divisor [math]D' \sim D[/math]. 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.
