Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Extremal results on feedback arc sets in digraphs   A directed graph is oriented if it can be obtained by orienting the edges of
a simple, undirected graph. For an oriented graph $G$, let $\beta(G)$ denote
the size of a minimum feedback arc set, a smallest subset of edges whose
deletion leaves an acyclic subgraph. A simple consequence of a result of Berger
and Shor is that any oriented graph $G$ with $m$ edges satisfies $\beta(G) =
m/2 - \Omega(m^{3/4})$.
  We observe that if an oriented graph $G$ has a fixed forbidden subgraph $B$,
the upper bound of $\beta(G) = m/2 - \Omega(m^{3/4})$ is best possible as a
function of the number of edges if $B$ is not bipartite, but the exponent $3/4$
in the lower order term can be improved if $B$ is bipartite. We also show that
for every rational number $r$ between $3/4$ and $1$, there is a finite
collection of digraphs $\mathcal{B}$ such that every $\mathcal{B}$-free digraph
$G$ with $m$ edges satisfies $\beta(G) = m/2 - \Omega(m^r)$, and this bound is
best possible up to the implied constant factor. The proof uses a connection to
Tur\'an numbers and a result of Bukh and Conlon. Both of our upper bounds come
equipped with randomized linear-time algorithms that construct feedback arc
sets achieving those bounds. Finally, we give a characterization of quasirandom
directed graphs via minimum feedback arc sets.

25
The categories of this paper are: patt-sol
12
The categories of this paper are: nucl-th
18
The categories of this paper are: econ
4
The categories of this paper are: cond-mat
33
The categories of this paper are: plasm-ph
32
The categories of this paper are: atom-ph
37
The categories of this paper are: supr-con
9
The categories of this paper are: nlin
23
The categories of this paper are: solv-int
31
The categories of this paper are: ao-sci
19
The categories of this paper are: eess
5
The categories of this paper are: gr-qc
17
The categories of this paper are: q-fin
15
The categories of this paper are: nucl-ex
29
The categories of this paper are: funct-an
34
The categories of this paper are: chem-ph