Cover Image

Asymptotics of the Minimal Feedback Arc Set in Erdős-Rényi Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Diamond, Harvey, Kon, Mark, Raphael, Louise
Format:	Preprint
Published:	2024
Subjects:	Combinatorics 05C80 (Primary) 05C85, 68W40 (Secondary)
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Asymptotic Lower Bounds for the Feedback Arc Set Problem in Random Graphs
by: Diamond, Harvey, et al.
Published: (2024)

A $5/4$-Approximation for Two-Edge Connectivity
by: Bosch-Calvo, Miguel, et al.
Published: (2024)

On Conjectures concerning the Labeled Coupon Collector Problem
by: Barak-Pelleg, Dina, et al.
Published: (2025)

Regular bipartite decompositions of pseudorandom graphs
by: Ferber, Asaf, et al.
Published: (2024)

Zero-free regions of partition functions with applications to algorithms and graph limits
by: Regts, Guus
Published: (2015)

Finding cliques and dense subgraphs using edge queries
by: Csóka, Endre, et al.
Published: (2023)

Improved Approximation Algorithms for Path and Forest Augmentation via a Novel Relaxation
by: Hommelsheim, Felix
Published: (2025)

A $4/3$ Approximation for $2$-Vertex-Connectivity
by: Bosch-Calvo, Miguel, et al.
Published: (2023)

Minimal obstructions to $C_5$-coloring in hereditary graph classes
by: Goedgebeur, Jan, et al.
Published: (2024)

Young domination on Hamming rectangles
by: Gravner, Janko, et al.
Published: (2025)

Algorithmic releases on the spanning trees of suitable graphs
by: Imbesi, Maurizio, et al.
Published: (2017)

Vector encoding of phylogenetic trees by ordered leaf attachment
by: Richman, Harry, et al.
Published: (2025)

Large deviations of the greedy independent set algorithm on sparse random graphs
by: Kolesnik, Brett
Published: (2020)

Towards a dichotomy for the switch list homomorphism problem for signed graphs
by: Kim, Hyobin, et al.
Published: (2021)

Improved lower bounds for the maximum order of an induced acyclic subgraph
by: Asgarli, Shamil, et al.
Published: (2025)

Recolouring Homomorphisms to triangle-free reflexive graphs
by: Lee, Jae-baek, et al.
Published: (2021)

Cup Stacking in Graphs
by: Fay, Paul, et al.
Published: (2023)

The spread of fire on a random multigraph
by: Goldschmidt, Christina, et al.
Published: (2017)

Limiting Behavior of Resistances in Triangular Graphs
by: Hendel, Russell Jay
Published: (2021)

The process of fluctuations of the giant component of an Erdős-Rényi graph
by: Enriquez, Nathanaël, et al.
Published: (2023)

Asymptotic size of the Karp-Sipser Core in Configuration Model
by: Chatterjee, Arnab, et al.
Published: (2025)

5-Coloring Planar Graphs with a Color Class of Order at Most $|V|/6$
by: Inoue, Yuta, et al.
Published: (2025)

Cofinality of Regular Tournaments
by: Hatem, Omar, et al.
Published: (2026)

Slavic Techniques for Hat Guessing Algorithms
by: McInnis, I. M. J.
Published: (2025)

Tight complexity bounds for diagram commutativity verification
by: Malko, Artem, et al.
Published: (2025)

The Antisymmetric Line Graph
by: Bal, Hartosh Singh
Published: (2026)

A greedy heuristic for graph burning
by: García-Díaz, Jesús, et al.
Published: (2024)

Asymptotic normality for general subtree counts in conditioned Galton--Watson trees
by: Rakotoniaina, Fameno, et al.
Published: (2026)

A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor
by: Milanič, Martin, et al.
Published: (2024)

A note on limits of sequences of binary trees
by: Grübel, Rudolf
Published: (2023)

Coloring graphs as complete graph invariants
by: Asgarli, Shamil, et al.
Published: (2025)

Tree independence number V. Walls and claws
by: Chudnovsky, Maria, et al.
Published: (2025)

4-cop-win graphs have at least 19 vertices
by: Turcotte, Jérémie, et al.
Published: (2020)

Oriented Colouring Graphs of Bounded Degree and Degeneracy
by: Clow, Alexander, et al.
Published: (2023)

Lower Bounds for the Pfaffian Number of Graphs
by: Junchaya, Enrique, et al.
Published: (2026)

On the joint embedding property for cographs and trees
by: Carter, Daniel
Published: (2024)

A new bound in Majority Dynamics on Random Graphs
by: Jaffe, Sean
Published: (2025)

An Analysis of Optimizer Choice on Energy Efficiency and Performance in Neural Network Training
by: Almog, Tom
Published: (2025)

Approximating inter-point distances in directed Bernoulli graphs
by: Barbour, A. D., et al.
Published: (2026)

Shortest two disjoint paths in conservative graphs
by: Schlotter, Ildikó
Published: (2023)