Speaker: Karthik Chandrasekaran (UIUC)
Title: Approximate version of Woodall’s conjecture
Abstract:
In a digraph, a dicut is a partition of the vertices into two non-empty parts such that all arcs crossing the partition do so in one direction. A dijoin is a subset of arcs that contains at least one arc from every dicut. By definition, the maximum number of arc disjoint dijoins is at most the minimum size of a dicut. Woodall (1976) conjectured that these two quantities are equal. In this talk, we will prove an approximate version of Woodall’s conjecture: max number of arc disjoint dijoins is at least (1/6) min size of a dicut. The talk will be based on a recent paper due to Cornuejols, Liu, and Ravi: https://arxiv.org/pdf/2311.04337.pdf.
