Cuts and partitions: solving, counting, and enumerating

Beideman, Calvin

Permalink

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

Description

Title

Cuts and partitions: solving, counting, and enumerating

Author(s)

Beideman, Calvin

Issue Date

2023-06-27

Director of Research (if dissertation) or Advisor (if thesis)

Chandrasekaran, Karthekeyan

Doctoral Committee Chair(s)

Chandrasekaran, Karthekeyan

Committee Member(s)

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

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

Abstract

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.

Graduation Semester

2023-08

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Calvin Beideman

Owning Collections