Algorithmic aspects of connectivity and density in graphs and hypergraphs

This thesis investigates algorithmic problems in combinatorial optimization centered around modifying a given network—via deletion, augmentation, or reconfiguration—to achieve tar- get connectivity or density bounds. We study associated optimization problems on graphs, hypergraphs, and submodular functions. Our main contributions are: • Hypergraph Splitting-off. We introduce a splitting-off operation in hypergraphs and prove an analogue of Mader’s theorem: in every hypergraph, a vertex can be re- moved via splitting-off while preserving all pairwise edge-connectivities. We give a strongly polynomial-time algorithm in weighted hypergraphs, with applications including a constructive characterization of k-hyperedge-connected hypergraphs and an alternate proof of an approximate min-max relation for Steiner rooted-connected orientations. Our framework extends to symmetric skew-supermodular functions. • Hypergraph Connectivity Augmentation. We study augmentation to achieve target pairwise connectivities subject to vertex degree constraints. We give a strongly polynomial time algorithm, improving prior pseudo-polynomial results. Our method extends to generating near-uniform hypergraphs, simultaneously augmenting two hypergraphs, and to covering skew-supermodular functions. Applications include strongly polyno- mial time algorithms for node-to-area and mixed-hypergraph connectivity augmentation. • Graph Density Deletion. We study vertex deletion on graphs where the goal is to delete a minimum-cost subset of vertices so that the densest subgraph has density at most a given target ρ. When ρ ≤ 1, this problem is 2-approximable. In contrast, we show logarithmic hardness of approximation for all fixed integers ρ > 1. We also study a generalization to monotone supermodular functions, show approximation equivalence to Submodular Set Cover, and design bicriteria approximation algorithms. • Feedback Vertex Set (FVS) and Pseudoforest Deletion Set (PFDS). We undertake a polyhedral study of FVS and PFDS, special cases of graph density deletion for appropriate ρ ≤ 1. Both problems are 2-approximable, but lacked polynomial-time solvable LP relaxations with matching approximation guarantees. We establish the first such LP formulations for both problems. For PFDS, we resolve a question of Bodlaender, Ono and Otachi by exhibiting an extreme point property of an associated polytope.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Kulkarni, Shubhang M

Contributors dc:contributor

• Chandrasekaran, Karthekeyan
• Chekuri, Chandra
• Har-Peled, Sariel
• Bérczi, Kristóf

• Combinatorial Optimization
• Graph Optimization
• Hypergraph Optimization
• Submodular Functions
• Polyhedral Combinatorics
• Approximation Algorithms
• Linear Programming
• Randomized Algorithms
• Connectivity Augmentation
• Densest Subgraph
• Hypergraph Splitting-Off
• Feedback Vertex Set

Statement dc:rights

• Copyright 2025 Shubhang Kulkarni

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

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