6. D YNAMIC P ROGRAMMING II 6.

D YNAMIC P ROGRAMMING II

‣ sequence alignment ‣ sequence alignment

‣ Hirschberg′s algorithm ‣ Hirschberg′s algorithm
‣ Bellman–Ford–Moore algorithm ‣ Bellman–Ford–Moore algorithm
‣ distance-vector protocols ‣ distance-vector protocols
‣ negative cycles ‣ negative cycles

SECTION 6.6
Lecture slides by Kevin Wayne

Copyright © 2005 Pearson-Addison Wesley

http://www.cs.princeton.edu/~wayne/kleinberg-tardos

Last updated on 5/19/21 10:15 AM

String similarity Edit distance

Q. How similar are two strings? Edit distance. [Levenshtein 1966, Needleman–Wunsch 1970]
・Gap penalty δ; mismatch penalty αpq.
Ex. ocurrance and occurrence. ・Cost = sum of gap and mismatch penalties.

o c u r r a n c e – o c – u r r a n c e C T – G A C C T A C G

o c c u r r e n c e o c c u r r e n c e C T G G A C G A A C G

6 mismatches, 1 gap 1 mismatch, 1 gap cost = δ + αCG + αTA

assuming αAA = αCC = αGG = αTT = 0

Applications. Bioinformatics, spell correction, machine translation,

o c – u r r – a n c e
speech recognition, information extraction, ...
o c c u r r e – n c e
Spokesperson confirms senior government adviser was found 

0 mismatches, 3 gaps
Spokesperson said the senior adviser was found

3 4
BLOSUM matrix for proteins Dynamic programming: quiz 1

What is edit distance between these two strings?




P A L E T T E P A L A T E


Assume gap penalty = 2 and mismatch penalty = 1. 


A. 1

B. 2

C. 3

D. 4
P A L E T T E
E. 5
P A L – A T E

1 mismatch, 1 gap

5 6

Sequence alignment Sequence alignment: problem structure

Goal. Given two strings x1 x2 ... xm and y1 y2 ... yn , find a min-cost alignment. Def. OPT(i, j) = min cost of aligning prefix strings x1 x2 ... xi and y1 y2 ... yj.
Goal. OPT(m, n).
Def. An alignment M is a set of ordered pairs xi – yj such that each character
appears in at most one pair and no crossings. Case 1. OPT(i, j) matches xi – yj.
xi – yj and xiʹ – yj′ cross if i < i ′, but j > j ʹ
Pay mismatch for xi – yj + min cost of aligning x1 x2 ... xi–1 and y1 y2 ... yj–1.
Def. The cost of an alignment M is:
cost(M ) = α xi y j +
∑ ∑ δ+ ∑ δ Case 2a. OPT(i, j) leaves xi unmatched.
(x i , y j ) ∈ M
i : x unmatched j : y unmatched
!##"## $ !#i### #"#j#### $ Pay gap for xi + min cost of aligning x1 x2 ... xi–1 and y1 y2 ... yj.
mismatch gap

optimal substructure property

Case 2b. OPT(i, j) leaves yj unmatched. (proof via exchange argument)

€ x1 x2 x3 x4 x5 x6 Pay gap for yj + min cost of aligning x1 x2 ... xi and y1 y2 ... yj–1.
C T A C C – G

Bellman equation. j i=0

– T A C A T G
i j=0
y1 y2 y3 y4 y5 y6 OP T (i, j) = x i yj + OP T (i 1, j 1)

an alignment of CTACCG and TACATG min + OP T (i 1, j)

M = { x2–y1, x3–y2, x4–y3, x5–y4, x6–y6 } + OP T (i, j 1)
7 <latexit sha1_base64="60wUnMrLdnu23FwG/Nh5FwbDvxY=">AAADS3ichVJdaxNBFJ3dWq3xq62PvgwGpUUbdsViIRQKvvhmhKYtZEKYnb1JJp2dXWbu1oQlz/4aX/VX+AP8Hb6JD85uFslHwQsDl3PPPefOnYkyJS0GwU/P37qzfffezv3Gg4ePHj/Z3du/sGluBHRFqlJzFXELSmrookQFV5kBnkQKLqPr92X98gaMlak+x1kG/YSPtBxKwdFBgz2PfuycH8jXdHJIWfuUtRssgpHUhXCidt5gbTqhLAaFnL6kDGGKhRzOHZdKekoDylivdQxJv1EhtzMnG0yWSL3hxLjKxnxQTAdyNpiUna8ctZrvKHQTHoWHyyK11zrrP5yFToOBjmvnf9OmOAbzWVqYL5cHu82gFVRBN5OwTpqkjo7b6T6LU5EnoFEobm0vDDLsF9ygFKoUzy1kXFzzEfRcqnkCtl9UbzmnLxwS02Fq3NFIK3S5o+CJtbMkcsyE49iu10rwtlovx+FJv5A6yxG0WBgNc0UxpeXHoLE0IFDNXMKFkW5WKsbccIHu+6y4VNoZiJWbFNNcS5HGsIYqnKLh5RbD9Z1tJhdvWmHQCj+9bZ6d1PvcIc/Ic3JAQvKOnJEPpEO6RHhfvK/eN++7/8P/5f/2/yyovlf3PCUrsbX9Fz1PAsg=</latexit>

8
 Sequence alignment: bottom-up algorithm Sequence alignment: traceback

P A L A T E
SEQUENCE-ALIGNMENT(m, n, x1, …, xm, y1, …, yn, δ, α)
________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

0 2 4 6 8 10 12 P A L E T T E
FOR i = 0 TO m
P 2 0 2 4 6 8 10 P A L – A T E
M [i, 0] ← i δ.
FOR j = 0 TO n 1 mismatch, 1 gap
A 4 2 0 2 4 6 8
M [0, j] ← j δ.
L 6 4 2 0 2 4 6

FOR i = 1 TO m
E 8 6 4 2 1 3 4
FOR j = 1 TO n
M [i, j] ← min { αxi yj + M [i – 1, j – 1], T 10 8 6 4 3 1 3

δ + M [i – 1, j], already
computed T 12 10 8 6 5 3 2
δ + M [i, j – 1] }.
E 14 12 10 8 7 5 3

RETURN M [m, n].

________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

9 10

Sequence alignment: analysis Dynamic programming: quiz 3

Theorem. The DP algorithm computes the edit distance (and an optimal It is easy to modify the DP algorithm for edit distance to…
alignment) of two strings of lengths m and n in Θ(mn) time and space.
Pf.
A. Compute edit distance in O(mn) time and O(m + n) space.
・Algorithm computes edit distance.
・Can trace back to extract optimal alignment itself. ▪ B. Compute an optimal alignment in O(mn) time and O(m + n) space.

C. Both A and B.

D. Neither A nor B.

Theorem. [Backurs–Indyk 2015] If can compute edit distance of two strings

