Efficient heuristics to compute minimal and stable feedback arc sets

Claudia Cavallaro (), Vincenzo Cutello () and Mario Pavone ()
Additional contact information
Claudia Cavallaro: University of Catania
Vincenzo Cutello: University of Catania
Mario Pavone: University of Catania

Journal of Combinatorial Optimization, 2024, vol. 48, issue 4, No 3, 24 pages

Abstract: Abstract Given a directed graph $$G=(V,A)$$ G = ( V , A ) , we tackle the Minimum Feedback Arc Set (MFAS) Problem by designing an efficient algorithm to search for minimal and stable Feedback Arc Sets, i.e. such that none of the arcs can be reintroduced in the graph without disrupting acyclicity and such that for each vertex the number of eliminated outgoing (resp. incoming) arcs is not bigger than the number of remaining incoming (resp. outgoing) arcs. Our algorithm has a good polynomial upper bound and can therefore be applied even on large graphs. We also introduce an algorithm to generate strongly connected graphs with a known upper bound on their feedback arc set, and on such graphs we test our algorithm.

Keywords: Minimal feedback arc set; Linear arrangement of vertices; Heuristics; Optimization problem; Experimental analysis (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01209-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:48:y:2024:i:4:d:10.1007_s10878-024-01209-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01209-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().