General Information

Project Description

Graphs are becoming larger and larger every day, but the vertices of interest to us (called terminals) are potentially few. The paradigm of vertex sparsification explores the power and limit of compressing large graphs into smaller ones, while preserving important information, specifically cut and flow structures, with respect to terminals.
In this project, we will study a fundamental characterization problem (for cuts): Given a set T of terminals and a (2^T-2)-dimensional vector π whose coordinates are indexed by proper subsets of T, decide if there is a graph G that contains T, such that for all subsets S of T, π_S equals the value of the min-cut in G separating S from T\setminus S. We will also explore related questions concerning flow structures.

 

---

Weekly Log

---

---

Week 1:

My focus for this week was on understanding the foundational concepts and significant previous works in the study of mimicking networks and vertex sparsifiers in graph theory. This included an in-depth analysis of the characterization of multiterminal flow networks and the principles underlying the construction of mimicking networks, especially for networks with bounded treewidth. This involved reviewing seminal works by Hagerup, Katajainen, Nishimura, and Ragde, who introduced the concept of mimicking networks, and subsequent advancements by other researchers that improved the upper and lower bounds on the size of these networks. These studies provided a solid theoretical framework for the practical implications of constructing smaller, more efficient mimicking networks for large-scale graphs with multiple terminals​ .

Week 2:

More reading this week: specifically, I focused on the inequalities presented by Chaudhuri et al. for sets of terminals of order k=3,4,5. I studied how these inequalities can be applied to characterize terminal cuts in different network configurations. Additionally, I explored Zihan et al.'s generalization of Chaudhuri's findings using linear programming and Khan et al's findings about the convex cone(ality?) of the set of type vectors for a given k, which provided a broader framework for understanding terminal cuts in more complex graphs. I then made steps towards developing a system of inequalities for the 6 terminal case.

Week 3:

Completed the necessary background reading and leveraged Chaudhuri's work and the submodularity lemma toward developing a robust set of inequalities that can precisely describe the behavior of terminal cuts in graphs with 6 terminals. The focus was on ensuring that these inequalities are tight and accurately reflect the minimum cut values for various subsets of terminals for 31-dim type-vectors. Additionally, I developed an understanding of how to transform cut problems into dual distance problems by leveraging continuous optimization methods.