The main aim of the book is to give a review of all relevant information regarding a well-known and important problem of Feedback Arc Set (FAS). This review naturally also includes a history of the problem, as well as specific algorithms. To this point such a work does not exist: There are sources where one can find incomplete and perhaps untrustworthy information. With this book, information about FAS can be found easily in one place: formulation, description, theoretical background, applications, algorithms etc. Such a compendium will be of help to people involved in research, but also to people that want to quickly acquaint themselves with the problem and need reliable information. Thus research, professional work and learning can proceed in a more streamlined and faster way.
Author(s): Robert Kudelić
Series: SpringerBriefs in Computer Science
Publisher: Springer
Year: 2022
Language: English
Pages: 133
City: Cham
Foreword
Preface
Contents
Part I Overview of Findings
1 Feedback Arc Set
1.1 The Problem and the Name
1.2 Origin
1.3 Description
1.4 Linear Programming Formulation
1.5 Inherently Hard to Solve
1.6 Hard to Approximate by Extension
1.7 Feedback Arc Set and Tournament
1.8 Feedback Arc Set and Eulerian Digraph
1.9 Subset Feedback Arc Set
1.10 Graph Bipartization
1.11 Maximum Acyclic Subgraph—Dual
1.12 Feedback Arc and Vertex Set
1.13 The Forcing Problem
1.14 Practical Relevance
References
Part II Feedback Arc Set and Algorithms Thereof
2 Introductory Remarks
2.1 Methodology
2.2 Cited Literature
2.3 About the History
3 Papers and Algorithms
3.1 On Directed Graphs and Integer Programs
3.2 Minimum Feedback Arc Sets for a Directed Graph
3.3 Minimum Feedback Arc and Vertex Sets of a Directed Graph
3.4 A Heuristic Algorithm for the Minimum Feedback Arc Set
3.5 A Branch and Bound Algorithm for the Acyclic Subgraph
3.6 Acyclic Subdigraphs and Linear Orderings
3.7 Finding a Minimum Feedback Arc Set in Reducible FlowGraphs
3.8 A Contraction Algorithm for Finding Small Cycle Cut-sets
3.9 Approximation Algorithms for the Maximum Acyclic Subgraph
3.10 Exact and Heuristic Algorithms for the Weighted FAS
3.11 Approximation for Concurrent Flow with Uniform Capacities
3.12 Method for Finding a Minimal Feedback Arc Set in Digraphs
3.13 A Fast and Effective Heuristic for the Feedback Arc Set
3.14 Approximations for the Maximum Acyclic Subgraph
3.15 A Heuristic for the Feedback Arc Set
3.16 New Results on the Computation of Median Orders
3.17 Approx. Minimum Feedback Sets and Multi-Cuts in Digraphs
3.18 A Fast and Effective Algorithm for the Feedback Arc Set
3.19 Computing Approximate Solutions of FSPs using GRASP
3.20 A New Rounding Procedure for the Assignment Problem
3.21 On Enumerating All Minimal Solutions of Feedback Problems
3.22 Combinatorial Algorithms for Feedback Problems in Digraphs
3.23 A Contraction Algorithm for Finding Minimal Feedback Sets
3.24 Exact Exp. Algorithms for Vertex Bipartization and Others
3.25 Parameterized Algorithms for Feedback Set Problems
3.26 Branch and Bound Algo. for Linear Ordering in Tournaments
3.27 How to Rank with Fewer Errors
3.28 Feedback Arc Set in Bipartite Tournaments
3.29 Aggregating Inconsistent Information: Ranking and Clustering
3.30 Minimum Feedback Arc Sets in Rotator Graphs
3.31 Ranking Tournaments: Local Search and a New Algorithm
3.32 Deterministic Pivoting for Constrained Ranking and Clustering
3.33 Faster FAST (Feedback Arc Set in Tournaments)
3.34 Fixed-Parameter Tractability Results for FSPs in Tournaments
3.35 Fast Local Search Algorithm for Weighted FAS in Tournaments
3.36 Faster Algorithms for Feedback Arc Set Tournament
3.37 Sorting Heuristics for the Feedback Arc Set
3.38 Linear Programming Based Approximation Algorithmsfor FSPs
3.39 An Efficient Genetic Algorithm for the Feedback Set Problems
3.40 Packing Feedback Arc Sets in Reducible Flow Graphs
3.41 Algorithms and Kernels in Generalizations of Tournaments
3.42 An Exact Method for the Minimum Feedback Arc Set
3.43 Monte-Carlo Randomized Algorithm for Minimum FAS
3.44 Optimal Disruption of Complex Networks
3.45 Efficient Computation of Feedback Arc Set at Web-Scale
3.46 Optimal Segmentation of Digraph and the Minimum FAS
3.47 Quantum Speedups for Exp-Time Dynamic Prg. Algorithms
3.48 Ant Inspired Monte-Carlo Algorithm for Minimum FAS
3.49 Tight Localizations of Feedback Sets
References
Part III Complexity Informed
4 Having the Right Tool
4.1 Tackling With Feedback Arc Set
4.2 Tractability in Special Cases
References
