Shortest (A + B)-path packing via hafnian

arXiv:1603.08073v2 [math.CO] 13 Jun 2017

Hiroshi HIRAI and Hiroyuki NAMBA
Department of Mathematical Informatics,
Graduate School of Information Science and Technology,
The University of Tokyo, Tokyo, 113-8656, Japan.
hirai@mist.i.u-tokyo.ac.jp
hiroyukinannba@gmail.com

June 14, 2017
Abstract
Björklund and Husfeldt developed a randomized polynomial time algorithm
to solve the shortest two disjoint paths problem. Their algorithm is based on
computation of permanents modulo 4 and the isolation lemma. In this paper, we
consider the following generalization of the shortest two disjoint paths problem, and
develop a similar algebraic algorithm. The shortest perfect (A + B)-path packing
problem is: given an undirected graph G and two disjoint node subsets A, B with
even cardinalities, find shortest |A|/2 + |B|/2 disjoint paths whose ends are both in
A or both in B. Besides its NP-hardness, we prove that this problem can be solved
in randomized polynomial time if |A| + |B| is fixed. Our algorithm basically follows
the framework of Björklund and Husfeldt but uses a new technique: computation
of hafnian modulo 2k combined with Gallai’s reduction from T -paths to matchings.
We also generalize our technique for solving other path packing problems, and
discuss its limitation.
Keywords: shortest disjoint paths problem, hafnian, randomized polynomial
time algorithm

1

Introduction

The shortest two disjoint paths problem is: given an undirected graph G = (V, E) and
s1 , t1 , s2 , t2 ∈ V , find two disjoint paths, one connecting s1 and t1 and the other connecting s2 and t2 , such that the sum of their lengths is minimum. Although the length-less
version, the two disjoint paths problem, is elegantly solved [12, 13, 14], no polynomial
time algorithm was known for this generalization. Recently, Björklund and Husfeldt [2]
obtained the first polynomial time algorithm.
Theorem 1.1 ([2]). There exists a randomized polynomial time algorithm to solve the
shortest two disjoint paths problem.
Their algorithm is build on striking application of computation of permanents modulo 4 by Valiant [15] and the isolation lemma by Mulmuley–Vazirani–Vazirani [9].
1

In this paper, we consider a generalization of the shortest two disjoint paths problem
and develop a randomized polynomial time algorithm based on a similar algebraic technique. Let us introduce our problem. For T ⊆ V , a T -path is a path connecting distinct
nodes in T . We are given two disjoint terminal sets A and B with even cardinalities. A
perfect (A+B)-path packing is a set P of node-disjoint paths such that each path is an
A-path or B-path and |P| = |A|/2 + |B|/2. The size of a perfect (A + B)-path packing is
defined as the total sum of the length of each path, where the length of a path is defined
as the number of edges in the path. The shortest perfect (A + B)-path packing problem
asks to find a perfect (A + B)-path packing with minimum size. It will turn out that this
problem is NP-hard. In the case where |A| = |B| = 2, the problem is the shortest two
disjoint paths problem above. When B is empty, the problem is the disjoint A-path problem by Gallai [4]. Our main result says that the problem is tractable, provided |A| + |B|
is fixed.
Theorem 1.2. There exists a randomized algorithm to solve the shortest perfect (A+B)path packing problem in O(f (|V |)|A|+|B| ) time, where f is a polynomial.
Our algorithm basically follows the framework of Björklund–Husfeldt [2] but we use
a new technique: computation of hafnian modulo 2k , instead of permanent modulo 4,
combined with a classical reduction technique to matching by Gallai (for T -paths) [4]
and Edmonds (for odd path); see [11, Section 29.11e].
Related work Colin de Verdière–Schrijver [3] and Kobayashi–Sommer [7] gave combinatorial polynomial time algorithms for shortest disjoint paths problems in planar graphs
with special terminal configurations. Karzanov [6] and Hirai–Pap [5] showed the polynomial time solvability of a shortest version of edge-disjoint T -paths problem. Yamaguchi [16] reduced the shortest disjoint S-paths problem (nonzero T -paths problem
in a group labeled graph, more generally) to weighted matroid matching. Kobayashi–
Toyooka [8] developed a randomized polynomial time algorithm for the shortest nonzero
(s, t)-path problem in a group labeled graph; their algorithm is also based on the framework of Björklund–Husfeldt.
It is well-known that the hafnian of the adjacency matrix of a graph is equal to the
number of perfect matchings. By utilizing the hafnian, Björklund [1] developed a faster
algorithm to count the number of perfect matchings.
Organization The rest of this paper is organized as follows. In Section 2, we first
show that hafnian modulo 2k for fixed k is computable in polynomial time. This direct
generalization of permanent computation modulo 2k seems new and interesting in its own
right. Next we present the randomized algorithm in Theorem 1.2. In Section 3, we verify
the hardness of the (A + B)-path packing problem, and then generalize our technique for
solving other path packing problems, and discuss its limitation.

