Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of chip-firing game on directed graphs

DOI10.1007/S00026-015-0266-9zbMath1331.68095arXiv1303.3708OpenAlexW2963123511MaRDI QIDQ2355284

Kévin Perrot, Trung van Pham

Publication date: 22 July 2015

Published in: Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1303.3708

zbMATH Keywords

complexitychip-firing gamecritical configurationEulerian digraphfeedback arc setrecurrent configurationsandpile model

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (8)

Chip-firing game and a partial Tutte polynomial for Eulerian digraphs ⋮ Abelian sandpile model and Biggs-Merino polynomial for directed graphs ⋮ Chip-firing based methods in the Riemann-Roch theory of directed graphs ⋮ Algorithmic aspects of rotor-routing and the notion of linear equivalence ⋮ Beyond the worst case: semi-random complexity analysis of winner determination ⋮ Riemann-Roch theory for graph orientations ⋮ Abelian Logic Gates ⋮ Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chip-firing game and a partial Tutte polynomial for Eulerian digraphs
• Chip-firing games on directed graphs
• Chip-firing games on graphs
• Feedback arc set in bipartite tournaments is NP-complete
• \(G\)-parking functions, acyclic orientations and spanning trees
• Asymmetric Abelian sandpile models
• Chip-firing and the critical group of a graph
• Chip firing and the Tutte polynomial
• The sand-pile model and Tutte polynomials
• Classes of lattices induced by chip firing (and sandpile) dynamics.
• A family of bijections between \(G\)-parking functions and spanning trees
• Doubly stochastic matrices and dicycle covers and packings in Eulerian digraphs
• Packing directed circuits fractionally
• Packing circuits in eulerian digraphs
• Lattices generated by chip firing game models: criteria and recognition algorithms
• Chip-firing and energy minimization on M-matrices
• Primer for the algebraic geometry of sandpiles
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Chip-Firing and Rotor-Routing on Directed Graphs
• Finding a minimum feedback arc set in reducible flow graphs
• Self-organized critical state of sandpile automaton models
• Primal-dual approximation algorithms for feedback problems in planar graphs
• Trees, parking functions, syzygies, and deformations of monomial ideals
• Reducibility among Combinatorial Problems
• Large Feedback Arc Sets, High Minimum Degree Subgraphs, and Long Cycles in Eulerian Digraphs
• The lattice structure of chip firing games and related models

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