of length n in O(n2−ε) time for some constant ε > 0, then can solve SAT
j i=0
with n variables and m clauses in poly(m) 2(1−δ) n time for some constant δ > 0.
i j=0
which would disprove SETH
Edit Distance Cannot Be Computed (strong exponential time hypothesis) OP T (i, j) = x i yj + OP T (i 1, j 1)
in Strongly Subquadratic Time
(unless SETH is false)∗ min + OP T (i 1, j)
+ OP T (i, j 1)
C] 15 Aug 2017

Arturs Backurs† Piotr Indyk‡

MIT MIT <latexit sha1_base64="60wUnMrLdnu23FwG/Nh5FwbDvxY=">AAADS3ichVJdaxNBFJ3dWq3xq62PvgwGpUUbdsViIRQKvvhmhKYtZEKYnb1JJp2dXWbu1oQlz/4aX/VX+AP8Hb6JD85uFslHwQsDl3PPPefOnYkyJS0GwU/P37qzfffezv3Gg4ePHj/Z3du/sGluBHRFqlJzFXELSmrookQFV5kBnkQKLqPr92X98gaMlak+x1kG/YSPtBxKwdFBgz2PfuycH8jXdHJIWfuUtRssgpHUhXCidt5gbTqhLAaFnL6kDGGKhRzOHZdKekoDylivdQxJv1EhtzMnG0yWSL3hxLjKxnxQTAdyNpiUna8ctZrvKHQTHoWHyyK11zrrP5yFToOBjmvnf9OmOAbzWVqYL5cHu82gFVRBN5OwTpqkjo7b6T6LU5EnoFEobm0vDDLsF9ygFKoUzy1kXFzzEfRcqnkCtl9UbzmnLxwS02Fq3NFIK3S5o+CJtbMkcsyE49iu10rwtlovx+FJv5A6yxG0WBgNc0UxpeXHoLE0IFDNXMKFkW5WKsbccIHu+6y4VNoZiJWbFNNcS5HGsIYqnKLh5RbD9Z1tJhdvWmHQCj+9bZ6d1PvcIc/Ic3JAQvKOnJEPpEO6RHhfvK/eN++7/8P/5f/2/yyovlf3PCUrsbX9Fz1PAsg=</latexit>

11 12
Abstract
The edit distance (a.k.a. the Levenshtein distance) between two strings is defined as the
minimum number of insertions, deletions or substitutions of symbols needed to transform one
string into another. The problem of computing the edit distance between two strings is a
classical computational task, with a well-known algorithm based on dynamic programming.
 Sequence alignment in linear space

Theorem. [Hirschberg] There exists an algorithm to find an optimal

6. D YNAMIC P ROGRAMMING II alignment in O(mn) time and O(m + n) space.
・Clever combination of divide-and-conquer and dynamic programming.
‣ sequence alignment ・Inspired by idea of Savitch from complexity theory.
‣ Hirschberg′s algorithm
‣ Bellman–Ford–Moore algorithm
A = a x a 2 . . . a m if and only if there is a mapping F:
{1, 2, . . . , p} ~ {1, 2, . . . , m} such that f(i) = k only
if c~ is ak and F is a m o n o t o n e strictly increasing func-
tion (i.e. F(i) = u, F ( j ) = v, and i < j imply that

‣ distance-vector protocols
u<v).
Programming G. Manacher
String C is a c o m m o n subsequence of strings A and B
Techniques Editor
if and only if C is a subsequence of A and C is a subse-
A Linear Space quence of B.

‣ negative cycles Algorithm for

