论文标题
反馈弧集中的极端结果
Extremal results on feedback arc sets in digraphs
论文作者
论文摘要
如果可以通过定向简单，无向图的边缘来获得有向图。对于定向的图$ g $，令$β（g）$表示最小反馈弧集的大小，这是最小的边缘子集，其删除留下了一个无环子图。 Berger和Shor结果的一个简单结果是，任何带有$ M $ edges的面向图形$ g $都满足$β（g）= m/2 -ω（m^{3/4}）$。 我们观察到，如果一个定向的图$ G $具有固定的禁止子图$ b $，则最大可能是$β（g）= m/2 -ω（m^{3/4}）$的上限，如果$ b $不是bipartite，则最好作为边缘数量的函数，但如果下级$ 3/4 $可以改善$ 3/4 $，则可以改善$ 3/4 $。我们还表明，对于每个有理数的$ r $，$ 3/4 $和$ 1 $之间，都有有限的Digraphs $ \ Mathcal {B} $的收藏，使每个$ \ Mathcal {B} $ - 免费的Digraph $ G $带有$ M $ EDGES $ M $ EDGES $β（g）= m/2------------（m^r）$ bunst and bount and bount and bount and bount and bount and bount and bount and bount and bount and bount and bount and bount。证明使用了与Turán数字的连接，以及Bukh和Conlon的结果。我们的两个上限都配备了随机线性时间算法，这些算法构建反馈弧设置可实现这些边界。最后，我们通过最小反馈弧集对quasirandom有向图的表征进行表征。
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 $β(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 $β(G) = m/2 - Ω(m^{3/4})$. We observe that if an oriented graph $G$ has a fixed forbidden subgraph $B$, the upper bound of $β(G) = m/2 - Ω(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 $β(G) = m/2 - Ω(m^r)$, and this bound is best possible up to the implied constant factor. The proof uses a connection to Turán 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.
