Complexity of the chip-firing reachability problem for general digraphs

From Egres Open
Jump to: navigation, search


Is the chip-firing reachability problem co-NP-hard for general digraphs?


Remarks

The question of the complexity of the chip-firing reachability problem appeared in [1], where the problem was conjectured to be hard.

The chip-firing reachability problem is known to be in co-NP [2].

References

  1. ↑ A. Björner, L. Lovász, Chip-firing games on directed graphs, DOI link, Author link
  2. ↑ B. Hujter, V. Kiss, L. Tóthmérész, On the complexity of the chip-firing reachability problem, EGRES Technical Report
Retrieved from "http://lemon.cs.elte.hu/egres/internals/index.php5?title=Complexity_of_the_chip-firing_reachability_problem_for_general_digraphs&oldid=2390"