Feedback Arc Sets and Girth in Digraphs

Опубликовано 6 сентября 2016, 16:41

Given a directed graph G with girth at least m+1 (and no parallel edges), let b(G) denote the size of the smallest subset X of the edges of G so that G \ X has no directed cycles, and let c(G) be the number of non-edges (unordered pairs of vertices with no edge between them). Prior joint work with Maria Chudnovsky and Paul Seymour showed that when m = 3, b(G) is at most c(G), and we conjectured b(G) is actually at most c(G)/2. Can one say anything stronger if m is greater than three? In this talk, I will discuss a new conjecture giving a ratio between b(G) and c(G), namely b(G) is at most 2c(G) / (m^2-m-1), for all m which are at least three. The talk will also cover two new results in this direction: that b(G) is at most c(G)/3 when m is at least four, and for circular interval graphs, a generalization of previous methods which gives a new bound for all m.