Cuts and partitions: solving, counting, and enumerating

The problem of finding a global minimum cut in an undirected graph is fundamental to combinatorial optimization. It has numerous applications including network reliability, clustering, and the Travelling Salesman Problem. In addition to this computational problem, structural and enumerative aspects of minimum cuts are also foundational to representation and algorithmic results. The number of constant-approximate global minimum cuts in a connected graph is polynomial in the number of vertices. This structural result has applications in constructing cut sparsifiers, sketching and streaming algorithms, and approximation algorithms for TSP. In this thesis we consider various generalizations of the minimum cut problem. We focus on solving these variants and on counting and enumerating optimum solutions. Our results include: - A new and faster algorithm for computing connectivity in hypergraphs, - The first deterministic polynomial time algorithm for enumerating hypergraph min-$k$-cut-sets, - The first polynomial bound on the number of Multiobjective Min-cuts for a constant number of cost functions as well as the first polynomial time algorithm for enumerating all of them, and - Inapproximability results for representing symmetric submodular functions using hypergraph cut functions.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Beideman, Calvin

Contributors dc:contributor

• Chandrasekaran, Karthekeyan
• Chekuri, Chandra
• Har-Peled, Sariel
• Mukhopadhyay, Sagnik

• Min-cut
• Connectivity
• Hypergraphs
• Min-k-cut
• Combinatorial Optimization
• Multicriteria Optimization

Statement dc:rights

• Copyright 2023 Calvin Beideman

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/121433

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F121433