Blocking flows were introduced by Dinic (Soviet Math Doklady 11: 1277–1280, 1970) to speed up the computation of maximum network flows. They have been used in algorithms for problems such as maximum ...cardinality matching of bipartite graphs Hopcroft and Karp (SIAM J Comput 2(4), 225–231, 1973) and general graphs Micali and Vazirani (in: Proceedings of the 21st Annual Symposium on Foundations of Computer Science, 17–27, 1980), maximum weight matching of general graphs Gabow and Tarjan (J ACM 38(4), 815–853, 1991), and many others. The blocking algorithm of Gabow and Tarjan (1991) for matching is based on depth-first search. We extend the depth-first search approach to find
f
-factors of general multigraphs. Here
f
is an arbitrary integral-valued function on vertices, an
f
-
matching
is a subgraph where every vertex
x
has degree
≤
f
(
x
)
, an
f
-
factor
has equality in every degree bound. A set of
blocking trails
for an
f
-matching
M
is a maximal collection
A
of edge-disjoint augmenting trails such that
M
⨁
A
∈
A
A
is a valid
f
-matching. Blocking trails are needed in efficient algorithms for maximum cardinality
f
-matching Huang and Pettie (Algorithmica 84(7): 1952–1992, 2022), maximum weight
f
-factors/matchings by scaling Duan et al. (In: Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Vol. 168 of LIPIcs, 41:1-41:17, 2020; Gabow (A weight-scaling algorithm for
f
-factors of multigraphs.
arXiv:2010.01102
, 2020), and approximate maximum weight
f
-factors and
f
-edge covers Huang and Pettie (2022). Since these algorithms find many sets of blocking trails, the time to find blocking trails is a dominant factor in the running time. Our blocking trail algorithm runs in linear time
O
(
m
). In independent work and using a different approach, Huang and Pettie (2022) present a blocking trails algorithm using time
O
(
m
α
(
m
,
n
)
)
. As examples of the time bounds for the above applications, an approximate maximum weight
f
-factor is found in time
O
(
m
α
(
m
,
n
)
)
using Huang and Pettie (2022), and our algorithm eliminates the factor
α
(
m
,
n
)
. Similarly a maximum weight
f
-factor is found in time
O
(
Φ
log
Φ
m
α
(
m
,
n
)
log
(
Φ
W
)
)
using Huang and Pettie (2022) , (
Φ
=
∑
v
∈
V
f
(
v
)
,
W
the maximum edge weight) and our algorithm eliminates the
α
(
m
,
n
)
factor, making the time within a factor
log
Φ
of the bound for bipartite multigraphs. The technical difficulty for this work stems from the fact that a fixed vertex can occur many times in a given search. This does not occur in ordinary matching or in algorithms for maximum cardinality or maximum weight
f
-matching. These multiple occurrences can create a new variant of blossom, the “skew blossom”. Also they can make blossoms become “incomplete”, i.e., partially processed yet still relevant in future searches.
The challenge for graph matching algorithms is to extend known time bounds for bipartite graphs to general graphs. We discuss combinatorial algorithms for finding a maximum weight
f
-factor on an ...arbitrary multigraph, for given integral weights of magnitude at most
W
. (An
f
-factor is a subgraph whose degree function is the given function
f
:
V
→
N
.) For simple bipartite graphs the best-known time bound for combinatorial algorithms is
O
(
n
2
/
3
m
log
n
W
)
Gabow and Tarjan, SIAM J Comput 18(5):1013–1036, 1989;
n
and
m
are respectively the number of vertices and edges. A recent algorithm of Duan et al. in: Proc. of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 2020 for
f
-factors of simple general graphs comes within logarithmic factors of this bound,
O
~
(
n
2
/
3
m
log
W
)
. The best-known bound for bipartite multigraphs is
O
(
Φ
m
log
Φ
W
)
(
Φ
≤
m
is the size of the
f
-factor,
Φ
=
∑
v
∈
V
f
(
v
)
/
2
). This bound is more general than the restriction to simple graphs, and is even superior on “small” simple graphs, i.e.,
Φ
=
o
(
n
4
/
3
)
. We present an algorithm that comes within a
log
Φ
factor of this bound, i.e.,
O
(
Φ
log
Φ
m
log
Φ
W
)
. The algorithm is a direct generalization of the algorithm of Gabow and Tarjan J ACM 38(4):815–853, 1991 for the special case of ordinary matching (
f
≡
1
). We present that algorithm first. Our analysis is a simplified and more concrete version of Gabow and Tarjan J ACM 38(4):815–853, 1991 and has independent interest. Furthermore the algorithm and analysis are both incorporated, without modification, into the
f
-factor algorithm. To extend these ideas to
f
-factors, the first step is “expanding” edges (i.e., replacing an edge by a length 3 alternating path). Duan et al. in: Proc. of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 2020 uses a one-time expansion of the entire graph. In contrast, our algorithm keeps the graph small by only expanding selected edges (edges incident to blossoms, in “
I
(
B
) sets”). Expanded edges get “compressed” back to their source when no longer needed. Expansion necessitates using an alternate graph model for blossoms (we call them “e-blossoms”). Compression requires coordinating e-blossoms with standard blossoms.
Consider a directed or an undirected graph with integral edge weights from the set -W, W, that does not contain negative weight cycles. In this article, we introduce a general framework for solving ...problems on such graphs using matrix multiplication. The framework is based on the usage of Baur-Strassen's theorem and of Strojohann's determinant algorithm. It allows us to give new and simple solutions to the following problems: Finding Shortest Cycles. We give a simple Õ(Wnω) time algorithm for finding shortest cycles in undirected and directed graphs. For directed graphs (and undirected graphs with nonnegative weights), this matches the time bounds obtained in 2011 by Roditty and Williams. On the other hand, no algorithm working in Õ(Wn ω) time was previously known for undirected graphs with negative weights. Furthermore, our algorithm for a given directed or undirected graph detects whether it contains a negative weight cycle within the same running time. Computing Diameter and Radius. We give a simple Õ(Wnω) time algorithm for computing a diameter and radius of an undirected or directed graphs. To the best of our knowledge, no algorithm with this running time was known for undirected graphs with negative weights. Finding Minimum-Weight Perfect Matchings. We present an Õ(Wnω) time algorithm for finding minimum-weight perfect matchings in undirected graphs. This resolves an open problem posted by Sankowski 2009 who presented such an algorithm but only in the case of bipartite graphs. These three problems that are solved in the full generality demonstrate the utility of this framework. Hence, we believe that it can find applications for solving larger spectra of related problems. As an illustrative example, we apply it to the problem of computing a set of vertices that lie on cycles of length at most t, for some given t. We give a simple Õ(Wnω) time algorithm for this problem that improves over the Õ(Wnωt) time algorithm given by Yuster in 2011. Besides giving this flexible framework, the other main contribution of this article is the development of a novel combinatorial interpretation of the dual solution for the minimum-weight perfect matching problem. Despite the long history of the matching problem, such a combinatorial interpretation was not known previously. This result sheds a new light on the problem, as there exist many structural theorems about unweighted matchings, but almost no results that could cope with the weighted case.
Various instances of the minimal-set poset (minset-poset for short) have been proposed in the literature, e.g., the representation of Picard and Queyranne for all
st
-minimum cuts of a flow network. ...We begin with an explanation of why this poset structure is common. We show any family of sets
F
that can be defined by a “labelling algorithm” (e.g., the Ford-Fulkerson labelling algorithm for maximum network flow) has an algorithm that constructs the minset poset for
F
. We implement this algorithm to efficiently find the nodes of the poset when
F
is the family of minimum edge cuts of an unweighted graph; we also give related algorithms to construct the entire poset for weighted graphs. The rest of the article discusses applications to edge- and vertex connectivity, both combinatorial and algorithmic, that we now describe.
For digraphs, a natural interpretation of the minset poset represents all minimum edge cuts. In the special case of undirected graphs, the minset poset is proved to be a variant of the well-known cactus representation of all mincuts. We use the poset algorithms to construct the cactus representation for unweighted graphs in time
O
(
m
+λ
2
n
log (n/λ)) (λ is the edge connectivity) improving the previous bound
O
(λ
n
2
) for all but the densest graphs. We also construct the cactus representation for weighted graphs in time
O
(
nm
log(
n
2
/
m
)), the same bound as a previously known algorithm but in linear space
O
(
m
). The latter bound also holds for constructing the minset poset for any weighted digraph; the former bound also holds for constructing the nodes of that poset for any unweighted digraph. The poset is used in algorithms to increase the edge connectivity of a graph by adding the fewest edges possible. For directed and undirected graphs, weighted and unweighted, we achieve the time of the preceding two bounds, i.e., essentially the best-known bounds to compute the edge connectivity itself. Some constructions of minset posets for graph rigidity are also sketched.
For vertex connectivity, the minset poset is proved to be a slight variant of the dominator tree. This leads to an algorithm to construct the dominator tree in time
O
(
m
) on a RAM. (The algorithm is included in the appendix, since other linear-time algorithms of similar simplicity have recently been presented.)
Several papers have achieved time O n m for cardinality matching, starting from first principles. This results in a long derivation. We simplify the task by employing well-known concepts for maximum ...weight matching. We use Edmonds’ algorithm to derive the structure of shortest augmenting paths. We extend this to a complete algorithm for maximum cardinality matching in time O n m .
Celotno besedilo
Dostopno za:
DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
This article shows the weighted matching problem on general graphs can be solved in time
O
(
n
(
m
+
n
log
n
)) for
n
and
m
the number of vertices and edges, respectively. This was previously known ...only for bipartite graphs. The crux is a data structure for blossom creation. It uses a dynamic nearest-common-ancestor algorithm to simplify blossom steps, so they involve only back edges rather than arbitrary nontree edges.
The rest of the article presents direct extensions of Edmonds’ blossom algorithm to weighted
b
-matching and
f
-factors. Again, the time bound is the one previously known for bipartite graphs: for
b
-matching the time is
O
(min {
b
(
V
),
n
log
n
}(
m
+
n
log
n
)), and for
f
-factors the time is
O
(min {
f
(
V
),
m
log
n
}(
m
+
n
log
n
)), where
b
(
V
) and
f
(
V
) both denote the sum of all degree constraints. Several immediate applications of the
f
-factor algorithm are given: The generalized shortest path structure of Reference 19, i.e., the analog of the shortest-paths tree for conservative undirected graphs, is shown to be a version of the blossom structure for
f
-factors. This structure is found in time
O
(|
N
|(
m
+
n
log
n
)) for
N
, the set of negative edges (0 < |
N
| <
n
). A shortest
T
-join is found in time
O
(
n
(
m
+
n
log
n
)) or
O
(|
T
|(
m
+
n
log
n
)) when all costs are nonnegative. These bounds are all slight improvements of previously known ones, and are simply achieved by proper initialization of the
f
-factor algorithm.
The (vertex) connectivity κ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known algorithm for finding κ. For a digraph ...with
n
vertices,
m
edges and connectivity κ the time bound is
O
((
n
+ min{κ
5/2;
, κ
n
3/4;
})
m
). This improves the previous best bound of
O
((
n
+ min{κ
3
, κ
n
})
m
). For an undirected graph both of these bounds hold with
m
replaced by κ
n
. Expander graphs are useful for solving the following subproblem that arises in connectivity computation: A known set
R
of vertices contains two large but unknown subsets that are separated by some unknown set
S
of κ vertices; we must find two vertices of
R
that are separated by
S
.
We present the best known algorithms for approximating the minimum-size undirected $k$-edge connected spanning subgraph. For simple graphs our approximation ratio is $1+ {1}/(2k) + O({1}/{k^2})$. The ...more precise version of this bound requires $k\ge 7$, and for all such $k$ it improves the long-standing performance ratio of Cheriyan and Thurimella SIAM J. Comput., 30 (2000), pp. 528-560, $1+2/(k+1)$. The improvement comes in two steps. First we show that for simple $k$-edge connected graphs, any laminar family of degree $k$ sets is smaller than the general bound ($n(1+ {3}/{k} + O(1/k\sqrt k))$ versus $2n$). This immediately implies that iterated rounding improves the performance ratio of Cheriyan and Thurimella. The second step carefully chooses good edges for rounding. For multigraphs our approximation ratio is $1+(21/11)k <1+1.91/k$ for any $k>1$. This improves the previous ratio $1+2/k$ H. N. Gabow, M. X. Goemans, E. Tardos, and D. P. Williamson, Networks, 53 (2009), pp. 345-357. It is of interest since it is known that for some constant $c>0$, an approximation ratio $\le 1+c/k$ implies $P=NP$. Our approximation ratio extends to the minimum-size Steiner network problem, where $k$ denotes the average vertex demand. The algorithm exploits rounding properties of the first two linear programs in iterated rounding.
PDF
