Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of Chip-firing game on directed graphs
pith:XAUS473K Add to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{XAUS473K}
Prints a linked pith:XAUS473K badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original abstract
In this paper we present further studies of recurrent configurations of Chip-firing games on Eulerian directed graphs (simple digraphs), a class on the way from undirected graphs to general directed graphs. A computational problem that arises naturally from this model is to find the minimum number of chips of a recurrent configuration, which we call the minimum recurrent configuration (MINREC) problem. We point out a close relationship between MINREC and the minimum feedback arc set (MINFAS) problem on Eulerian directed graphs, and prove that both problems are NP-hard.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.