2

Algorithm

In this section, we first provide an algorithm to compute hafnian modulo 2k , and next
present a randomized polynomial time algorithm to solve the shortest perfect (A + B)path packing problem for fixed |A| + |B|. An undirected pair or edge {i, j} is simply
denoted by ij.
2

2.1

Computing Hafnian Modulo 2k

The hafnian haf A of a 2n × 2n symmetric matrix A = (aij ) is defined by
X Y
haf A :=
aij ,
M ∈M ij∈M

where M is the set of all partitions of {1, 2, 3, . . . , 2n} into n pairs.
Let S(n, N ) denote the set of all 2n × 2n symmetric matrices with zero diagonal each
of whose element is a univariate polynomial of degree at most N . Let haf 2k A denote the
hafnian of A modulo 2k . The main result of this subsection is the following:
Theorem 2.1. There exists a bivariate polynomial f such that for all A ∈ S(n, N ),
haf 2k A can be computed in O(f (n, N )k ) time.
We prove Theorem 2.1 by the similar way to that for permanents modulo 2k [15] and
that for permanents of polynomial matrices modulo 2k [2, 8]. First we verify Theorem 2.1
for k = 1. Let Ã = (ãij ) be a skew-symmetric matrix obtained from A by replacing aij
by −aij if i > j. Modulo 2, haf A coincides with pf Ã (Pfaffian
p of Ã). Hence haf 2 A can

be obtained in time polynomial in n and N by computing det Ã (mod 2).
Next, we consider the case of k ≥ 2. We use a formula like the Laplace expansion of
determinants. Let A[i, j] denote the matrix obtained from A by removing the row i, row
j, column i, and column j. For distinct i, j, p, q, let A[i, j, p, q] := (A[i, j])[p, q].
X
Lemma 2.2. (1) haf A =
aij haf A[i, j].
j: j6=i

X

(2) haf A = aij haf A[i, j] +

(aip ajq + aiq ajp ) haf A[i, j, p, q].

pq: p,q6∈{i,j},p6=q

Proof. (1) For j =
6 i, let Mj be the set of all M ∈ M that contain ij. Since {Mj | j 6= i}
is a partition of M, we obtain
Y
X
X
X
aij haf A[i, j].
aij
apq =
haf A :=
j: j6=i

M ∈Mj pq∈M \{ij}

j: j6=i

(2) By using (1) repeatedly, we obtain
X
X
aip haf A[i, p] = aij haf A[i, j] +
aip haf A[i, p]
haf A =
p: p6∈{i,j}

p: p6=i

= aij haf A[i, j] +

X

aip

p: p6∈{i,j}

= aij haf A[i, j] +

X

ajq haf A[i, j, p, q]

q: q6∈{i,j,p}

X

aip ajq haf A[i, j, p, q].

(p,q): p,q6∈{i,j},p6=q

Combining the terms for (p, q) and (q, p), we obtain (2).
For A ∈ S(n, N ), let A(i, j; c) denote the matrix obtained from A by adding c multiple
of column i to column j, adding c multiple of row i to row j, and replacing the jjth element
with zero. We refer to this operation as the (i, j; c)-operation. Note that differences
between A and A(i, j; c) occur only in row j and column j, and that A(i, j; c) also belongs
to S(n, N ). We investigate how the hafnian changes by the (i, j; c)-operation. Let A(i →
j) denote the matrix obtained from A by replacing row j with row i and column j with
column i.
3

Lemma 2.3. haf A(i, j; c) = haf A + c haf A(i → j).
Proof. Let ãpq denote the pqth element of A(i, j; c). We use Lemma 2.2 (1) with respect
to row j and column j.
X
haf A(i, j; c) =
ãkj haf A[k, j]
k:k6=j

=

X

akj haf A[k, j] +

k: k6=j

X

caki haf A[k, j]

k: k6=j

= haf A + c haf A(i → j).

