Asymptotic Lower Bounds for the Feedback Arc Set Problem in Random Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912755840188416 |
|---|---|
| author | Diamond, Harvey Kon, Mark Raphael, Louise |
| author_facet | Diamond, Harvey Kon, Mark Raphael, Louise |
| contents | Given a directed graph, the Minimum Feedback Arc Set (FAS) problem asks for a minimum (size) set of arcs in a directed graph, which, when removed, results in an acyclic graph. In a seminal paper, Berger and Shor [1], in 1990, developed initial upper bounds for the FAS problem in general directed graphs. Here we find asymptotic \textit{lower bounds} for the FAS problem in a class of random, oriented, directed graphs derived from the Erdős-Rényi model $G(n,M)$, with n vertices and M (undirected) edges, the latter randomly chosen. Each edge is then randomly given a direction to form our directed graph. We show that
$$Pr\left(\textbf{Y}^* \le M \left( \frac{1}{2} -\sqrt{\frac{\log n}{Δ_{av}}}\right)\right)$$ approaches zero exponentially in $n$, with $\textbf{Y}^*$ the (random) size of the minimum feedback arc set and $Δ_{av}=2M/n$ the average vertex degree. Lower bounds for random tournaments, a special case, were obtained by Spencer [12] and de la Vega [13] and these are discussed. In comparing the bound above to averaged experimental FAS data on related random graphs developed by K. Hanauer [7] we find that the approximation $\textbf{Y}^*_{av} \approx M\left( \frac{1}{2} -\frac{1}{2}\sqrt{\frac{\log n}{Δ_{av}}}\right)$ lies remarkably close graphically to the algorithmically computed average size $\textbf{Y}^*_{av}$ of minimum feedback arc sets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_16443 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Asymptotic Lower Bounds for the Feedback Arc Set Problem in Random Graphs Diamond, Harvey Kon, Mark Raphael, Louise Combinatorics 05C80 (Primary) 05C85, 68W40 (Secondary) Given a directed graph, the Minimum Feedback Arc Set (FAS) problem asks for a minimum (size) set of arcs in a directed graph, which, when removed, results in an acyclic graph. In a seminal paper, Berger and Shor [1], in 1990, developed initial upper bounds for the FAS problem in general directed graphs. Here we find asymptotic \textit{lower bounds} for the FAS problem in a class of random, oriented, directed graphs derived from the Erdős-Rényi model $G(n,M)$, with n vertices and M (undirected) edges, the latter randomly chosen. Each edge is then randomly given a direction to form our directed graph. We show that $$Pr\left(\textbf{Y}^* \le M \left( \frac{1}{2} -\sqrt{\frac{\log n}{Δ_{av}}}\right)\right)$$ approaches zero exponentially in $n$, with $\textbf{Y}^*$ the (random) size of the minimum feedback arc set and $Δ_{av}=2M/n$ the average vertex degree. Lower bounds for random tournaments, a special case, were obtained by Spencer [12] and de la Vega [13] and these are discussed. In comparing the bound above to averaged experimental FAS data on related random graphs developed by K. Hanauer [7] we find that the approximation $\textbf{Y}^*_{av} \approx M\left( \frac{1}{2} -\frac{1}{2}\sqrt{\frac{\log n}{Δ_{av}}}\right)$ lies remarkably close graphically to the algorithmically computed average size $\textbf{Y}^*_{av}$ of minimum feedback arc sets. |
| title | Asymptotic Lower Bounds for the Feedback Arc Set Problem in Random Graphs |
| topic | Combinatorics 05C80 (Primary) 05C85, 68W40 (Secondary) |
| url | https://arxiv.org/abs/2409.16443 |