The problem can be stated as follows: Given strings
A = aia.2.. "am and B = b x b 2 . . . b n (over alphabet Z),
find a string C = ClC2...cp such that C, is a c o m m o n
Computing Maximal subsequence of A and B and p is maximized.
We call C an example of a m a x i m a l c o m m o n subse-
Common Subsequences quence.
Notation. F o r string D = dld2. • • dr, Dk t is dkdk+l. • • d,
i f k < t ; d k d k _ x . . . d , i f k >__ t. When k > t, we shall
D.S. Hirschberg
write ]3kt so as to make clear that we are referring to a
Princeton University
"reverse substring" of D.
SECTION 6.7 L(i, j ) is the m a x i m u m length possible of any com-
mon subsequence of Ax~ and B~s.
x[ lY is the concatenation of strings x and y.
The problem of finding a longest common subse- We present the algorithm described in [3], which
quence of two strings has been solved in quadratic time takes quadratic time and space.
and space. An algorithm is presented which will solve
this problem in quadratic time and in linear space.
Key Words and Phrases: subsequence, longest Algorithm A
common subsequence, string correction, editing
CR Categories: 3.63, 3.73, 3.79, 4.22, 5.25 Algorithm A accepts as input strings A~m and Bx.
and produces as output the matrix L (where the ele-
ment L(i, j ) corresponds to our notation of m a x i m u m
length possible of any c o m m o n subsequence of Axl and
B.).
Introduction ALGA (m, n, A, B, L)
1. Initialization: L(i, 0) ~ 0 [i=0...m]; 14
The problem of finding a longest c o m m o n subse- L(O,j) +-- 0 [j=0...n];
quence of two strings has been solved in quadratic time 2. for i +-- 1 to m do
begin
and space [1, 3]. F o r strings of length 1,000 (assuming 3. for j ~- 1 to n do
coefficients of 1 microsecond and 1 byte) the solution if A (i) = B(j) then L(i, j) ~- L(i-- 1, j - - 1) "k 1
would require 106 microseconds (one second) and 106 else L(i,j) ~-- max{L(i,j--1), L(i-- I,j)}
bytes (1000K bytes). The former is easily accommo- end
dated, the latter is not so easily obtainable. I f the

Hirschberg′s algorithm Hirschberg′s algorithm strings were of length 10,000, the problem might not be
solvable in main m e m o r y for lack of space. Proof of Correctness of Algorithm A
To find L(i, j), let a c o m m o n subsequence of that
We present an algorithm which will solve this prob-
lem in quadratic time and in linear space. For example, length be denoted by S(i, j ) = ClC2...cp. I f al = bj,
assuming coefficients of 2 microseconds and 10 bytes, we can do no better than by taking cp = a~ and looking
for strings of length 1,000 we would require 2 seconds for c l . . . c p _ l as a c o m m o n subsequence of length
L(i, j) -- 1 of strings AI,~-1 and B1.i-x. Thus, in this
Edit distance graph. Edit distance graph. and 10K bytes; for strings of length 10,000 we would
require a little over 3 minutes and 100K bytes. case, L ( i , j ) = L ( i - 1,j- 1) -+- 1.

・Let f (i, j) denote length of shortest path from (0,0) to (i, j). ・Let f (i, j) denote length of shortest path from (0,0) to (i, j).
String C = c~c2...cp is a subsequence of string If ai ~ bs, then cp is ai, b;, or neither (but not both).
Copyright © 1975, Association for Computing Machinery, Inc. I f cp is a~, then a solution C to problem (A~, B~j) [writ-
General permission to republish, but not for profit, all or part ten P(i, j)] will be a solution to P(i, j - 1) since bj is

・Lemma: f (i, j) = OPT(i, j) for all i and j. ・Lemma: f (i, j) = OPT(i, j) for all i and j.
of this material is granted provided that ACM's copyright notice not used. Similarly, if cp is bi, then we can get a solu-
is given and that reference is made to the publication, to its date
of issue, and to the fact that reprinting privileges were granted tion to P(i, j ) by solving P ( i -- 1, j ) . I f c~ is neither,
by permission of the Association for Computing Machinery. then a solution to either P ( i -- 1,j) or P ( i , j -- 1) will
Research work was supported in part by NSF grant GJ-30126 suffice. In determining the length of the solution, it is
and National Science Foundation Graduate Felolwship. Author's
address: Department of Electrical Engineering, Princeton Uni- seen that L(i, j ) [corresponding to P(i, j)] will be the
versity, Princeton, NJ 08540. m a x i m u m o f L ( i - - 1 , j ) and L ( i , j - - 1). []

341 Communications June 1975

Pf of Lemma. [ by strong induction on i + j ] of
the ACM
Volume 18
Number 6

・Base case: f (0, 0) = OPT (0, 0) = 0.

ε y1 y2 y3 y4 y5 y6
・Inductive hypothesis: assume true for all (iʹ, jʹ) with iʹ + jʹ < i + j.
ε 0–0 ・Last edge on shortest path to (i, j) is from (i – 1, j – 1), (i – 1, j), or (i, j – 1).
・Thus,
ff (i,
(i, j)
j) =
= min{
min{ xii y
x yjj + ff (i
+ (i 1, jj
1, 1),
1), + ff (i
+ (i 1, j),
1, j), + ff (i,
+ (i, jj 1)}
1)}
x1
α xi y j =
= min{
min{ xii y
yjj + OP
+ OP T
T (i
(i 1, jj
1, 1),
1), + OP
+ OP T
T (i
(i 1, j),
1, j), + OP
+ OP T
T (i,
(i, jj 1)}
1)}
δ x

inductive = OP T
T (i,
(i, j)
j) ▪
x2 hypothesis
= OP
i–j
€ δ
Bellman
α xi y j
δ
equation

x3 m–n i–j
15 € δ 16
Hirschberg’s algorithm Hirschberg’s algorithm

Edit distance graph. Edit distance graph.

・Let f (i, j) denote length of shortest path from (0,0) to (i, j). ・Let g(i, j) denote length of shortest path from (i, j) to (m, n).
・Lemma: f (i, j) = OPT(i, j) for all i and j.
・Can compute f (·, j) for any j in O(mn) time and O(m + n) space.
j

ε y1 y2 y3 y4 y5 y6 ε y1 y2 y3 y4 y5 y6

ε 0–0 ε 0–0

x1 x1 i–j

x2 i–j x2

x3 m–n x3 m–n
17 18

Hirschberg’s algorithm Hirschberg’s algorithm

Edit distance graph. Edit distance graph.

・Let g(i, j) denote length of shortest path from (i, j) to (m, n). ・Let g(i, j) denote length of shortest path from (i, j) to (m, n).
・Can compute g(i, j) by reversing the edge orientations and ・Can compute g(·, j) for any j in O(mn) time and O(m + n) space.
inverting the roles of (0, 0) and (m, n).

ε y1 y2 y3 y4 y5 y6 ε y1 y2 y3 y4 y5 y6

ε 0–0 ε 0–0

δ
x1 i–j x1 i–j

δ xi+1 yj+1

x2 x2

x3 m–n x3 m–n
19 20
Hirschberg’s algorithm Hirschberg’s algorithm

Observation 1. The length of a shortest path that uses (i, j) is f (i, j) + g(i, j). Observation 2. let q be an index that minimizes f(q, n / 2) + g (q, n / 2).
Then, there exists a shortest path from (0, 0) to (m, n) that uses (q, n / 2).

n/2

ε y1 y2 y3 y4 y5 y6 ε y1 y2 y3 y4 y5 y6

ε 0–0 ε 0–0

x1 i–j x1 i–j q

x2 x2

x3 m–n x3 m–n
21 22

Hirschberg’s algorithm Hirschberg’s algorithm: space analysis

Divide. Find index q that minimizes f (q, n / 2) + g(q, n / 2); save node i–j as Theorem. Hirschberg’s algorithm uses Θ(m + n) space.
part of solution.
Pf.
Conquer. Recursively compute optimal alignment in each piece. ・Each recursive call uses Θ(m) space to compute f (·, n / 2) and g(·, n / 2).
・Only Θ(1) space needs to be maintained per recursive call.
・Number of recursive calls ≤ n. ▪
n/2

ε y1 y2 y3 y4 y5 y6

ε 0–0

x1 i–j q

x2

x3 m–n
23 24
Dynamic programming: quiz 4 Hirschberg’s algorithm: running time analysis warmup

What is the worst-case running time of Hirschberg’s algorithm? Theorem. Let T(m, n) = max running time of Hirschberg’s algorithm on
strings of lengths at most m and n. Then, T(m, n) = O(m n log n).

A. O(mn)
Pf.
B. O(mn log m)
・T(m, n) is monotone nondecreasing in both m and n.
C. O(mn log n) ・T(m, n) ≤ 2 T(m, n / 2) + O(m n)
⇒ T(m, n) = O(m n log n).
D. O(mn log m log n)

Remark. Analysis is not tight because two subproblems are of size

(q, n / 2) and (m – q, n / 2). Next, we prove T(m, n) = O(m n).

25 26

Hirschberg′s algorithm: running time analysis LONGEST COMMON SUBSEQUENCE

Theorem. Let T(m, n) = max running time of Hirschberg’s algorithm on
strings of lengths at most m and n. Then, T(m, n) = O(m n). Problem. Given two strings x1 x2 ... xm and y1 y2 ... yn , find a common
subsequence that is as long as possible.
Pf. [ by strong induction on m + n ]
・O(m n) time to compute f ( ·, n / 2) and g ( ·, n / 2) and find index q. Alternative viewpoint. Delete some characters from x ; delete some
・T(q, n / 2) + T(m – q, n / 2) time for two recursive calls. character from y ; a common subsequence if it results in the same string.
・Choose constant c so that: T(m, 2) ≤ c m
T(2, n) ≤ c n
Ex. LCS(GGCACCACG, ACGGCGGATACG ) = GGCAACG.
T(m, n) ≤ c m n + T(q, n / 2) + T(m – q, n / 2)
・Claim. T(m, n) ≤ 2 c m n.
・Base cases: m = 2 and n = 2. Applications. Unix diff, git, bioinformatics.
・Inductive hypothesis: T(m, n) ≤ 2 c m n for all (mʹ, nʹ) with mʹ + nʹ < m + n.

T(m, n) ≤ T(q, n / 2) + T(m – q, n / 2) + c m n

≤ 2 c q n / 2 + 2 c (m – q) n / 2 + c m n
inductive = cq n + cmn – cqn + cmn
hypothesis
= 2 cmn ▪
27 28
LONGEST COMMON SUBSEQUENCE LONGEST COMMON SUBSEQUENCE

Solution 1. Dynamic programming. Solution 2. Reduce to finding a min-cost alignment of x and y with
Def. OPT(i, j) = length of LCS of prefix strings x1 x2 ... xi and y1 y2 ... yj. ・Gap penalty δ = 1
・Mismatch penalty
0 p=q
Goal. OPT(m, n). pq =
p=q
<latexit sha1_base64="fJvJmXDOUjarlNvgrVZSE2Bl4wI=">AAACj3icbVFNj9MwEHXD11K+uuXIZUQF4lQlaCWKVosqcYHbIlF2pbqqHGfSWus4rj1BraL+Q/4Af4MrHHC6OdCWkSw9vfc8M35OrVae4vhnJ7pz9979BycPu48eP3n6rHfa/+bLykmcyFKX7joVHrUyOCFFGq+tQ1GkGq/Sm4+NfvUdnVel+Uobi7NCLIzKlRQUqHkv50LbpZjXdrWFiy5PcaFMLUNHv+3y8xheAydcU63yLfBzsHABK+A8aFyZnDbHBm5wBavGgiZrW817g3gY7wqOQdKCAWvrcn7a6fOslFWBhqQW3k+T2NKsFo6U1Bh2qzxaIW/EAqcBGlGgn9W7QLbwKjAZ5KULxxDs2H9v1KLwflOkwVkIWvpDrSH/p00rykezWhlbERp5OyivNFAJTbqQKYeS9CYAIZ0Ku4JcCickhT/Ym7LrbVHuvaReV0bJMsMDVtOanGhSTA4zOwaTt8P3w+TL2WA8auM8YS/YS/aGJewdG7NP7JJNmGQ/2C/2m/2J+tEo+hCNb61Rp73znO1V9PkvMtTJIQ==</latexit>

Case 1. xi = yj. ・Edit distance = # gaps = number of characters deleted from x and y.
・ 1 + length of LCS of x1 x2 ... xi–1 and y1 y2 ... yj–1.
optimal substructure property
・Length of LCS = (m + n − edit distance) / 2.
(proof via exchange argument)
Case 2. xi ≠ yj. Analysis. O(mn) time and O(m + n) space.
・ Delete xi : length of LCS of x1 x2 ... xi–1 and y1 y2 ... yj.
・ Delete y : j length of LCS of x1 x2 ... xi and y1 y2 ... yj–1. Lower bound. No O(n2−ε) algorithm unless SETH is false.

Bellman equation.
Tight Hardness Results for LCS and other
0 i=0 j=0 Sequence Similarity Measures
Amir Abboud⇤ Arturs Backurs Virginia Vassilevska Williams⇤
OP T (i, j) = 1 + OP T (i 1, j 1) xi = yj Stanford University MIT Stanford University
[email protected] [email protected] [email protected]

<latexit sha1_base64="JiQBeZHxov289Psn1044C6KDh34=">AAADFnicbZLNbtQwEMed8FWWr205crFYgVpBVwlCalFVqRIXbiyiSyuto8hxZrfeOk6wHZQo2gs8BU/DCXHlykPwDtjZFHW3tZTon9/M/MceJykE1yYI/nj+jZu3bt/ZuNu7d//Bw0f9za1POi8VgzHLRa5OE6pBcAljw42A00IBzRIBJ8n5Wxc/+QJK81wem7qAKKMzyaecUWNR3P/7fnS8zV/i+Q4mB4fkAPdIAjMuG2ZN9aJnSYCfY2KgMrjh04VNwxwfWmpFh3PV4vkSk8lwD7LIleLQ8hdWtF12Q9tnN9y58Luwq2JnWMfzy7Uko1XbovlfTNw23XtJ2m9nRxbXORIJn51pj4BMu+PE/UEwDNqFr4qwEwPUrVG86W2RNGdlBtIwQbWehEFhooYqw5kAO59SQ0HZOZ3BxEpJM9BR097LAj+zJMXTXNlHGtzSyxUNzbSus8RmZtSc6fWYg9fFJqWZ7kcNl0VpQLJlo2kpsMmxu2SccgXMiNoKyhS3e8XsjCrKjP0VVrq03gWwlZM0VSk5y1NYo8JURlE3xXB9ZlfF+NXwzTD88HpwtN+NcwM9QU/RNgrRHjpC79AIjRHzPnq199X75n/3f/g//V/LVN/rah6jleX//gcQD+1P</latexit>
max {OP T (i 1, j), OP T (i, j 1)} xi = yj
29 30
Abstract
Two important similarity measures between sequences are the longest common subsequence
(LCS) and the dynamic time warping distance (DTWD). The computations of these measures for
two given sequences are central tasks in a variety of applications. Simple dynamic programming
algorithms solve these tasks in O(n2 ) time, and despite an extensive amount of research, no
algorithms with significantly better worst case upper bounds are known.

Shortest paths with negative weights

In this paper, we show that an O(n2 " ) time algorithm, for some " > 0, for computing
the LCS or the DTWD of two sequences of length n over a constant size alphabet, refutes the
popular Strong Exponential Time Hypothesis (SETH). Moreover, we show that computing the
LCS of k strings over an alphabet of size O(k) cannot be done in O(nk " ) time, for any " > 0,
under SETH.

Shortest-path problem. Given a digraph G = (V, E), with arbitrary edge

6. D YNAMIC P ROGRAMMING II lengths ℓvw, find shortest path from source node s to destination node t.

assume there exists a path

‣ sequence alignment from every node to t

‣ Hirschberg′s algorithm
‣ Bellman–Ford–Moore algorithm −2

‣ distance-vector protocols 5
4 12
s −5
‣ negative cycles ⇤
Supported by NSF Grant CCF-1417238, BSF Grant BSF:2012338 and a Stanford SOE Hoover Fellowship.
8
17
7

9 −1
−6
SECTION 6.8 5 11
5
−3 13

4 10 t

length of shortest s↝t path = 9 − 3 − 6 + 11 = 11

32
Shortest paths with negative weights: failed attempts Negative cycles

Dijkstra. May not produce shortest paths when edge lengths are negative. Def. A negative cycle is a directed cycle for which the sum of its edge
lengths is negative.
s 6 v

−8 Dijkstra selects the vertices in the order s, t, w, v

2 4
But shortest path from s to t is s→v→w→t.

t 3 w 5

−3 −3
Reweighting. Adding a constant to every edge length does not necessarily
make Dijkstra’s algorithm produce shortest paths.
4 −4

s 14 v

Adding 8 to each edge weight changes the a negative cycle W : (W ) = e < 0

10 0 shortest path from s→v→w→t to s→t. e W
12 <latexit sha1_base64="RSPr2SRjQX4pLklN8jDnfDJBxfc=">AAACWHicbVDLSsNAFJ3ER+u7rUs3g0XQTU1EsKKC4MZlBWuFpoTJ9FYHJ5MwcyMtoZ/h17jVjxB/xknbha1emMvhnPuYe6JUCoOe9+W4S8srq6Xy2vrG5tb2TqVaezBJpjm0eSIT/RgxA1IoaKNACY+pBhZHEjrRy02hd15BG5Goexyl0IvZkxIDwRlaKqwcByDlYeeIBhf0qkiByeIwBxoIRTtjWsghFMJlkbywUvca3iToX+DPQJ3MohVWnVrQT3gWg0IumTFd30uxlzONgksYrweZgZTxF/YEXQsVi8H08sllY3pgmT4dJNo+hXTC/u7IWWzMKI5sZczw2SxqBfmf1s1w0OzlQqUZguLTRYNMUkxoYRPtCw0c5cgCxrWwf6X8mWnG0Zo5t2UyOwU+d0k+zJTgSR8WWIlD1GxsXfQXPfsL2ieN84Z/d1q/bs7sLJM9sk8OiU/OyDW5JS3SJpy8kXfyQT6db9dxS+7atNR1Zj27ZC7c2g+AELL2</latexit>

t 11 w
33 34

Shortest paths and negative cycles Shortest paths and negative cycles

Lemma 1. If some v↝t path contains a negative cycle, then there does not Lemma 2. If G has no negative cycles, then there exists a shortest v↝t path
exist a shortest v↝t path. that is simple (and has ≤ n – 1 edges).

Pf. If there exists such a cycle W, then can build a v↝t path of arbitrarily Pf.
negative length by detouring around W as many times as desired. ▪ ・Among all shortest v↝t paths, consider one that uses the fewest edges.
・If that path P contains a directed cycle W, can remove the portion of P
corresponding to W without increasing its length. ▪

v v
t t
W W

ℓ(W) < 0 ℓ(W) ≥ 0

35 36
Shortest-paths and negative-cycle problems Dynamic programming: quiz 5

Single-destination shortest-paths problem. Given a digraph G = (V, E) with Which subproblems to find shortest v↝t paths for every node v?

edge lengths ℓvw (but no negative cycles) and a distinguished node t,
find a shortest v↝t path for every node v.
A. OPT(i, v) = length of shortest v↝t path that uses exactly i edges.

Negative-cycle problem. Given a digraph G = (V, E) with edge lengths ℓvw, B. OPT(i, v) = length of shortest v↝t path that uses at most i edges.
find a negative cycle (if one exists). C. Neither A nor B.

1 5

4 2 −3 5 −3 −3

t 4 −4

shortest-paths tree negative cycle

37 38

Shortest paths with negative weights: dynamic programming Shortest paths with negative weights: implementation

Def. OPT(i, v) = length of shortest v↝t path that uses ≤ i edges.

Goal. OPT(n – 1, v) for each v. by Lemma 2, if no negative cycles,

there exists a shortest v↝t path that is simple SHORTEST-PATHS(V, E, ℓ, t)
_________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Case 1. Shortest v↝t path uses ≤ i – 1 edges. FOREACH node v ∈ V :

・OPT(i, v) = OPT(i – 1, v). optimal substructure property
M [0, v] ← ∞.
(proof via exchange argument)
M [0, t] ← 0.
Case 2. Shortest v↝t path uses exactly i edges.
・if (v, w) is first edge in shortest such v↝t path, incur a cost of ℓvw.
FOR i = 1 TO n – 1

・Then, select best w↝t path using ≤ i – 1 edges. FOREACH node v ∈ V :

M [i, v] ← M [i – 1, v].
Bellman equation. FOREACH edge (v, w) ∈ E :
M [i, v] ← min { M [i, v], M [i – 1, w] + ℓvw }.
0 i=0 v=t _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

OP T (i, v) = i=0 v=t

min OP T (i 1, v), min {OP T (i 1, w) + vw } i>0

<latexit sha1_base64="XuctLUoOwYWddz7b+9lLeQH116s=">AAADV3icjVJdaxNBFJ1NtMb40aY++nIxKBFj2LWChVApiOCbEZq2kAlhdvZuMnR2djszmyYs+RX+Gl/1V/TX6GwaWpP44IWFu+eec+fs2QkzKYz1/WuvUr13f+dB7WH90eMnT3f3GvunJs01xz5PZarPQ2ZQCoV9K6zE80wjS0KJZ+HFp3J+NkVtRKpO7DzDYcLGSsSCM+ugUcNrf+2dtEQbpq+Bdo9ot05DHAtVcLfULOq068MroBZnFgoQMSxAwBH4txBTkcOmDrNA6aBzgMnQqahQsZ3/n5QqvNxQJ0IBlRg7tADahqXJt0Fps+18QkmgUiTCmlHRmrbhytl3ms+LO9mtxs3eAEUpR8X0yhG0GE8cYwHl5ru3La8fS6+0TlFFqzhGe02/4y8Ltptg1TTJqnou330apTxPUFkumTGDwM/ssGDaCi7R5ZsbzBi/YGMcuFaxBM2wWP7XBbx0SARxqt2jLCzRvxUFS4yZJ6FjJsxOzOasBP81G+Q2PhwWQmW5RcVvDopzCTaF8pJAJDRyK+euYVwL5xX4hGnGrbtKa6csd2fI176kmOVK8DTCDVTamdWsTDHYzGy7OX3XCfxO8O198/hwlWeNPCcvSIsE5AM5Jl9Ij/QJ9757P7yf3q/KdeV3dadau6FWvJXmGVmrauMP2c4DqA==</latexit>
(v,w) E

39 40
Shortest paths with negative weights: implementation Dynamic programming: quiz 6

Theorem 1. Given a digraph G = (V, E) with no negative cycles, the DP It is easy to modify the DP algorithm for shortest paths to…
algorithm computes the length of a shortest v↝t path for every node v
in Θ(mn) time and Θ(n2) space.
A. Compute lengths of shortest paths in O(mn) time and O(m + n) space.

Pf. B. Compute shortest paths in O(mn) time and O(m + n) space.

・Table requires Θ(n2)

space. C. Both A and B.
・Each iteration i takes Θ(m) time since we examine each edge once. ▪
D. Neither A nor B.

Finding the shortest paths.

・Approach 1: Maintain successor[i, v] that points to next node
on a shortest v↝t path using ≤ i edges.
・Approach 2: Compute optimal lengths M[i, v] and consider
only edges with M[i, v] = M[i – 1, w] + ℓvw. Any directed path in this
subgraph is a shortest path.

41 42

Shortest paths with negative weights: practical improvements Bellman–Ford–Moore: efficient implementation

Space optimization. Maintain two 1D arrays (instead of 2D array).

・d[v] = length of a shortest v↝t path that we have found so far. BELLMAN–FORD–MOORE(V, E, c, t)
・successor[v] = next node on a v↝t path. _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

FOREACH node v ∈ V :
d[v] ← ∞.
Performance optimization. If d[w] was not updated in iteration i – 1,
then no reason to consider edges entering w in iteration i. successor[v] ← null.
d[t] ← 0.
FOR i = 1 TO n – 1
FOREACH node w ∈ V :
IF (d[w] was updated in previous pass)
FOREACH edge (v, w) ∈ E :
pass i
IF (d[v] > d[w] + ℓvw) O(m) time

d[v] ← d[w] + ℓvw.

successor[v] ← w.
IF (no d[⋅] value changed in pass i) STOP.
_________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

43 44
Dynamic programming: quiz 7 Bellman–Ford–Moore: analysis

Which properties must hold after pass i of Bellman–Ford–Moore?
 Lemma 3. For each node v : d[v] is the length of some v↝t path.
Lemma 4. For each node v : d[v] is monotone non-increasing.

A. d[v] = length of a shortest v↝t path using ≤ i edges.

Lemma 5. After pass i, d[v] ≤ length of a shortest v↝t path using ≤ i edges.
B. d[v] = length of a shortest v↝t path using exactly i edges. Pf. [ by induction on i ]
C. Both A and B. ・Base case: i = 0.
D. Neither A nor B.
・Assume true after pass i.
・Let P be any v↝t path with ≤ i + 1 edges.
・Let (v, w) be first edge in P and let Pʹ be subpath from w to t.
・By inductive hypothesis, at the end of pass i, d[w] ≤ ℓ(Pʹ)
because Pʹ is a w↝t path with ≤ i edges.
d[v] = 3 d[w] = 2 d[t] = 0 ・After considering edge (v, w) in pass i + 1: and by Lemma 4,
d[w] does not increase
v 1 w 2 t
d[v] ≤ ℓvw + d[w]
4
≤ ℓvw + ℓ(Pʹ)
and by Lemma 4,
if node w considered before node v,
then d[v] = 3 after 1 pass
d[v] does not increase = ℓ(P) ▪
45 46

Bellman–Ford–Moore: analysis Dynamic programming: quiz 8

Theorem 2. Assuming no negative cycles, Bellman–Ford–Moore computes Assuming no negative cycles, which properties must hold throughout
the lengths of the shortest v↝t paths in O(mn) time and Θ(n) extra space. Bellman–Ford–Moore?

Pf. Lemma 2 + Lemma 5. ▪

A. Following successor[v] pointers gives a directed v↝t path.

shortest path exists and after i passes,
has at most n−1 edges d[v] ≤ length of shortest path
that uses ≤ i edges B. If following successor[v] pointers gives a directed v↝t path,

then the length of that v↝t path is d[v].

C. Both A and B.
Remark. Bellman–Ford–Moore is typically faster in practice.
D. Neither A nor B.
・Edge (v, w) considered in pass i + 1 only if d[w] updated in pass i.
・If shortest path has k edges, then algorithm finds it after ≤ k passes.

47 48
Bellman–Ford–Moore: analysis Bellman–Ford–Moore: analysis

Claim. Throughout Bellman–Ford–Moore, following the successor[v] Claim. Throughout Bellman–Ford–Moore, following the successor[v]
pointers gives a directed path from v to t of length d[v]. pointers gives a directed path from v to t of length d[v].

Counterexample. Claim is false! Counterexample. Claim is false!

・Length of successor v↝t path may be strictly shorter than d[v]. ・Length of successor v↝t path may be strictly shorter than d[v].

consider nodes in order: t, 1, 2, 3 consider nodes in order: t, 1, 2, 3

successor[2] = 1 successor[1] = t successor[2] = 1 successor[1] = 3

d[2] = 20 d[1] = 10 d[t] = 0 d[2] = 20 d[1] = 2 d[t] = 0
2 10 1 10 t 2 10 1 10 t

1 1
1 1

successor[3] = t 3 successor[3] = t 3
d[3] = 1 d[3] = 1
49 50

Bellman–Ford–Moore: analysis Bellman–Ford–Moore: analysis

Claim. Throughout Bellman–Ford–Moore, following the successor[v] Claim. Throughout Bellman–Ford–Moore, following the successor[v]
pointers gives a directed path from v to t of length d[v]. pointers gives a directed path from v to t of length d[v].

Counterexample. Claim is false! Counterexample. Claim is false!

・Length of successor v↝t path may be strictly shorter than d[v]. ・Length of successor v↝t path may be strictly shorter than d[v].
・If negative cycle, successor graph may have directed cycles. ・If negative cycle, successor graph may have directed cycles.

consider nodes in order: t, 1, 2, 3, 4 consider nodes in order: t, 1, 2, 3, 4

d[3] = 10 d[2] = 8 d[3] = 10 d[2] = 8

3 2 2 3 2 2
9 d[t] = 0 9 d[t] = 0
t t
1 3 1 3

5 5

4 −8 1 4 −8 1

d[4] = 11 d[1] = 5 51 d[4] = 11 d[1] = 3 52

Bellman–Ford–Moore: finding the shortest paths Bellman–Ford–Moore: finding the shortest paths

Lemma 6. Any directed cycle W in the successor graph is a negative cycle. Theorem 3. Assuming no negative cycles, Bellman–Ford–Moore finds
Pf. shortest v↝t paths for every node v in O(mn) time and Θ(n) extra space.
・If successor[v] = w, we must have d[v] ≥ d[w] + ℓvw. Pf.
(LHS and RHS are equal when successor[v] is set; d[w] can only decrease; ・The successor graph cannot have a directed cycle. [Lemma 6]
d[v] decreases only when successor[v] is reset) ・Thus, following the successor pointers from v yields a directed path to t.
・Let v → v → … → v → v be the sequence of nodes in a directed cycle W.
1 2 k 1 ・Let v = v1 → v2 → … → vk = t be the nodes along this path P.
・Assume that (v , v ) is the last edge in W added to the successor graph.
k 1 ・Upon termination, if successor[v] = w, we must have d[v] = d[w] + ℓvw.
・Just prior to that: d[v ] ≥ d[v ] + ℓ(v , v )
1 2 1 2 (LHS and RHS are equal when successor[v] is set; d[·] did not change)
d[v2] ≥ d[v3] + ℓ(v2, v3) ・Thus, d[v1] = d[v2] + ℓ(v1, v2)
since algorithm
⋮ ⋮ ⋮ d[v2] = d[v3] + ℓ(v2, v3) terminated

d[vk–1] ≥ d[vk] + ℓ(vk–1, vk) ⋮ ⋮ ⋮

d[vk] > d[v1] + ℓ(vk, v1) holds with strict inequality
since we are updating d[vk]
d[vk–1] = d[vk] + ℓ(vk–1, vk)

・Adding inequalities yields ℓ(v , v ) + ℓ(v , v ) 1 2 2 3 + … + ℓ(vk–1, vk) + ℓ(vk, v1) < 0. ▪ ・Adding equations yields d[v] = d[t] + ℓ(v1, v2) + ℓ(v2, v3) + … + ℓ(vk–1, vk). ▪

W is a negative cycle length of path P

min length of any v↝t path 0
(Theorem 2)

53 54

Single-source shortest paths with negative weights

year worst case discovered by

6. D YNAMIC P ROGRAMMING II
1955 O(n4) Shimbel
‣ sequence alignment
1956 O(m n2 W) Ford
‣ Hirschberg′s algorithm
1958 O(m n) Bellman, Moore
‣ Bellman–Ford–Moore algorithm
1983 O(n3/4 m log W) Gabow
‣ distance-vector protocols
1989 O(m n1/2 log(nW)) Gabow–Tarjan

1993 Goldberg
‣ negative cycles
O(m n1/2 log W)

2005 O(n2.38 W) Sankowsi, Yuster–Zwick

2016 Õ(n10/7 log W) Cohen–Mądry–Sankowski–Vladu

SECTION 6.9
20xx

single-source shortest paths with weights between –W and W

55
Distance-vector routing protocols Distance-vector routing protocols

Communication network. Distance-vector routing protocols. [ “routing by rumor” ]

・Node ≈ router. ・Each router maintains a vector of shortest-path lengths to every other
・Edge ≈ direct communication link. node (distances) and the first hop on each path (directions).
・Length of edge ≈ latency of link. non-negative, but
Bellman–Ford–Moore used anyway! ・Algorithm: each router performs n separate computations, one for each
potential destination node.
Dijkstra’s algorithm. Requires global information of network.
Ex. RIP, Xerox XNS RIP, Novell’s IPX RIP, Cisco’s IGRP, DEC’s DNA Phase IV,
Bellman–Ford–Moore. Uses only local knowledge of neighboring nodes. AppleTalk’s RTMP.

Synchronization. We don’t expect routers to run in lockstep. The order in

which each edges are processed in Bellman–Ford–Moore is not important. Caveat. Edge lengths may change during algorithm (or fail completely).
Moreover, algorithm converges even if updates are asynchronous.
suppose this edge
1 gets deleted

s 1 v 1 t

d(s) = 2 d(v) = 1 d(t) = 0

57
“counting to infinity” 58

Path-vector routing protocols

not just the distance

Link-state routing protocols. and first hop

・Each router stores the whole path (or network topology). 6. D YNAMIC P ROGRAMMING II
・Based on Dijkstra’s algorithm.
・Avoids “counting-to-infinity” problem and related difficulties. ‣ sequence alignment
・Requires significantly more storage. ‣ Hirschberg′s algorithm
‣ Bellman–Ford–Moore algorithm
Ex. Border Gateway Protocol (BGP), Open Shortest Path First (OSPF). ‣ distance vector protocol
‣ negative cycles

SECTION 6.10

59
Detecting negative cycles Detecting negative cycles: application

Negative cycle detection problem. Given a digraph G = (V, E), with edge Currency conversion. Given n currencies and exchange rates between pairs
lengths ℓvw, find a negative cycle (if one exists). of currencies, is there an arbitrage opportunity?

Remark. Fastest algorithm very valuable!

0.741 * 1.366 * .995 = 1.00714497

EUR
0.
88
0 8
35
1.

1.4
66
1
74

1.3
0. 1.

33
12
6
0.657
USD GBP
1. 1.521
5 6 06
1 8
53

1.0
1.

14
11

1.6
−3 2 4 −3 −3

32

20
0.9

0.6
0.7
0

0.6
65

95

98
0. 0.
94
3
4 −4 1.049
CAD CHF
0.953
61 62
An arbitrage opportunity

Detecting negative cycles Detecting negative cycles

Lemma 7. If OPT(n, v) = OPT(n – 1, v) for every node v, then no negative cycles. Theorem 4. Can find a negative cycle in Θ(mn) time and Θ(n2) space.
Pf. The OPT(n, v) values have converged ⇒ shortest v↝t path exists. ▪ Pf.
・Add new sink node t and connect all nodes to t with 0-length edge.
Lemma 8. If OPT(n, v) < OPT(n – 1, v) for some node v, then (any) shortest v↝t ・G has a negative cycle iff G ʹ has a negative cycle.
path of length ≤ n contains a cycle W. Moreover W is a negative cycle. ・Case 1. [ OPT(n, v) = OPT(n – 1, v) for every node v ]
By Lemma 7, no negative cycles.
Pf. [by contradiction] ・Case 2. [ OPT(n, v) < OPT(n – 1, v) for some node v ]
・Since OPT(n, v) < OPT(n – 1, v), we know that shortest v↝t path P has Using proof of Lemma 8, can extract negative cycle from v↝t path.
exactly n edges. (cycle cannot contain t since no edge leaves t) ▪
・By pigeonhole principle, the path P must contain a repeated node x.
・Let W be any cycle in P.
・Deleting W yields a v↝t path with <
5 6 G′
n edges ⇒ W is a negative cycle. ▪
0
0
x 4 −3 t
v −3 2 −3
t 0
W
0
4 −4
c(W) < 0 63 64
Detecting negative cycles Dynamic programming: quiz 9

Theorem 5. Can find a negative cycle in O(mn) time and O(n) extra space. How difficult to find a negative cycle in an undirected graph?

Pf.
・Run Bellman–Ford–Moore on G ʹ for nʹ = n + 1 passes (instead of nʹ – 1). A. O(m log n)
・If no d[v] values updated in pass nʹ, then no negative cycles.
・Otherwise, suppose d[s] updated in pass nʹ. B. O(mn)

・Define pass(v) = last pass in which d[v] was updated. C. O(mn + n2 log n)
・Observe pass(s) = nʹ and pass(successor[v]) ≥ pass(v) – 1 for each v. D. O(n2.38)
・Following successor pointers, we must eventually repeat a node. Chapter 46

・Lemma 6 ⇒ the corresponding cycle is a negative cycle. ▪ E. No poly-time algorithm is known.

Chapter Data
46 Structures for Weighted Matching and
Nearest Common Ancestors with Linking

Remark. See p. 304 for improved version and early termination rule. Structures
Data Harold for Weighted
N. Gabow* Matching and
Nearest Common Ancestors with Linking
(Tarjan’s subtree disassembly trick)
Harold N. Gabow*

Abstract. This paper shows that the weighted match- optimization; detailed discussions are in [L, LP, PS].
ing problem on general graphs can be solved in time Edmonds gave the first polynomial-time algorithm for
O(n(m + n log n)), f or n and m the number of vertices weighted matching [El. Several implementations of Ed-
and edges, respectively. This was previously known monds’ algorithm have been proposed, with increas-
Abstract. only This forpaper
bipartite that the Itweighted
shows graphs. also shows match- optimization;
that a sequence detailed discussions are in [L,
ingly fast running times: O(n3) [G73, L], O(mn log n) LP, PS].
algorithm for
ing problemof m on ncageneraland graphs can be solved
link operations time can Edmonds
on nin nodes be pro- gave[BD, GMG],polynomial-time
the first O(n(m log Tog log 2++,n + n log n))
O(n(m + ncessed f or n in
log n)),on-line andtimem the number n)+n).
O(ma(m, of vertices This was previ- matching
weighted [El. Several implementations
‘[GGS]. Edmonds’ algorithm is a generalization of Ed- of the’
previouslytypeknown monds’ algorithm have been proposed, with increas-
and edges,ously known onlyThis
respectively. for was
a restricted of link operation. Hungarian algorithm, due to Kuhn, for weighted match-
O(n3) [G73, L], O(mn log n)
only for bipartite graphs. It also shows that a sequence ingly fast running ing ontimes: bipartite graphs [K55, K56]. Fredman and Tar-
of m nca and link operations on n nodes can be pro- [BD, GMG], O(n(m jan implement log Tog log the + n log n))
2++,nHungarian algorithm in O(n(m +
1. Introduction. This was previ- ‘[GGS]. Edmonds’ algorithm is a generalization of the’
cessed on-line in time O(ma(m, n)+n).
n logn)) time Kuhn, using for Fibonacci heaps [FT]. They ask if
ously known onlyThis for paper solvestype
a restricted two ofwell-known
link operation. problems Hungarian
in data algorithm, due to weighted match-
65 structures and gives some related results. The ing starting general matching can be done in this time. Our first
on bipartite graphs [K55, K56]. Fredman and Tar-
result is an affirmative 66
point is the matching problem for graphs, which jan
1. Introduction.
leads to
implement the Hungarian algorithmanswer: in O(n(m We show + that a search
the other problems. This section defines the problems
n logn)) time inusingEdmonds’
Fibonacci algorithm
heaps [FT].canThey be implemented
ask if in time
This paper solves two well-known problems in data
O(m can + nlogn).
be done This in thisimplies
time. that Our the first weighted match-
structures and and states
gives some the results.
related results. The starting general matching
point is the matching A maMing problem onforagraphs,
graph whichis a set leadsof to result
vertex-disjoint‘ is an ing
affirmative problem answer:can be
We solved
show in
that time
a search O(n(m + n log n)).
the other edges.
problems.Suppose each edge
This section e has
defines thea problems in
real-valued cosi c(e). Edmonds’ In both
algorithm cases
can the
be space
implementedis O(m). in Our
time implementation
and states The cost c(S) of a set of edges S is the sumO(m
the results. of +thenlogn). of This a search implies is inthat
some the sense
weighted optimal:
match-As shown in [FT]
individualon aedge
A maMing graphcosts.
is a set A ofminimum cost matching
vertex-disjoint‘ ing problem
is a for be
can Dijkstra’s time O(n(mone+ search
solved inalgorithm, n log n)). of Edmonds’ algo-
matching
edges. Suppose each of edgesmallest real-valuedcost.cosiThere
e has apossible c(e). are Ina both num- cases rithm the space can isbeO(m). used Our to sortimplementation
n numbers. Thus a search
The cost ber a set of edges
c(S) ofof variations: S is the cost of the
sum maximum of a search is in some sense optimal: As
requires time fI(m + n log n) in an appropriate shown in [FT] model of
a minimum cardinal-
matching is a for Dijkstra’s algorithm,
computation. one search of Edmonds’ algo-
individual ity edge costs. Ais minimum
matching a matchingcost with the greatest number
num-constraint rithm can be used to sort n numbers. Thus a search
matching of smallestpossible,
of edges There are
cost. subject
possible which to athis has Another algorithm for weighted matching is based
maximum cardinal- requires time fI(m + n log n) in an appropriate model of
ber of variations:
the smallest a minimumpossiblecostcost; minimum cost cardinality-
computation. on cost scaling. This approach is applicable if all costs
greatest number
ity matching is a matching
k matching (for awith giventhe integer k); maximum weight are integers. The best known time bound for such
of edges possible, which subject to this constraint has Another algorithm for weighted matching is based
matching; etc. The weighted matching problem refers a scaling algorithm is O(dncr(m, n) log n m log (ni’V))
the smallest possible cost; minimum cost cardinality- on cost scaling. This approach is applicable if all costs
to all of the problems in this list. [GT89]; here N is the largest magnitude of an edge cost
k matching (for a given integer k); maximum weight are integers. The best known time bound for such
In stating resource
matching; etc. The weighted matching problem refers
bounds for graph algorithms
a scaling algorithm is O(dncr(m, ofn)Ackermann’s
we and a is an inverse log n m log (ni’V)) function (see below).
assume throughout
to all of the problems in this list. this paper that the given graph has Under the similarity
[GT89]; here N is the largest magnitude of an assumption edge [GSSa]cost N 5 nOcl), this
n vertices
In stating resource andbounds
m edges. For notational
for graph algorithms simplicity
we andwea as- boundof is
is an inverse superior to function
Ackermann’s Edmonds’(seealgorithm.below). However our
sume m 2thisn/2.paper
assume throughout In the
that weighted
the given matching
graph has problem Underthis result is
the similarity still of interest
assumption [GSSa] for N 5atnOcl),least this two reasons: First,
can always be achieved by
n vertices and m edges. For notational simplicity we as- discarding isolated vertices. Edmonds’
bound is superior to Edmonds’ algorithm is
algorithm. theoretically
However ourattractive because
sume m 2 n/2. Weighted In the weightedmatchingmatching is a classic
problem problem
this in result
networkis still of it is strongly
interest for at polynomial.
least two Second,
reasons: First, for a number of
can always be achieved by discarding isolated vertices. Edmonds’ algorithm is theoretically attractive because
Weighted matching isofa classic
* Department Computerproblem
Science, is strongly
University it of
in network Boulder, for a number of
at Boulder, Second,
Colorado polynomial.
CO 80309. Research supported in part by NSF Grant No. CCR-8815636.
* Department of Computer Science, University of Colorado at Boulder, Boulder,
CO 80309. Research supported in part by NSF Grant No. CCR-8815636.
434

434