Algorithmic aspects of connectivity and density in graphs and hypergraphs

Kulkarni, Shubhang M

Permalink

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

Description

Title

Algorithmic aspects of connectivity and density in graphs and hypergraphs

Author(s)

Kulkarni, Shubhang M

Issue Date

2025-04-24

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
• Bérczi, Kristóf

Department of Study

Siebel School Comp & Data Sci

Discipline

Computer Science

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• 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

Abstract

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.

Graduation Semester

2025-05

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

Copyright 2025 Shubhang Kulkarni

Owning Collections