Skip to main content
Top

2022 | Book

Feedback Arc Set

A History of the Problem and Algorithms

share
SHARE
insite
SEARCH

About this book

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.

Table of Contents

Frontmatter

Overview of Findings

Frontmatter
Chapter 1. Feedback Arc Set
Abstract
The chapter deals with the problem and the name, origin of the FAS, and its description. Hardness is argued, including in the extended version. Various often used, and some not that often, instances of the problem are discussed upon. The chapter ends with the dual of the problem, namely Maximum Acyclic Subgraph, and the strong link with the Feedback Vertex Set problem, including the Forcing problem as well. Last section deals with vast practical relevance of the FAS problem.
Robert Kudelić

Feedback Arc Set and Algorithms Thereof

Frontmatter
Chapter 2. Introductory Remarks
Abstract
The chapter consists of introductory remarks that are necessary to speak out before the reader goes into reading about the research and the algorithms. A few words are given about methodology, cited literature and history of the problem itself with regards to coverage in the book. After these are dealt with, the book continues with the next chapter that deals with the FAS problem literature.
Robert Kudelić
Chapter 3. Papers and Algorithms
Abstract
The chapter presents what would in a nutshell be a traveling through time with the problem of Feedback Arc Set. The review goes from the first paper, jumping through a number of periods and research results, ending with recent achievements, including a quantum computing algorithm. This chapter, more than any other part of the book, provides a historical compendium of techniques in Computer Science.
Robert Kudelić

Complexity Informed

Frontmatter
Chapter 4. Having the Right Tool
Abstract
After dealing with everything important Feedback Arc Set in the first chapter of the book, and after presenting a number of algorithms, giving both breadth and depth, in the second chapter, in this chapter one will find a miniature guide for algorithmically solving Feedback Arc Set. This will be achieved by focusing on both special, and more general cases. Algorithms suggested are disparate in efficiency, approximability, and practical relevance.
Robert Kudelić
Metadata
Title
Feedback Arc Set
Author
Robert Kudelić
Copyright Year
2022
Electronic ISBN
978-3-031-10515-9
Print ISBN
978-3-031-10514-2
DOI
https://doi.org/10.1007/978-3-031-10515-9

Premium Partner