Let d be a fixed positive integer. A term of a polynomial is said to be lower if its degree
is at most d and higher otherwise. A polynomial f is said to be even if all coefficients of
lower terms of the polynomial f (x) are even. For a polynomial f (x) that is not even, let
m(f (x)) denote the lowest degree of terms with odd coefficients.
Let A = (aij ) ∈ S(n, d). We are going to show that all lower terms of haf A modulo
2k can be computed in time polynomial in n and d. The hafnian does not change if we
exchange row i and row j, and column i and column j. Hence we exchange rows and
columns of A in advance so that a12 is a minimizer of m(a1j ) in a1j (j = 2, . . . , 2n) that are
not even. Next we find a polynomial cj such that cj a12 + a1j is even for j = 3, . . . 2n. The
computation can easily be done in time polynomial in n and d [2, Section 3.2]. Using the
(2, j; cj )-operation for j = 3, . . . 2n in order, we obtain matrices A3 := A(2, 3; c3 ), A4 :=
A3 (2, 4; c4 ), . . . , A2n := A2n−1 (2, 2n; c2n ). Then 1j elements of A2n are even if j ≥ 3.
Applying Lemma 2.3 repeatedly, we obtain
haf A2n = haf A +

2n
X

cj haf Aj−1 (2 → j),

j=3

where A2 = A. Using Lemma 2.2 (1) for A2n = (bij ), we obtain
haf A = b12 haf A2n [1, 2] +

2n
X

b1j haf A2n [1, j] −

j=3

2n
X

cj haf Aj−1 (2 → j).

(1)

j=3

Though there may be higher terms in elements of matrices in (1), we may replace these
higher terms with 0 (since our goal is computing lower terms). Similarly we may replace
higher terms in b1j (j = 2, . . . , 2n) with 0. Hence all matrices in right-hand side of (1)
can be regarded in S(n − 1, d) or S(n, d).
Next we discuss the second and third terms of the right-hand side in detail. For the
second term, we obtain b1j haf A2n [1, j] modulo 2k from haf A2n [1, j] modulo 2k−1 since
b1j (3 ≤ j ≤ 2n) are even. Therefore we need to compute hafnians of 2n − 2 polynomial
matrices in S(n − 1, d) modulo 2k−1 .
Next we consider the third term. For A(i → j), it holds aip = ajp , aiq = ajq and
aij = 0 (since A has zero diagonals). Hence, applying Lemma 2.2 (2) to A(i → j), we
obtain the following:
X
haf A(i → j) =
2aip ajq haf A[i, j, p, q].
p,q

4


Hence we obtain haf A(i → j) modulo 2k from hafnians of 2n−2
matrices in S(n − 2, d)
2
k−1
modulo 2 .
In this way, our algorithm recursively computes lower terms of haf A modulo 2k according to (1). We are now ready to prove Theorem 2.1.
Proof of Theorem 2.1. Let T (n, d, k) be the computational complexity of computing all
lower terms of the hafnian of a matrix in S(n, d). From (1) and the argument after (1),
it follows
T (n, d, k) ≤ T (n − 1, d, k) + (2n − 2)T (n − 1, d, k − 1)


2n − 2
+(2n − 2)
T (n − 2, d, k − 1) + poly(n, d),
2
where poly(n, d) is a polynomial of n and d. Since T (n, d, k) is monotone increasing on n,
it follows that
T (n, d, k) ≤ T (n − 1, d, k) + 4n3 T (n, d, k − 1) + poly(n, d).
Using this inequality repeatedly, we obtain
T (n, d, k) ≤ 4n4 T (n, d, k − 1) + poly(n, d).
T (n, d, 1) is a polynomial of n and d by the result of the case k = 1. Hence there exists
a polynomial f of n and d such that for all positive integers k, T (n, d, k) is O(f (n, d)k ).
For A ∈ S(n, N ), the degree of haf A is at most nN . Apply the above algorithm with
d = nN , we obtain haf 2k A in O(f (n, nN )k ) time. This completes the proof.

2.2

Perfect (A + B)-Path Packing via Hafnian

Let G = (V, E) be a simple undirected graph and A, B disjoint node sets of even cardinalities. Let n := |V | and m := |E|. We can assume that G = (V, E) has no edge with both
endpoints in A ∪ B; otherwise, replace each edge by a series of two edges. We consider a
general case where G has positive integer weight w(e) on each edge e. We assume that
the maximum value of the weight is bounded by a polynomial of n. For a path P , let
w(P ) denote the sum of the weight of edges in P . The size of a set P of vertex-disjoint
paths is defined as the total sum of w(P ) over P ∈ P, and is denoted by w(P).
Gallai’s construction From input G, A, B, we construct graph H = (VH , EH ) so that
matchings in H correspond to disjoint T -paths in G (with T = A ∪ B). This construction
is due to Gallai [4]; see [11, Section 73.1]. Let U := V \(A ∪ B). First we add to G a
copy of the subgraph of G induced by U . The copy of a node v ∈ U is denoted by v 0 .
Let U 0 := {v 0 | v ∈ U }, VH := V ∪ U 0 = A ∪ B ∪ U ∪ U 0 . Next, for each v ∈ U , add
an edge vv 0 . The set of such edges is denoted by E= . Finally, we add edge uv 0 for each
uv ∈ E with u ∈ A ∪ B, v ∈ U . The set of all edges in A ∪ B ∪ U 0 is denoted by E 0 . Let
EH := E ∪ E 0 ∪ E= . The weight w is extended to EH → Z≥0 by


