Asymptotics of the Minimal Feedback Arc Set in Erdős-Rényi Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914635172544512 |
|---|---|
| author | Diamond, Harvey Kon, Mark Raphael, Louise |
| author_facet | Diamond, Harvey Kon, Mark Raphael, Louise |
| contents | Given a directed graph, the Minimal Feedback Arc Set (FAS) problem asks for a minimal set of arcs which, when removed, results in an acyclic graph. Equivalently, the FAS problem asks to find an ordering of the vertices that minimizes the number of feedback arcs. The FAS problem is considered an algorithmic problem of central importance in discrete mathematics. Our purpose in this paper is to consider the problem in the context of Erdős-Rényi random directed graphs, denoted $D(n,p)$, in which each possible directed arc is included with a fixed probability $p>0$. Our interest is the typical ratio of the number of feedforward arcs to the number of feedback arcs that are removed in the FAS problem. We show that as the number $n$ of vertices goes to infinity the probability that this ratio is greater than $1+ε$ for any fixed $ε> 0$ approaches zero. Similarly, letting $p$ go to zero as $n\rightarrow \infty$ this result remains true if $p>C\log{n}/n$ where $C$ depends on $ε$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_04187 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Asymptotics of the Minimal Feedback Arc Set in Erdős-Rényi Graphs Diamond, Harvey Kon, Mark Raphael, Louise Combinatorics 05C80 (Primary) 05C85, 68W40 (Secondary) Given a directed graph, the Minimal Feedback Arc Set (FAS) problem asks for a minimal set of arcs which, when removed, results in an acyclic graph. Equivalently, the FAS problem asks to find an ordering of the vertices that minimizes the number of feedback arcs. The FAS problem is considered an algorithmic problem of central importance in discrete mathematics. Our purpose in this paper is to consider the problem in the context of Erdős-Rényi random directed graphs, denoted $D(n,p)$, in which each possible directed arc is included with a fixed probability $p>0$. Our interest is the typical ratio of the number of feedforward arcs to the number of feedback arcs that are removed in the FAS problem. We show that as the number $n$ of vertices goes to infinity the probability that this ratio is greater than $1+ε$ for any fixed $ε> 0$ approaches zero. Similarly, letting $p$ go to zero as $n\rightarrow \infty$ this result remains true if $p>C\log{n}/n$ where $C$ depends on $ε$. |
| title | Asymptotics of the Minimal Feedback Arc Set in Erdős-Rényi Graphs |
| topic | Combinatorics 05C80 (Primary) 05C85, 68W40 (Secondary) |
| url | https://arxiv.org/abs/2401.04187 |