Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs
From MaRDI portal
Publication:2355284
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.
Recommendations
- Minimal recurrent configurations of chip firing games and directed acyclic graphs
- On the complexity of the chip-firing reachability problem
- Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
- Addition of recurrent configurations in chip firing games: finding minimal recurrent configurations with Markov chains
- Chip-firing games on directed graphs
Cites work
- G-parking functions, acyclic orientations and spanning trees
- A family of bijections between \(G\)-parking functions and spanning trees
- Asymmetric Abelian sandpile models
- Chip firing and the Tutte polynomial
- Chip-firing and energy minimization on M-matrices
- Chip-Firing and Rotor-Routing on Directed Graphs
- Chip-firing and the critical group of a graph
- Chip-firing game and a partial Tutte polynomial for Eulerian digraphs
- Chip-firing games on directed graphs
- Chip-firing games on graphs
- Classes of lattices induced by chip firing (and sandpile) dynamics.
- Doubly stochastic matrices and dicycle covers and packings in Eulerian digraphs
- Feedback arc set in bipartite tournaments is NP-complete
- Finding a minimum feedback arc set in reducible flow graphs
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 5295462 (Why is no real title available?)
- scientific article; zbMATH DE number 139781 (Why is no real title available?)
- scientific article; zbMATH DE number 1268810 (Why is no real title available?)
- Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs
- Lattices generated by chip firing game models: criteria and recognition algorithms
- Minimal recurrent configurations of chip firing games and directed acyclic graphs
- On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
- Packing circuits in eulerian digraphs
- Packing directed circuits fractionally
- Primal-dual approximation algorithms for feedback problems in planar graphs
- Primer for the algebraic geometry of sandpiles
- Reducibility among combinatorial problems
- Self-organized critical state of sandpile automaton models
- The lattice structure of chip firing games and related models
- The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
- The sand-pile model and Tutte polynomials
- Trees, parking functions, syzygies, and deformations of monomial ideals
Cited in
(15)- Abelian sandpile model and Biggs-Merino polynomial for directed graphs
- Algorithmic aspects of rotor-routing and the notion of linear equivalence
- Rotor-routing reachability is easy, chip-firing reachability is hard
- Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph
- Chip-firing based methods in the Riemann-Roch theory of directed graphs
- Chip-firing game and a partial Tutte polynomial for Eulerian digraphs
- Minimal recurrent configurations of chip firing games and directed acyclic graphs
- Riemann-Roch theory for graph orientations
- Abelian logic gates
- On the complexity of the chip-firing reachability problem
- Beyond the worst case: semi-random complexity analysis of winner determination
- Computing the EHZ capacity is \(\operatorname{NP}\)-hard
- Minimizing the minimizers via alphabet reordering
- Don't let your breaks go to waste: the waste-performance-tradeoff-problem
- An equality for balanced digraphs
This page was built for publication: Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2355284)