if e ∈ E= ,
w(e) := 0
0
w(uv ) := w(uv) if uv 0 ∈ E 0 , u ∈ A ∪ B,


w(u0 v 0 ) := w(uv) if u0 v 0 ∈ E 0 , u0 , v 0 ∈ U 0 .
5

A perfect (A ∪ B)-path packing is a set of |A|/2 + |B|/2 node-disjoint (A ∪ B)-paths.
From a perfect matching M of H, we obtain a perfect (A ∪ B)-path packing PM in G as
follows. For all s ∈ A ∪ B, there exists a unique path P = {s, v1 , v2 , . . . , t} in H such that
(s, v1 ) ∈ M , t ∈ (A ∪ B)\{s} and it goes through edges in M and edges in E= alternately.
This path in H determines an (s, t)-path in G by picking up the only nodes in (A∪B)∪U
in the same order. Gathering up these paths, we obtain a perfect (A ∪ B)-path packing
PM in G. Conversely, one can see that any perfect (A ∪ B)-path packing in G is obtained
in this way. The size of PM is at most the weight of M . They coincide if and only if all
edges of M not used by PM belong to E= .
Matrices S and S 0 Next we introduce a symmetric matrix S associated with H. Let
h := |VH |. We can assume that VH = {1, 2, . . . , h}. Let S = (sij ) be an h × h symmetric
matrix defined by
(
xw(ij) if ij ∈ EH ,
sij :=
0
otherwise.
Recall that w(ij) denotes the weight of the edge ij in H.
For t ∈ A ∪ B, let Et denote the set of edges joining t and U , and let Et0 denote the
set of edges joining t and U 0 . From the matrix S, we define a new matrix S 0 = (s0ij ) by
(
−sij
s0ij :=
sij

if ij ∈ Et0 for some t ∈ B,
otherwise.

Let τ := (|A|+|B|)/2. For a perfect (A+B)-path packing P, let θ(P) denote the number
of even-length B-paths in P.
Lemma 2.4.
haf S 0 =

X
(−1)θ(P) 2τ xw(P) (1 + xfP (x)),
P

where P ranges over all perfect (A + B)-path packings, and fP (x) is a polynomial.
Q
Proof. For a matching M of H, let s0 (M ) := ij∈M s0ij . By the above discussion on
Gallai’s construction, we obtain
X
X X
haf S 0 =
s0 (M ) =
s0 (M ),
(2)
P

M

M :PM =P

where M ranges over all perfect matchings
P in H and P ranges over all perfect (A ∪ B)path packings in G. First we estimate M :PM =P s0 (M ). Suppose P = {P1 , . . . , Pτ }. For
each path Pk = (sk , v1 , v2 , . . . , vnk , tk ) (k = 1, . . . , τ ), we define two matchings Mk,1 , Mk,2
in H by
(
{sk v1 , v10 v20 , . . . , vnk −1 vnk , vn0 k tk } if nk is odd,
Mk,1 =
{sk v1 , v10 v20 , . . . , vn0 k −1 vn0 k , vnk tk } if nk is even,
(
{sk v10 , v1 v2 , . . . , vn0 k −1 vn0 k , vnk tk } if nk is odd,
Mk,2 =
{sk v10 , v1 v2 , . . . , vnk −1 vnk , vn0 k tk } if nk is even.

6

Both of them have weight w(P
Sτ k ). Then a perfect matching M with PM = P 0 can be
represented as the union of k=1 Mk,ik (ik ∈ {1, 2}) andSa perfect matching M of the
subgraph H − P of H obtained by removing vertices in τk=1 Mk,ik . Then we obtain
X
X
X X
s0 (M ) =
···
s0 (M1,i1 ) · · · s0 (Mτ,iτ )s0 (M 0 )
M :PM =P

i1 ∈{1,2}

iτ ∈{1,2} M 0

= (s0 (M1,1 ) + s0 (M1,2 )) · · · (s0 (Mτ,1 ) + s0 (Mτ,2 ))

X

s0 (M 0 ),

(3)

M0

where M 0 ranges over all perfect matchings of H − P.
Next we estimate s0 (Mk,1 ) + s0 (Mk,2 ). We call an edge in Et0 for t ∈ B minus. Then
s0 (Mk,j ) = xw(Pk ) if Mk,j has an even number of minus edges, and s0 (Mk,j ) = −xw(Pk ) if
Mk,j has an odd number of minus edges. If Pk connects A and B, just one of Mk,1 and
Mk,2 contains one minus edge. If Pk is an A-path, then neither Mk,1 nor Mk,2 contains
one minus edge. If Pk is a B-path and the length of Pk is odd, one of Mk,1 and Mk,2 has
two minus edges and the other has no minus edge. If Pk is a B-path and the length of Pk
is even, both of Mk,1 and Mk,2 have one minus edge. (Recall the assumption that there
is no edge joining A ∪ B.) Hence we obtain


if Pk connects A and B,
0
0
0
(4)
s (Mk,1 ) + s (Mk,2 ) = −2xw(Pk ) if Pk is an even-length B-path,

 w(Pk )
2x
otherwise.
P
Finally we estimate M 0 s0 (M 0 ). The perfect matching consistingP
of edges in E= has
weight 0, and other perfect matchings have weight at least 1. Thus M 0 s0 (M 0 ) is represented as 1 + xf (x) for a polynomial f . By this fact and equations (2), (3) and (4), we
obtain the formula.
Unique Optimal Solution Case. We first consider the case where G has a unique
shortest perfect (A + B)-path packing P ∗ . Here w is not necessarily uniform (but is
bounded by a polynomial of n). In this case, Lemma 2.4 immediately yields a desired algorithm to find P ∗ . Indeed, the leading term (lowest degree term) of haf S 0 is
∗
∗
(−1)θ(P ) 2τ xw(P ) (by the uniqueness). In particular we can obtain the minimum degree
w(P ∗ ) by computing haf S 0 modulo 2τ +1 . Observe that an edge e belongs to P ∗ if and
only if the degree of the leading term of haf S 0 strictly increases when e is removed from
G. Thus we can determine P ∗ by m + 1 computations of the hafnian of a 2n × 2n matrix in modulo 2τ +1 . By Theorem 2.1 (with N = maximum of w), this can be done in
O(f (n)|A|+|B| ) time for a polynomial f .
General Case. Suppose now that w is uniform weight, i.e., w(e) = 1 for all e in E. We
consider the general case where there may be two or more shortest perfect (A + B)-path
packings. We construct a randomized polynomial time algorithm with the help of the
isolation lemma [9]. This technique is due to [2]. We use the isolation lemma in the
following form:
Lemma 2.5. Let n be a positive integer and F a family of subsets of E = {e1 , . . . , em }.
Weight w(ei ) is assigned to each element ei of E, where w(ei ) are chosen independently
and uniformly at random from {2mn, 2mn+1, . . . , 2mn+2m−1}. Then, withP
probability
greater than 1/2, there exists a unique set F ∈ F of minimum weight w(F ) := e∈F w(e).
7

We are ready to prove our main theorem.
Proof of Theorem 1.2. We perturb the weight w into w0 so that a shortest packing for w0 is
unique and is also shortest for w. For each edge e, choose a from {2mn, . . . , 2mn+2m−1}
independently and uniformly at random, and let w0 (e) := a. By Lemma 2.5, with a high
probability (≥ 1/2), a shortest (A + B)-path packing P ∗ for w0 is unique. By the unique
optimal solution case above, we can find P ∗ in O(f (n)|A|+|B| ) time. We finally verify
that P ∗ is actually shortest for the original uniform weight w. Indeed, pick an arbitrary
packing P not equal to P ∗ . Then we have
1 ≤ w0 (P) − w0 (P ∗ ) ≤ (2mn + 2m − 1)w(P) − 2mnw(P ∗ )
≤ 2mn(w(P) − w(P ∗ )) + (2m − 1)w(P).
Hence we have
w(P) − w(P ∗ ) ≥

(2m − 1)w(P)
1 + w(P)
1
−
≥ −1 +
> −1,
2mn
2mn
2mn

where the second inequality follows from w(P) ≤ n. Since both w(P) and w(P ∗ ) are
integers, we have w(P) − w(P ∗ ) ≥ 0. This means that P ∗ is shortest for w.

3
3.1

Related Results
NP-Completeness

Here we verify that the perfect (A + B)-path packing problem, the problem of deciding
the existence of a perfect (A + B)-path packing (with |A| + |B| unfixed), is intractable.
Theorem 3.1. The perfect (A+B)-path packing problem is NP-complete, even if |B| = 2.
Proof. Hirai and Pap [5] proved that the following edge-disjoint paths problem is NPcomplete: (∗) Given an undirected graph G = (V, E) and S, T ⊆ V with S ∩ T = ∅ and
|S| = |T | = k and a, b ∈ V \ (S ∪ T ), find an edge-disjoint set P of paths P0 , P1 , . . . , Pk
such that P0 connects a and b and Pi connects S and T (i = 1, 2, . . . , k). They gave a
reduction from 3-SAT to the problem (∗). In their reduction [5, Section 5.2.3], a solution
is necessarily vertex-disjoint. Moreover, one can see from the reduction that a set P of
paths is a solution of (∗) if and only if P is a perfect (S ∪ T + {a, b})-path packing.
Consequently the perfect (A + B)-path packing problem is also NP-complete, even if
|B| = 2.

3.2

Other Path Packing via Hafnian

In this subsection, we generalize our technique for solving other path packing problems
and discuss its limitation. Let G = (V, E) be a simple undirected graph. Let T be a
terminal set with even cardinality |T | = 2τ . As in Section 2.2, we assume that there is
no edge joining T .
To specify path packing problems, we introduce a notion of perfect matching with
parity (PMP) on T , which is defined as a set of pairs (si ti , σi ) (i = 1, . . . , τ ) such that
S
i {si , ti } = T and σi ∈ {odd, even} is a parity. A perfect T -path packing P (a disjoint
set of τ T -paths) induces PMP MP :
MP := {(st, σ) | P has an (s, t)-path with its length having the parity σ}.
8

For a set M of PMPs, a perfect M-path packing is a perfect T -path packing with
MP ∈ M. We introduce the shortest perfect M-path packing problem as the problem
of finding a perfect M-path packing of minimum size. Notice that an (A + B)-path
packing corresponds to MA+B := {M ∪ M 0 | M :PMP on A, M 0 :PMP on B}.
Next we consider a generalization of matrix S 0 . As in Section 2.2, consider graph H,
edge sets Et and Et0 , and matrix S (with A ∪ B = T ). Suppose that T = {1, 2, 3, . . . , 2τ }.
For p = (p1 , . . . , p2τ ), q = (q1 , . . . , q2τ ) ∈ Z2τ , we define the matrix S[p, q] from S by


pt sij if ij ∈ Et for t ∈ T,
(S[p, q])ij := qt sij if ij ∈ Et0 for t ∈ T,


sij
otherwise.
For distinct s, t ∈ T and parity σ, define [p, q]st,σ by
(
ps pt + qs qt if σ = odd,
[p, q]st,σ :=
ps qt + qs pt if σ = even.
A set M of PMPs is said to be h-representable if there exist N, k ∈ Z>0 , ni ∈ Z≥0 ,
pi , q i ∈ Z2τ for i = 1, . . . , N such that a PMP M belongs to M if and only if
N
X

ni

i=1

Y

[pi , q i ]st,σ 6≡ 0 mod 2k .

(st,σ)∈M

In particular, the argument in Section 2.2 says that MA+B is h-representable with N = 1,
k = τ + 1, n1 = 1, p1 = (1, 1, . . . , 1) and q 1 = (1, . . . , 1, −1, . . . , −1). That is, q 1 has 1 for
the first |A| entries and −1 the remaining |B| entries. A generalization of Theorem 1.2
is the following.
Theorem 3.2. Suppose that a set M of PMPs is h-representable with parameters N, k, ni ,
pi , q i (i = 1, 2, . . . , N ). Then the shortest perfect M-path packing problem can be solved
in randomized polynomial time, provided N and k are fixed.
Proof. As in the proof of Lemma 2.4, one can show


N
N
X
X X
Y

ni
[pi , q i ]st,σ  xw(P) (1 + xfP (x)),
ni haf S[pi , q i ] =
i=1

P

i=1

(st,σ)∈MP

where P ranges over all perfect T -path packings. Therefore, if G hasPa unique shortest
i i
perfect M-path packing P ∗ , then we can obtain P ∗ by computing N
i=1 ni haf S[p , q ]
modulo 2k . This can be done in polynomial time provided N and k are fixed. As in Section
2.2, we obtain the randomized polynomial time algorithm for the general case.
We do not know a characterization of h-representable sets of PMPs. We here discuss three interesting special cases, where odd and even are simply denoted by o and e
respectively.

9

Shortest two disjoint paths via hafnian modulo 4. First we return to the shortest
two disjoint paths problem, which corresponds to T = {1, 2, 3, 4} and
M2 := {{(12, σ1 ), (34, σ2 )} | σ1 , σ2 ∈ {o, e}}.
We have seen that M2 is h-representable with N = 1 = n1 = 1, p1 = (1, 1, 1, 1),
q 1 = (1, 1, −1, −1), and k = 3. We present another economical h-representation.
Proposition 3.3. M2 is h-representable with N = 1, k = 2, n1 = 1, p1 = (1, 1, 1, 1),
and q 1 = (0, 1, −1, −1).
Proof. A direct calculation (e.g.,[p1 , q 1 ]12,e [p1 , q 1 ]34,o = (1·1+0·1){1·1+(−1)·(−1)} = 2)
shows


if M = {(12, o), (34, o)}, {(12, e), (34, o)},
2
Y
1 1
[p , q ]st,σ = −2 if M = {(12, o), (34, e)}, {(12, e), (34, e)},


(st,σ)∈M
0
otherwise.

In particular, modulo 4 computation is sufficient. It might be interesting to compare
with the original approach by Björklund–Husfeldt [2]: their algorithm requires to compute permanents of three n × n matrices modulo 4, whereas our algorithm with these
parameters requires to compute the hafnian of one 2n × 2n matrix modulo 4.
Shortest odd two disjoint paths via four hafnians modulo 4. The hafnian approach can solve the shortest two disjoint paths problem with a parity constraint that
the sum of the lengths of paths is odd. This problem corresponds to T = {1, 2, 3, 4} and
M2,odd := {{(12, o), (34, e)}, {(12, e), (34, o)}}.
Theorem 3.4. M2,odd is h-representable with N = 4, k = 2, (n1 , n2 , n3 , n4 ) = (1, 1, −1, −1),
and
p1 = (1, 1, 1, 0),
p2 = (1, 1, 0, 1),
p3 = (1, 0, 1, 1),
p4 = (0, 1, 1, 1),

q 1 = (0, 0, 0, 1),
q 2 = (0, 0, 1, 0),
q 3 = (0, 1, 0, 0),
q 4 = (1, 0, 0, 0).

Proof. One can verify the theorem from the value of Ci :=
1, 2, 3, 4 and all PMPs M on T , which are shown in Table 1.

Q

(st,σ)∈M [p

i

, q i ]st,σ for i =

Non h-representability of 3-disjoint paths. A deep result by Robertson–Seymour [10]
is that the k-disjoint paths problem is solvable in polynomial time (for fixed k) . One
may naturally ask whether the shortest k-disjoint paths problem for k ≥ 3 is solvable
by this approach. Unfortunately our approach cannot reach the shortest 3-disjoint paths
problem, which corresponds to T = {1, 2, 3, 4, 5, 6} and
M3 := {{(12, σ1 ), (34, σ2 ), (56, σ3 )} | σ1 , σ2 , σ3 ∈ {o, e}}.
Theorem 3.5. M3 is not h-representable.
10

PMP
{(12, o), (34, o)}
{(12, o), (34, e)}
{(12, e), (34, o)}
{(12, e), (34, e)}
{(13, o), (24, o)}
{(13, o), (24, e)}
{(13, e), (24, o)}
{(13, e), (24, e)}
{(14, o), (23, o)}
{(14, o), (23, e)}
{(14, e), (23, o)}
{(14, e), (23, e)}

Table
C1
0
1
0
0
0
1
0
0
0
0
1
0

1: Values of Ci .
C2 C3 C4 C1 + C2 − C3 − C4
0
0
0
0
1
0
0
2
0
1
1
-2
0
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
0
0
0

We start with a preliminary argument. Let 1 := (1, 1, . . . , 1). For χ ∈ {0, 1}2τ , let
S(χ) := S[χ, 1 − χ]. Then haf S[p, q] can be expressed as a linear combination of haf S(χ)
over χ ∈ {0, 1}2τ :
Lemma 3.6. haf S[p, q] =

X

2τ
Y

{χi pi + (1 − χi )qi } haf S(χ).

χ∈{0,1}2τ i=1

Proof. Each perfect matching of H determines χ ∈ {0, 1}2τ as: χi = 1 if and only if
node i is matched to a node in U . Here χ is called the type of M . We classify all perfect
matchings in terms of their types. One can verify
" 2τ
#
X Y
Y
(S[p, q])ij =
{χi pi + (1 − χi )qi } haf S(χ).
M :type χ ij∈M

i=1

Thus we have the desired formula.
From Lemma 3.6, in the definition of h-representability,Qit suffices to consider the case
where p = χ and q = 1 − χ for χ ∈ {0, 1}2τ . In this case, (st,σ)∈M [p, q]st,σ is 0 or 1. Let
[χ]st,σ := [χ, 1 − χ]st,σ .
Proof of Theorem 3.5. First consider the following six PMPs:
M1 := {(12, o), (34, o), (56, e)}, M2 := {(12, o), (36, o), (45, e)},
M3 := {(14, o), (23, o), (56, e)}, M4 := {(14, o), (36, o), (25, e)},
M5 := {(16, o), (23, e), (45, o)}, M6 := {(16, o), (34, e), (25, o)}.
Observe that M1 is in M3 and other five PMPs are not in M3 . For PMP M and
χ ∈ {0, 1}6 , define bM,χ by
Y
bM,χ :=
[χ]st,σ .
(st,σ)∈M

By computer calculation, we have verified the following 64 equations to hold;
bM1 ,χ = bM2 ,χ + bM3 ,χ − bM4 ,χ + bM5 ,χ − bM6 ,χ
11

(χ ∈ {0, 1}6 ).

(5)

Next suppose that M3 is h-representable. Thanks to Lemma 3.6, there exist k ∈ Z>0
and nχ ∈ Z for χ ∈ {0, 1}6 such that a PMP M belongs to M if and only if
X
Y
nχ
[χ]st,σ 6≡ 0 mod 2k .
χ∈{0,1}6

(st,σ)∈M

In particular, it holds
X

nχ bMj ,χ ≡ 0

mod 2k (j = 2, 3, 4, 5, 6).

χ∈{0,1}6

By (5), we have
X

nχ bM1 ,χ ≡ 0

mod 2k .

χ∈{0,1}6

However this is a contradiction to M1 ∈ M3 .

Acknowledgments
We thank the referees for helpful comments. The work was partially supported by JSPS
KAKENHI Grant Numbers 25280004, 26330023, 26280004, 17K00029.

References
[1] A. Björklund: Counting perfect matchings as fast as Ryser, Proceedings of the
Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New
York, (2012), 914–921.
[2] A. Björklund and T. Husfeldt: Shortest two disjoint paths in polynomial time, Proceedings of 41st International Colloquium on Automata, Languages, and Programming,
Lecture Notes in Computer Science 8572, Springer-Verlag, Berlin, (2014), 211–222.
[3] É. Colin de Verdière and A. Schrijver: Shortest vertex-disjoint two-face paths in
planar graphs. ACM Transactions on Algorithms 7 (2011), No. 19, 12 pp.
[4] T. Gallai: Maximum-minimum Sätze und verallgemeinerte Faktoren von Graphen,
Acta Mathematica Academiae Scientiarum Hungaricae 12, (1961), 131–173.
[5] H. Hirai and G. Pap: Tree metrics and edge-disjoint S-paths, Mathematical Programming 147, (2014), 81–123.
[6] A. Karzanov: Edge-disjoint T-paths of minimum total cost, Technical Report, STANCS-92-1465, Department of Computer Science, Stanford University, Stanford, California, 1993, Available at http://alexander-karzanov.net/.
[7] Y. Kobayashi and C. Sommer: On shortest disjoint paths in planar graphs. Discrete
Optimization 7, (2010), 235–245.
[8] Y. Kobayashi and S. Toyooka: Finding a shortest non-zero path in group-labeled
graphs, Algorithmica 77, (2017), 1128–1142.
12

[9] K. Mulmuley, U. V. Vazirani and V. V. Vazirani: Matching is as easy as matrix
inversion, Combinatorica 7, (1987), 105–113.
[10] N. Robertson and P. D. Seymour: Graph minors. XIII. The disjoint paths problem,
Journal of Combinatorial Theory, Series B 63, (1995), 65–110.
[11] A. Schrijver: Combinatorial Optimization. Polyhedra and Efficiency, SpringerVerlag, Berlin, 2003.
[12] P. D. Seymour: Disjoint paths in graphs, Discrete Mathematics 29, (1980), 293–309.
[13] Y. Shiloach: A polynomial solution to the undirected two paths problem, Journal of
the ACM 27, (1980), 445–456.
[14] C. Thomassen: 2-linked graphs, European Journal of Combinatorics 1, (1980), 371–
378.
[15] L. G. Valiant: The complexity of computing the permanent, Theoretical computer
science, 8, (1979), 189–201.
[16] Y. Yamaguchi: Shortest disjoint non-zero A-paths via weighted matroid matching, Proceedings of the 27th International Symposium on Algorithms and Computation,
(2016), No. 63, 13 pp.

13

