Algorithms for new objectives in graph partitioning and generalizations

In this thesis, we consider a class of graph partitioning problems: The input consists of a graph and a positive integer k, and the goal is to partition the vertex set of the graph into k parts while satisfying certain constraints in order to optimize an objective of interest. Varying constraints and objectives lead to a wide variety of graph partitioning problems. The classic Graph-MinCut and Graph-Min-(s,t)-Cut problems can be viewed as special cases of these problems. The study of these problems has led to novel algorithmic techniques and structural results as well as developed connections between graph theory and algorithms. Graph partitioning problems further generalize to hypergraph and submodular partitioning problems. In this thesis, we investigate new objectives in graph and hypergraph partitioning and long-standing objectives in submodular partitioning. We advance both algorithmic and structural aspects of the associated partitioning problems. We show hardness results for several graph partitioning problems under new objectives. We design approximation algorithms and fixed-parameter approximation scheme to solve these graph partitioning problems. We prove new structural results for graphs and hypergraphs that lead to polynomial-time algorithms to enumerate all optimum solutions of certain graph/hypergraph partitioning problems. We analyze the approximation factor of a classic algorithm for submodular partitioning based on principle partition sequence for monotone, symmetric, and posimodular submodular function families.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Wang, Weihang

Contributors dc:contributor

• Chandrasekaran, Karthekeyan
• Balogh, József
• Chekuri, Chandra
• Kostochka, Alexandr

• Graph Partitioning
• Hypergraph Partitioning
• Submodular Partitioning
• Algorithms
• Graph Theory

Statement dc:rights

• Copyright 2023 Weihang Wang

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

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