On mimicking networks representing minimum terminal cuts

DOI10.1016/J.IPL.2014.02.011MaRDI QIDQ2446595zbMATH OpenOpenAlexFDO

Authors Arindam Khan, Prasad Raghavendra

Publication date 17 April 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.6371

zbMATH Keywords

analysis of algorithmsapproximation algorithmscombinatorial problemsgraph algorithms

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Abstract: Given a capacitated undirected graph $G=(V,E)$ with a set of terminals $KsubsetV$, a mimicking network is a smaller graph $H=(V_H,E_H)$ that exactly preserves all the minimum cuts between the terminals. Specifically, the vertex set of the sparsifier $V_H$ contains the set of terminals $K$ and for every bipartition $U,K-U$ of the terminals $K$, the size of the minimum cut separating $U$ from $K-U$ in $G$ is exactly equal to the size of the minimum cut separating $U$ from $K-U$ in $H$. This notion of a mimicking network was introduced by Hagerup, Katajainen, Nishimura and Ragde (1995) who also exhibited a mimicking network of size $2^{2^k}$ for every graph with $k$ terminals. The best known lower bound on the size of a mimicking network is linear in the number of terminals. More precisely, the best known lower bound is $k+1$ for graphs with $k$ terminals (Chaudhuri et al. 2000). In this work, we improve both the upper and lower bounds reducing the doubly-exponential gap between them to a single-exponential gap. Specifically, we obtain the following upper and lower bounds on mimicking networks: 1) Given a graph $G$, we exhibit a construction of mimicking network with at most $(|K|-1)$'th Dedekind number ($approx{2}^{(k-1)chooselfloor(k-1)/2floor}$) of vertices (independent of size of $V$). Furthermore, we show that the construction is optimal among all {it restricted mimicking networks} -- a natural class of mimicking networks that are obtained by clustering vertices together. 2) There exists graphs with $k$ terminals that have no mimicking network of size smaller than $2^{frack-12}$. We also exhibit improved constructions of mimicking networks for trees and graphs of bounded tree-width.

Recommendations

• Mimicking Networks and Succinct Representations of Terminal Cuts
• Computing mimicking networks
• An exponential lower bound for cut sparsifiers in planar graphs
• An exponential lower bound for cut sparsifiers in planar graphs
• Refined vertex sparsifiers of planar graphs

Cites work

• All-Pairs Min-Cut in Sparse Networks
• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
• Computing mimicking networks
• Delta-Wye Transformations and the Efficient Reduction of Two-Terminal Planar Graphs
• Extensions and limits to vertex sparsification
• Flows in one-crossing-minor-free graphs
• scientific article; zbMATH DE number 910923 (Why is no real title available?)
• Mimicking Networks and Succinct Representations of Terminal Cuts
• On vertex sparsifiers with Steiner nodes

Cited in

(15)

• An exponential lower bound for cut sparsifiers in planar graphs
• Vertex sparsification in trees
• Tight Bounds for Gomory-Hu-like Cut Counting
• NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs
• Improved guarantees for vertex sparsification in planar graphs
• An exponential lower bound for cut sparsifiers in planar graphs
• Refined vertex sparsifiers of planar graphs
• Improved guarantees for vertex sparsification in planar graphs
• Mimicking Networks and Succinct Representations of Terminal Cuts
• Quasipolynomial Multicut-mimicking Networks and Kernels for Multiway Cut Problems
• On quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems
• Vertex sparsifiers for hyperedge connectivity
• The Even-Path problem in directed single-crossing-minor-free graphs
• Nearly-tight bounds for flow sparsifiers in quasi-bipartite graphs
• Cut-preserving vertex sparsifiers for planar and quasi-bipartite graphs

This page was built for publication: On mimicking networks representing minimum terminal cuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2446595)