On Sparsest Cut and Conductance in Directed Polymatroidal Networks

We consider algorithms and spectral bounds for sparsest cut and conductance in directed polymatrodal networks. This is motivated by recent work on submodular hypergraphs \cite{Yoshida19,LiM18,ChenOT23,Veldt23} and previous work on multicommodity flows and cuts in polymatrodial networks \cite{Chekuri...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-10
Main Authors: Chekuri, Chandra, Anand, Louis
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Graph theory
Networks
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider algorithms and spectral bounds for sparsest cut and conductance in directed polymatrodal networks. This is motivated by recent work on submodular hypergraphs \cite{Yoshida19,LiM18,ChenOT23,Veldt23} and previous work on multicommodity flows and cuts in polymatrodial networks \cite{ChekuriKRV15}. We obtain three results. First, we obtain an \(O(\sqrt{\log n})\)-approximation for sparsest cut and point out how this generalizes the result in \cite{ChenOT23}. Second, we consider the symmetric version of conductance and obtain an \(O(\sqrt{OPT \log r})\) approximation where \(r\) is the maximum degree and we point out how this generalizes previous work on vertex expansion in graphs. Third, we prove a non-constructive Cheeger like inequality that generalizes previous work on hypergraphs. We provide a unified treatment via line-embeddings which were shown to be effective for submodular cuts in \cite{ChekuriKRV15}.
ISSN:2331-8422