ﻻ يوجد ملخص باللغة العربية
Given a capacitated undirected graph $G=(V,E)$ with a set of terminals $K subset V$, 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)} choose {lfloor {{(k-1)}/2} rfloor}}$) 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^{frac{k-1}{2}}$. We also exhibit improved constructions of mimicking networks for trees and graphs of bounded tree-width.
We give query-efficient algorithms for the global min-cut and the s-t cut problem in unweighted, undirected graphs. Our oracle model is inspired by the submodular function minimization problem: on query $S subset V$, the oracle returns the size of th
Given a graph $G=(V,E)$, capacities $w(e)$ on edges, and a subset of terminals $mathcal{T} subseteq V: |mathcal{T}| = k$, a mimicking network for $(G,mathcal{T})$ is a graph $(H,w)$ that contains copies of $mathcal{T}$ and preserves the value of mini
We present the first work-optimal polylogarithmic-depth parallel algorithm for the minimum cut problem on non-sparse graphs. For $mgeq n^{1+epsilon}$ for any constant $epsilon>0$, our algorithm requires $O(m log n)$ work and $O(log^3 n)$ depth and su
We give an algorithm to find a mincut in an $n$-vertex, $m$-edge weighted directed graph using $tilde O(sqrt{n})$ calls to any maxflow subroutine. Using state of the art maxflow algorithms, this yields a directed mincut algorithm that runs in $tilde
We address counting and optimization variants of multicriteria global min-cut and size-constrained min-$k$-cut in hypergraphs. 1. For an $r$-rank $n$-vertex hypergraph endowed with $t$ hyperedge-cost functions, we show that the number of multiobjec