William Lin

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2024-119

May 17, 2024

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2024/EECS-2024-119.pdf

We discuss a linear programming formulation of expander flows as applied to the sparsest cut problem. The sparsest cut problem looks to find the cut that minimizes the expansion: the ratio of edges to the number of vertices on the smaller side, and is NP-hard. A key idea to getting approximate certificates for this is expander flows, which embeds an expander of known expansion in the graph. This provides a lower bound on the number of edges in cuts in the original graph as significant flow must pass between the sets when embedding an expander. By proving that expander flows are approximately feasible in terms of the original graphs expansion, one can either certify the original graph expands or find a non- expanding cut. Originally, the embeddings required multicommodity flow methods but the cut matching paradigm allowed the use of a few calls to a single commodity flow algorithms to find sparse cuts.

In this thesis, we make the observation that good solutions to the expander flow linear program exist that only use a sequence of maximum single commodity flows. We note that the implementation remains difficult due to the lack of existence of a sufficiently good separation oracle for the expander flow linear program when using the ellipsoid algorithm, and briefly describe previous approaches that do this with worse bounds.

Another observation we make using this setup is that for graphs with small cuts, the approximation can be improved to only depend on the size of the cut rather than a function of the number of vertices.

Advisors: Satish Rao

---

BibTeX citation:

@mastersthesis{Lin:EECS-2024-119,
    Author= {Lin, William},
    Title= {Expander Flows and Sparsest Cut Linear Programming},
    School= {EECS Department, University of California, Berkeley},
    Year= {2024},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2024/EECS-2024-119.html},
    Number= {UCB/EECS-2024-119},
    Abstract= {We discuss a linear programming formulation of expander flows as applied to the sparsest cut problem. The sparsest cut problem looks to find the cut that minimizes the expansion: the ratio of edges to the number of vertices on the smaller side, and is NP-hard. A key idea to getting approximate certificates for this is expander flows, which embeds an expander of known expansion in the graph. This provides a lower bound on the number of edges in cuts in the original graph as significant flow must pass between the sets when embedding an expander. By proving that expander flows are approximately feasible in terms of the original graphs expansion, one can either certify the original graph expands or find a non- expanding cut. Originally, the embeddings required multicommodity flow methods but the cut matching paradigm allowed the use of a few calls to a single commodity flow algorithms to find sparse cuts.

In this thesis, we make the observation that good solutions to the expander flow linear program exist that only use a sequence of maximum single commodity flows. We note that the implementation remains difficult due to the lack of existence of a sufficiently good separation oracle for the expander flow linear program when using the ellipsoid algorithm, and briefly describe previous approaches that do this with worse bounds.

Another observation we make using this setup is that for graphs with small cuts, the approximation can be improved to only depend on the size of the cut rather than a function of the number of vertices.},
}

EndNote citation:

%0 Thesis
%A Lin, William 
%T Expander Flows and Sparsest Cut Linear Programming
%I EECS Department, University of California, Berkeley
%D 2024
%8 May 17
%@ UCB/EECS-2024-119
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2024/EECS-2024-119.html
%F Lin:EECS-2024-119