Theory Seminar: Annie Zeng, "Packing Steiner Forests in Graphs."
- Sponsor
- Theory and Algorithms Research Area
- Speaker
- Annie Zeng
- Contact
- Makrand Sinha
- msinha@illinois.edu
- Originating Calendar
- Siebel School Speakers Calendar
Abstract: We consider the problem of packing edge-disjoint Steiner forests in a graph. The input consists of a multi-graph G=(V,E) and a collection of h vertex subsets S={S1,S2,…,Sh}. A Steiner forest for S, also called an S-forest, is a forest of G in which each Si is connected. In the case where h=1, this is the Steiner Tree packing problem. Kriesell's conjecture postulates that 2k-edge-connectivity of S1 is sufficient to find k edge-disjoint S1-trees. Lau showed that 24k-edge-connectivity suffices for the Steiner Tree packing problem, which was improved to 6.5k by West and Wu and 5k+4 by Devos, McDonald and Pivotto.
In his thesis, Lau asserts that for the Steiner Forest problem, if each Si is 30k-edge-connected in G, then there exist k edge-disjoint S-forests. However, Lau's proof relies on an intermediate theorem called the Extension Theorem, which has a gap in the proof, as evidenced by a counterexample we found to this theorem. In this talk, I will explain the mistake in Lau's proof, and how we fixed it to obtain the result that 36k-edge-connectivity of each Si suffices to pack k S-forests.
This work was done as my undergraduate thesis, which was supervised by Chandra Chekuri.