K-Best Solutions of MSO Problems on
Tree-Decomposable Graphs
David Eppstein1 and Denis Kurz2
1
2

Computer Science Department, UC Irvine, USA
eppstein@uci.edu
Department of Computer Science, TU Dortmund, Germany
denis.kurz@tu-dortmund.de

arXiv:1703.02784v1 [] 8 Mar 2017

Abstract
We show that, for any graph optimization problem in which the feasible solutions can be expressed
by a formula in monadic second-order logic describing sets of vertices or edges and in which the
goal is to minimize the sum of the weights in the selected sets, we can find the k best solutions
for n-vertex graphs of bounded treewidth in time O(n + k log n). In particular, this applies to
the problem of finding the k shortest simple paths between given vertices in directed graphs of
bounded treewidth, giving an exponential speedup in the per-path cost over previous algorithms.
1998 ACM Subject Classification G.2.2 Graph Theory
Keywords and phrases graph algorithm, k-best, monadic second-order logic, treewidth
Digital Object Identifier 10.4230/LIPIcs...

1

Introduction

Finding multiple alternative routes between a given pair of vertices in a network, formalized
as the k shortest paths problem, has a huge number of applications including biological
sequence alignment, metabolic pathway reconstruction, hypothesis generation in natural
language processing, computer network routing, and vehicle routing [13]. When the input
network is a directed acyclic graph, it can be solved in constant time per path, after a
preprocessing stage whose time is bounded by the time for a single-source shortest path
problem [12]. However, for graphs with cycles, this algorithm may find paths with repeated
vertices, which are undesirable in many applications. A variant of the problem that disallows
these repetitions, the k shortest simple paths problem, has also been studied, but for the past
45 years there have been no asymptotic improvements to an algorithm of Yen, which takes
quadratic time per path [21]. Indeed, a reduction of Vassilevska Williams and Williams
suggests that, at least for the case k = 2, no substantial improvement to this algorithm
is possible for arbitrary directed graphs [20]. Even for the easier case of k shortest simple
paths in an undirected graph, known algorithms take the time of a single-source shortest
path computation per path [18], far from the constant time per path that can be attained
when paths are not required to be simple.
This situation suggests studying classes of graphs for which faster k-best optimization
algorithms are possible. In this paper we provide a first result of this type, showing that the
k shortest simple paths can be found in logarithmic time per path (an exponential speedup
over the per-path time of previous algorithms) for the graphs of bounded treewidth. Our
results are based on general algorithmic metatheorems that have been developed for these
graphs, and in particular on Courcelle’s theorem, according to which a wide class of decision
and optimization problems expressible in the monadic second-order logic of graphs (MSO)
licensed under Creative Commons License CC-BY
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

XX:2

K-Best Solutions of MSO Problems on Tree-Decomposable Graphs

can be solved in linear time on graphs of bounded treewidth. MSO is a form of logic
in which the variables of a formula represent vertices, edges, sets of vertices, and sets of
edges of a graph, one can test set membership and vertex–edge incidence, and variables
can be existentially or universally quantified. For instance the property that an edge set P
represents a simple path from s to t can be expressed in MSO as a formula
h

i
(∀v, e, f, g) I(v, e) ∧ e ∈ P ∧ I(v, f ) ∧ f ∈ P ∧ I(v, g) ∧ g ∈ P ⇒ e = f ∨ e = g ∨ f = g


h
i
∧ (∃e) I(s, e) ∧ e ∈ P ∧ (∀f ) I(s, f ) ∧ f ∈ P ) ⇒ e = f


h
i
∧ (∃e) I(t, e) ∧ e ∈ P ∧ (∀f ) I(t, f ) ∧ f ∈ P ) ⇒ e = f
h




∧ (∀S) ¬(∃v, e) v ∈ S ∧ e ∈ P ∧ I(v, e) ∨ ¬(∃v, e) ¬(v ∈ S) ∧ e ∈ P ∧ I(v, e) ∨

i
(∃v, w, e) v ∈ S ∧ ¬(w ∈ S) ∧ I(v, e) ∧ I(w, e)
(where s, t, v and w are vertex variables, e, f , and g are edge variables, S is a vertexset variable, and I is the vertex–edge incidence predicate). This formula expresses the
constraints that each vertex is incident to at most two edges of P , s and t are each incident
to exactly one edge of P , and every partition of the vertices that is not crossed by P has P
only on one of its two sides.
Courcelle’s theorem provides a translation from MSO formulas to tree automata, allowing
graphs of bounded treewidth that satisfy the formula to be recognized in linear time by a
bottom-up dynamic programming algorithm that executes the tree automaton on a treedecomposition of the given graph. Arnborg, Lagergren and Seese [2] and Courcelle and
Mosbah [9] gave extensions of this method that also solve optimization problems for MSO
predicates (formulas with one unbound set-variable) that seek the minimum weight vertex
set or edge set obeying the given predicate, on a weighted graph of bounded treewidth. For
instance, it could be used to find shortest simple paths on bounded-treewidth graphs with
negative edges and negative cycles, a problem that is NP-hard on arbitrary graphs.
In this paper, we show that, for any MSO predicate, the k minimum-weight sets satisfying
the predicate can be found on graphs of bounded treewidth in logarithmic time per set.
In particular, using the formula given above, we can find the k shortest simple paths in
logarithmic time per path. Other previously-studied graph optimization problems to which
our method applies (and provides an exponential per-solution speedup) include finding the
k smallest spanning trees [14], the k best matchings [7], and (with a doubly exponential persolution speedup) the k best solutions to the traveling salesperson problem [19]. Although
the example formula above describes simple paths in undirected graphs, our method applies
equally well to directed graphs as long as the undirected graph obtained by forgetting the
edge orientations has bounded treewidth.
Our method uses a special tree-decomposition, one that continues to have bounded width
but also has logarithmic depth and bounded degree. We translate the dynamic programming
algorithm for finding the minimum weight set satisfying a given MSO predicate into a fully
persistent dynamic graph algorithm for the same optimization problem, one that can report
the minimum weight solution after modifying the given graph by changing the weights of
some of its edges or vertices. We apply this method to find the second-best (rather than
best) solution, and to detect a feature of the graph (a vertex or edge) at which the best
and second-best solution differ. By branching on this feature (using the dynamic graph
algorithm to delete it in one subproblem and force it to be included in another) we can

David Eppstein and Denis Kurz

recursively decompose the original problem into a hierarchy of subproblems whose secondbest solutions (together with the global best solution) include all of the k best solutions
to the input problem. To find the k best solutions, we perform a best-first search of this
hierarchy.

2

Preliminaries

In this section, we establish most of our notation and definitions, and review algorithmic
components from previous research that we will use to establish our results.
We denote by [i] the set {1, . . . , i} for i ∈ N. The cardinality of a set M is denoted by
|M |, its power set by 2M . For a function f : M → N , we write f (M 0 ) = {f (a) | a ∈ M 0 } for
M 0 ⊆ M . For an n-element sequence S and i ∈ [n], we denote the i-th element of S by Si .
Our algorithms assume a RAM model of computation in which addition and comparison
operations on input weights or sums of weights can be performed in constant time per
operation.

2.1

Binary heap of subproblems

We adopt the following technique for finding the k best solutions to a combinatorial optimization problem. The technique was first used by Gabow for finding the k smallest
spanning trees [16], and is surveyed by Hamacher and Queyranne [17] and Eppstein [13].
We assume that the problem to be solved has solutions that can be represented as a set
of edges or vertices in a given weighted graph G, and that the goal is to minimize the total
weight of a solution. We may define a subproblem of this problem by forcing certain edges
or vertices to be included in the solution and preventing certain other edges or vertices from
being included; alternatively, these constraints can be simulated without changing the graph
structure by changing the weights of the forced edges or vertices to a large negative number
and by changing the weights of the excluded edges or vertices to a large positive number.
We say that a subproblem is feasible if there exists a solution to the given problem that is
consistent with its constraints. If S is any subproblem, then we may consider two solutions
to S, its best solution (the one with the minimum weight, subject to the constraints of S)
and its second-best solution (the one that differs from the best solution and otherwise has
the minimum possible weight), with ties broken in any consistent way. We say that an edge
or vertex is a pivot feature if it is present in the best solution but absent in the second-best
solution, or vice versa. If a subproblem has only a single solution, then we say that it is
uniquely solvable.
We then form a binary tree of feasible subproblems, as follows. The root of the tree is
the subproblem with no constraints (the one whose solutions are all solutions to the given
problem on the whole graph G). Then, for each subproblem S in the tree that is not
uniquely solvable, the two children of S are determined by choosing (arbitrarily) a pivot
feature of S, constraining that pivot feature to be included in the solutions for one child,
and constraining the same pivot feature to be excluded from the solutions for the other
child. These two children of S have solution sets that partition the solutions of S into two
nonempty subsets, one containing the best solution and the other containing the second-best
solution. A uniquely solvable subproblem in this tree of subproblems forms a leaf, with no
children.
Each solution of the given problem on G appears as the second-best solution of exactly
one subproblem in this binary tree of subproblems, except for the global best solution which

XX:3

XX:4

K-Best Solutions of MSO Problems on Tree-Decomposable Graphs

is never the second-best solution of any subproblem. The tree is ordered as a binary minheap according to the values of the second-best solutions at each subproblem of the tree:
the second-best solution of any subproblem is always better than the second-best solutions
of its two children. Therefore, the k-best solutions of the original problem can be found by
outputting the best solution and then performing a best-first search in the tree of subproblems to find the k − 1 subproblems whose second-best solutions have the smallest values.
This best-first search can be performed by evaluating O(k) subproblems (finding their best
solutions, second-best solutions, and a pivot feature) after using a priority queue of subproblems (prioritized by their second-best solution values) to select each successive subproblem
to evaluate in O(log k) time per subproblem. Alternatively, a more complex heap-selection
algorithm of Frederickson [15] can be used to find the k − 1 best subproblems in the tree
using (again) O(k) evaluations of subproblems but only O(1) overhead per subproblem to
select each successive subproblem to evaluate.
Using this method, the main remaining task is to show how to find the second-best solution values and pivot features of each subproblem in this tree of subproblems, as efficiently
as possible.

2.2

Path-copying persistence

We will develop a data structure that allows us to add a new constraint to a subproblem,
forming one of its child subproblems, and efficiently compute the new second-best solution
value of the new child subproblem. However, without additional techniques such a data
structure would allow us to follow only a single branch of the tree of subproblems. We use
ideas from persistent data structures, following Sarnak et al. [10], to extend these data structures to ones that let us explore multiple branches of the tree of subproblems concurrently.
An ephemeral data structure is one that has only a single version, which is changed by
certain update operations and accessed but not changed by additional query operations. In
the corresponding fully persistent data structure, each operation takes an additional argument, the version of the data structure, and operates on that version. Persistent queries
return the result of the query on that version, and do not change it. Persistent updates
create and return a new version of the data structure, in which the given change has been
made to the version given as an argument. The previous version is left intact, so that future
updates and queries can still be made to it.
Path copying is a general technique introduced by Sarnak et al. for converting any treebased ephemeral data structure (such as a binary heap or binary search tree) into a fully
persistent structure for the same problem. In order for it to be applicable, the underlying
ephemeral data structure must consist of a tree of nodes, with each node pointing to its
children in the tree (along with, possibly other information used as part of updates and
queries), but without pointers to parents or other non-child nodes. Every operation in the
ephemeral data structure should be performed by starting at the tree root, following child
pointers to find additional nodes reachable by paths from the root, and then (in case of
a query) collecting information from those nodes or (in case of an update) changing or
replacing some or all of the reached nodes.
To make such a data structure fully persistent, we represent each version of the data
structure by the root node of its tree. Persistent queries are handled by exactly the same
algorithm as ephemeral queries, starting from the root node representing the desired version
of the data structure. When an ephemeral update would change or replace some subset of
the nodes reached during the update, the persistent structure instead creates new nodes for
all of these changed or replaced nodes and all of their ancestors, without making any changes

David Eppstein and Denis Kurz

to the existing nodes. In this way, the space and time requirements of each persistent update
are proportional to the time for an ephemeral update.
Path-copying persistence was already used in the k-shortest paths algorithm of Eppstein [12], as part of the construction of certain persistent heap structures used to represent
sets of detours in the given graph. Here, we apply the same technique in a different way, to
make an ephemeral data structure for second-best solutions persistent. We will associate a
version of the second-best solution data structure with each subproblem in the binary tree
of subproblems described in the previous section. Then, when we expand a subproblem
(finding its pivot feature and using that feature to define two new child subproblems) the
data structure versions of the two child subproblems can be found by applying two different
persistent updates to the version of their parent.

2.3

Shallow tree decompositions

The data structure to which we will apply the path-copying persistence technique will be
based on a tree decomposition of the given graph. However, in order to make the pathcopying efficient, we need to use a special kind of tree decomposition, one with low depth.
A tree decomposition of a graph G = (V, E) is a pair (T = (U, F ), bag), where T is a tree,
bag : U → 2V maps tree nodes to subsets of V , and the following conditions are met:
S
V = bag(U ),
for each e = (v, w) ∈ E, there is some u ∈ U with {v, w} ⊆ bag(u), and
for each u, u0 , u00 , if u0 is on the path from u to u00 in T , we have bag(u)∩bag(u00 ) ⊆ bag(u0 ).
The width of a tree decomposition is one less than the size max{|bag(u)| | u ∈ U } of its largest
bag. The treewidth of a graph G is the smallest w such that G has a tree decomposition of
width w. For any fixed w, one can recognize the graphs of treewidth at most w and compute
a tree decomposition of optimal width for these graphs, in linear time, using an algorithm
of Bodlaender [5].
We define the depth of a tree decomposition to be the longest distance from a leaf to
a root node chosen to minimize this distance. A shallow tree decomposition of a graph
G of bounded treewidth w is a tree decomposition with width O(w) and depth O(log |G|)
whose tree is binary. Bodlaender [4] showed that a shallow tree decomposition always exists,
and that it can be constructed by a PRAM with O(|G|3w+4 ) processors in O(log |G|) time.
The shallow tree decomposition algorithm of Bodlaender and Hagerup [6] with O((log |G|)2 )
running time on an EREW PRAM can be simulated by a RAM in O(|G|) time.

2.4

Hypergraph algebra

We adopt much of the following notation from Courcelle and Mosbah [9].
Let A be a ranked alphabet consisting of edge labels, and let τ : A → N map labels to
their orders. A hypergraph G = (V, E, lab, vert, src) of order r consists of a set of vertices V
and a set of hyperedges E, an edge labeling function lab : E → A, a function vert : E → V ∗
that maps edges to node sequences, and a sequence src of r source nodes. The order of a
hyperedge e ∈ E is the length |vert(e)| of its vertex sequence, and must match the order
of its label: τ (lab(e)) = |vert(e)|. A graph of order r is a hypergraph of order r with
τ (lab(E)) = {2}, so every hyperedge has order 2. Hyperedges of a graph may be called
edges.
We define, for an edge label alphabet A, a hypergraph algebra with a possibly infinite set
of hypergraph operators and the following finite set of constants. The constant 0 denotes
the empty hypergraph of order 0. The constant 1 denotes the hypergraph of order 1 with

XX:5

XX:6

K-Best Solutions of MSO Problems on Tree-Decomposable Graphs

a single source vertex and no hyperedges. For each a ∈ A, the constant a denotes the
hypergraph of order τ (a) with node set {v1 , . . . , vτ (a) }, a single hyperedge e with lab(e) = a
and vert(e) = (vi )i∈[τ (a)] , and src = vert(e).
Let G be a hypergraph of order r and let G0 be a hypergraph of order r0 . The hypergraph
algebra has the following operators. The (r + r0 )-order hypergraph G ⊕r,r0 G0 consists of
the disjoint union of the vertex and edge sets of G and G0 , and the concatenation of their
source sequences. For each i, j ∈ [r], θi,j,r (G) is the hypergraph of order r obtained from
G by replacing every occurence of srcj with srci in the source sequence of G and in every
vertex sequence of a hyperedge of G. For a mapping α : [p] → [r], σα (G) is the hypergraph
of order p obtained from G by replacing its r-element source sequence src with the p-element
sequence src0 , with src0i = srcα(i) . We defined an infinite number of operators, and we are
able to generate any hypergraph with them. For each family of hypergraphs L that only
contains hypergraphs of bounded treewidth and bounded order, there is a finite subset of the
above operators that generates a superset of L [1, 3, 8]. We denote by Gw a finite hypergraph
algebra as above that generates all r-order hypergraphs over a fixed label set of treewidth
at most w and r < R for some fixed but arbitrary R.
Let A be an alphabet of edge labels, and let G = (V, E, lab, vert, src) be a hypergraph
over A. A formula in counting monadic second-order logic (CMS formula) is a formula
in monadic second-order logic, extended by pradicates Cardm,p (X) for m, p ∈ N, with
X |= Cardm,p (X) iff |X| ≡ m mod p, and by incidence predicates edga (e, v1 , . . . , vτ (a) )
for a ∈ A, with (G, e, v1 , . . . , vτ (a) ) |= edga (e, v1 , . . . , vτ (a) ) iff lab(e) = a and vert(e) =
(v1 , . . . , vτ (a) ). The class Φh,q
A,R (W) consists of all CMS formulas for hypergraphs of order at
most R over edge labels A on variables W whose depth of nested quantification is at most
h and p < q for all subformulas of the form Cardm,p (X). Since h, q, A and W are fixed
in most contexts, we use the short form ΦR = Φh,k
A,R (W). We require variable alphabets W
that include constants for all the source nodes of the hypergraphs, i.e., {si | i ∈ [R]} ⊂ W
and (G, v) |= (v = si ) iff v = srci . Every other variable X in W is assumed to be either
a vertex set variable, denoted as type(X) = V , or a hyperedge set variable, denoted as
type(X) = E. This can be enforced by only considering formulas that include subformulas
∀x : x ∈ X ⇒ x ∈ V if X is supposed to model a set of vertices, and ∀x : x ∈ X ⇒ x ∈ E
otherwise. Note that variables representing single elements can be emulated by a subformula
∃x : ∀y : x ∈ X ∧ (y ∈ X ⇒ x = y).
Our algorithms work on parse trees of hypergraphs with respect to some fixed hypergraph
algebra Gw . A parse tree T = (U, F ) is a directed rooted tree, with edges being directed
away from the root r. Leaves of T are associated with a constant of Gw ; inner nodes
are associated with an operator of Gw . The hypergraph represented by T is the hypergraph
constant associated with r if r is a leaf. Otherwise, T represents the hypergraph obtained by
applying the operator associated with r to the hypergraphs represented by the parse subtrees
rooted in the children of r. For u ∈ U , the hypergraph represented by the parse subtree
of T rooted in u is denoted by G(u). Sometimes it is convenient to have exactly two child
nodes for each inner node of the parse tree. We can think of σα operators as having a second
operand that is always the empty hypergraph. Likewise, θi,j,r operators can be viewed as
having a second operand that is always the one-vertex hypergraph. These modified operators
can even be derived from the original ones. Instead of σα , we can use σα0 = σα ◦ ⊕0,r (0).
0
The composition θi,j,r
= θi,j,r ◦ σα ◦ θi,r+1,r+1 ◦ ⊕1,r (1) with σ : [r] → [r + 1], σ(i) = i, can
replace θi,j,r . All operators of this derived algebra are binary. We call a respective parse
tree a full parse tree. The proper child of a θ or σ node is the one that does not represent
the one-vertex or empty hypergraph, respectively.

David Eppstein and Denis Kurz

XX:7

Let G be a hypergraph, and T = (U, F ) a parse tree of G. We consider combinatorial
problems on G that can be characterized by a CMS formula ϕ ∈ ΦR . Let n be the number of
free variables of ϕ, and let X = (Xi )i∈[n] be the free variables themselves. For example, we
need n = 1 edge set to describe a (simple) path, or n = c−1 node sets to describe a c-coloring
of a graph. An assignment maps every Xi to a subset of type(Xi ). A satisfying assignment
is an assignment f such that (f (X), G) |= ϕ. A solution is the sequence (f (Xi ))i∈[n] for
some assignment f . Two solutions S, S 0 , are considered distinct if there is a j ∈ [n] with
Sj 6= Sj0 . Note that for S1 6= S2 , (S1 , S2 ) is also distinct from (S2 , S1 ) regardless of ϕ, even
if ϕ is a formula on two free variables, and symmetric on these free variables. For a parse
tree node u ∈ U , we denote by S(u) the solution that is obtained from S by removing every
graph feature from every set Si that is not present in G(u). A solution is feasible if the
corresponding assignment is satisfying. We denote by sat(G, ϕ) the set of feasible solutions,
i.e., Y ∈ sat(G, ϕ) ⇔ (Y, G) |= ϕ.
Sets of solutions, and sat(G, ϕ) in particular, are sets of n-tuples of sets. The disjoint
union of two sets M and N (which is undefined if M ∩ N 6= ∅) is written as M t N . Let
X, Y be solutions, and A, B sets of solutions. We say that X and Y interfere if there are
i, j ∈ [n] such that Xi ∩ Yj 6= ∅. By extension, A and B interfere if some X ∈ A interferes
with some Y ∈ B. If A and B do not interfere, A ] B denotes the set of all combinations of
each X ∈ A and Y ∈ B, i.e.,
A ] B = {(Xi t Yi )i∈[n] | X ∈ A, Y ∈ B}.
The above operators are not defined for every combination of operands. A semi-homomorphism
from hS, ], t, ∅, ∅i to some evaluation structure hR, ⊕, ⊗, 0, 1i is a mapping f : S → R that
acts like a homomorphism where applicable, i.e., f (∅) = 0, f (∅) = 1, f (A]B) = f (A)⊕f (B)
if A and B do not interfere, and f (A t B) = f (A) ⊗ f (B) if A ∩ B = ∅.
Values of solution sets are expressed in terms of evaluation structures. An evaluation
structure is an algebra hR, ⊕, ⊗, 0, 1i such that hR, ⊕, 0i and hR, ⊗, 1i are monoids. An
evaluation v is a function that maps hypergraphs generated by Gw to an (ordered) evaluation
structure R. An evaluation v is an MS-evaluation if there exists a semi-homomorphism h
and a CMS formula ϕ ∈ ΦR such that v(G) = h(sat(G, ϕ)) for every hypergraph G.
A linear CMS extremum problem P consists of an r-order hypergraph G, a formula
ϕ = ϕ(P ) ∈ ΦR with n free variables X that characterizes feasible solutions, and a sequence
c of n cost functions with ci : type(Xi ) → R. This can be generalized to other totally-ordered
sets than R but we will not need this generalization. The value c(Y ) of a solution Y for
P
P
P is defined as i∈[n] y∈Yi ci (y). An optimal solution of P is a feasible solution Y ∗ such
that for each feasible solution Y 0 of P , we have c(Y ∗ ) ≤ c(Y 0 ). Our task is to find the
value of an optimal feasible solution of P , or equivalently, to compute the value of v(G) =
min{c(Y ) | Y ∈ sat(G, ϕ)}. This evaluation can be expressed as v(G) = h(sat(G, ϕ))
with h(A) = min{c(Y ) | Y ∈ A}, and is thus an MS-evaluation. Note that h is a semihomomorphism, and the corresponding evaluation structure is hR ∪ {∞}, +, min, 0, ∞i. The
class of all linear CMS extremum problems is called LinCMS. Let m = |sat(G, ϕ)|, and
sat(G, ϕ) = {Y 1 , . . . , Y m }. Let Π = Π(G, ϕ) ⊆ Sn ([m]) be the set of permutations such
that (c(Y π(i) ))i∈[m] is nondecreasing for π ∈ Π. For a problem P ∈ LinCMS, k-val(P ) is
again a problem that gets the same input as P itself, plus some k ∈ N. It asks for the
sequence (c(Y π(i) ))i∈[k0 ] for some π ∈ Π, where k 0 = min{k, m}. The problem k-sol(P ) gets
the same input as k-val(P ), but asks for (Y π(i) )i∈[k0 ] for any π ∈ Π. Note that, depending
on π, different outputs for k-sol(P ) are possible. However, there is only one valid output
for k-val(P ). Also note that 1-val(P ) is equivalent to P itself. For the sake of simplicity, we
assume k ≥ m for the remainder of this article.

XX:8

K-Best Solutions of MSO Problems on Tree-Decomposable Graphs

3

The second-best solution

In the following section, we describe how to solve 2-sol(P ) in linear time for each P in
LinCMS. In a later section we generalize these results to an arbitrary (constant) number of
solutions, and to LOGSPACE and PRAM models of computation.
Courcelle and Mosbah [9] showed that for a hypergraph G generated by Gw , and a formula
ϕ ∈ ΦR , sat(G, ϕ) can be computed by a bottom-up tree automaton on a parse tree of G.
We give a version of their theorem for full parse trees, where every inner node has exactly
two child nodes.
I Lemma 1 (Courcelle, Mosbah[9]). Let ϕ ∈ ΦR , and let T be a full parse tree rooted in r
that represents a hypergraph G. If r is not a leaf, it has two child nodes u1 , u2 representing
G1 = G(u1 ), G2 = G(u2 ), respectively, and the following holds:
]
sat(G, ϕ) =
sat(G1 , ψ1k ) t sat(G2 , ψ2k ) | k ∈ [l] ,
(1)
where l only depends on the hypergraph operator associated with r, and ψ1k , ψ2k are again in
ΦR for each k ∈ [l].
In the situation of Theorem 1, we call ψik a child formula of ϕ with respect to the
corresponding operator. For k ∈ [l], we call (ψ1k , ψ2k ) a fitting pair of child formulas.
A solution S ∈ sat(G, ϕ) has a unique fitting pair (ψ1 , ψ2 ) of child formulas with S ∈
(sat(G1 , ψ1 ) t sat(G2 , ψ2 )), which follows from the fact that all unions in Equation 1 are
disjoint. All child formulas ψ with respect to a θi,j,m node u can be chosen such that srci ∈
/ Sk
for any S ∈ sat(G(u0 ), ψ), where u0 is the proper child of u. Further, Courcelle and Mosbah
demonstrated that every MS-evaluation v can be computed by a similar tree automaton.
The running time required to compute v on the entire hypergraph G is O(|G| · µ), where µ is
the time required to compute f (A) ⊕ f (B) and f (A) ⊗ f (B) for valid combinations A, B. In
the uniform cost model, the operators of the evaluation structure hR ∪ {∞}, +, min, 0, ∞i,
addition and selecting the smaller of two real numbers, require O(1) time. Problems in
LinCMS can therefore be solved in linear time. Applying the semi-homomorphism h with
v(G) = h(sat(G, ϕ)) to Equation 1 yields

v(G) = h(sat(G, ϕ)) = min h(sat(G1 , ψ1k )) + h(sat(G2 , ψ2k )) | k ∈ [l] .
(2)
A different linear-time approach for this special case had been proposed earlier by Arnborg, Lagergren and Seese [2]. The basic algorithm of Courcelle and Mosbah computes
h(sat(G(u), ψ)) for every parse tree node u in a bottom-up manner, and every ψ ∈ ΦR .
Conceptually, we perform a depth-first search on T , starting at its root r. Every time we
finish a node v, we evaluate it, i.e., we compute the evaluation h(sat(G(v), φ)) for every formula ψ ∈ ΦR based on the child formulas of ψ according to Equation 2. Since the number
of formulas and the number of child formulas per formula are fixed, the overall running time
is linear in the size of T .
Courcelle and Mosbah also propose an improved algorithm, called the CM algorithm in
this article, that determines in a top-down preprocessing phase the set of formulas that are
reachable from ϕ at r via the child formula relation. We call these the relevant formulas
of a parse tree node u. Further, we say that u introduces a hypergraph feature x if there
is a feasible solution for relevant formula ψ of u that contains x, but no feasible solution
of relevant formulas at the children of u contains x. Hypergraph features can only be
introduced by leaf nodes and θ nodes, because all solutions for σ and ⊕ nodes are unions of
solutions for their child nodes. A node associated with a θi,j,r operation can only introduce

David Eppstein and Denis Kurz

the source vertex srci . In full parse trees, these θ nodes have an extra child v that represents
a hypergraph consisting only of srci . Therefore, all hypergraph features are introduced by
leaf nodes in full parse trees. Without loss of generality, exactly one parse tree node u(x)
introduces each hypergraph feature x.
Let u be a parse tree node, ψ1 , ψ2 two formulas relevant for u. The CM algorithm only
computes h(G(u), ψ1 ) and h(G(u), ψ2 ), which correspond to the values of optimal solutions
on G(u) for the problems characterized by ψ1 and ψ2 , respectively. We do not have any
information about the solutions themselves besides their values. In particular, we do not
know for any hypergraph feature if it appears in one of those solutions. Since we do not
require optimal solutions to be unique, we also do not know if they represent the same
solution even in the case h(sat(G(u), ψ1 )) = h(sat(G(u), ψ2 )).
In the next section, we need a way to tell if the optimal solutions for ψ1 and ψ2 are the
same by only looking at their evaluations. For this purpose, we establish for each parse tree
node u a mapping from the relevant formulas of u to solution IDs in [|ΦR |] that has the
following discriminating property. Each relevant formula ψ of u is mapped to an optimal
solution for ψ on G(u) such that two formulas are assigned the same solution if and only if
they are assigned the same solution ID. Solution IDs can be computed along with solution
values while keeping the linear time bound:
I Lemma 2. Given all solution IDs for all child nodes of a parse tree node u, solution IDs
for u can be computed in constant time.
Proof. If u is a leaf, let Mu be the set of possible solutions in G(u). Let π : [|Mu |] → Mu
be a permutation of these solutions such that their values are nondecreasing, i.e., c(π(i)) ≤
c(π(i + 1)) for any i ∈ [|Mu | − 1]. For each formula ψ relevant for u, we assign the smallest
i to h(sat(G(u), ψ)) with c(π(i)) = h(sat(G(u), ψ)) as the temporary ID for ψ. If u is an
inner node, let v1 , v2 be the child nodes of u. At least one fitting pair of child formulas
ρ have h(sat(G(u), ψ)) = h(sat(G(v1 ), ρ1 ) + h(sat(G(v2 ), ρ2 )). We choose one of these
pairs arbitrarily. Let a, b be the solution IDs associated with ρ1 at v1 and with ρ2 at v2 ,
respectively. We assign to ψ the temporary ID a · |ΦR | + b.
By induction, temporary IDs have the discriminating property, but there might be temporary IDs larger than |ΦR |. There are at most |ΦR | distinct temporary IDs in use, since
u cannot have more than ΦR many relevant formulas. We can therefore remap temporary
IDs to the range [|ΦR |] using an injective compression function.
J
The compression function can be stored with u, and a mapping from solution ID to
solution at leaf nodes, requiring only constant space. Even if sat(G(u), ψ) contains multiple
optimal solution, it is now possible to refer to the optimal solution, which is the one defined
recursively in terms of matching solution IDs. This particular optimal solution can be found
by a simple depth-first search based algorithm in linear time, starting at ϕ at the root of the
parse tree. For each (u, ψ), we find a fitting pair of child formulas ρ1 , ρ2 for child nodes v1 ,
v2 of u, respectively, such that the assigned solution IDs match, process (v1 , ρ1 ) and (v2 , ρ2 )
independently, and output the associated subsolution at leaf nodes.
To solve 2-val(P ), we have to adapt the evaluation structure. Instead of values in R ∪
{∞}, we use pairs (x, y) ∈ R = (R ∪ {∞})2 , where x represents the value of an optimal
solution, and y represents the value of a second-best solution. We define two new binary
operators +2 and min2 over R, with (x1 , y1 ) +2 (x2 , y2 ) = (x1 + x2 , min(x1 + y2 , x1 + y1 ))
and min2 ((x1 , y1 ), (x2 , y2 )) = (a, b), where a, b are the smallest and second-smallest element
of the multiset {x1 , y1 , x2 , y2 }, respectively.

XX:9

XX:10

K-Best Solutions of MSO Problems on Tree-Decomposable Graphs

I Lemma 3. Let P be a LinCMS problem characterized by the formula ϕ ∈ ΦR and cost functions c. Given a parse tree T of a hypergraph G, the CM algorithm solves 2-val(P ) in linear
time when used in conjunction with the evaluation structure hR, +2 , min2 , (0, 0), (∞, ∞)i.
Proof. For each leaf u of T , we solve 2-val(P ) on G(u) directly. Let S 1 ∈ sat(G, ϕ) be optimal. The mapping v(G) = (c(S1 ), min(c(sat(G, ϕ) \ {S 1 })) can be written as h(sat(G, ϕ))
with h(A ] B) = h(A) min2 h(B) and h(A t B) = h(A) +2 h(B). The operators min2 and +2
can be evaluated in constant time, resulting in linear total time using the CM algorithm. J
The concept of solution IDs can be trivially generalized to the new evaluation structure.
This enables us to refer to the optimal and second-best solution, and to reconstruct these
two solutions in linear time.
I Corollary 4. Let P be a LinCMS problem, and let w ∈ N be fixed. Given a parse tree T
of a hypergraph G with bounded treewidth, we can solve 2-sol(P ) on G in time O(|G|).

4

Dynamizing the second-best solution

In this section, we introduce the evaluation tree data structure that stores intermediate
results of the algorithm from the previous section. The data structure allows for a trivial
query for the values of the two best solutions in constant time, and a query for the solutions
themselves in linear time. We demonstrate how to perform a query for a pivot feature, and
how to update an evaluation tree to match the two subproblems with respect to this pivot
feature as described in subsection 2.1. Both operations start in the root of the given tree,
enabling us to use the path persistence technique described in subsection 2.2.
An evaluation tree is a tree with the same structure as the parse tree. We store with every
node of the evaluation tree the result of all evaluations of the CM algorithm as described
in section 3, as well as all solution ID information. In addition, we also store the solution
sets sat(G(u), ψ) themselves for each leaf node u. We first describe the query and update
procedures for problems characterized by CMS formulas with exactly one free variable. For
this purpose, we identify solutions (S1 ) with their first set S1 . For the sake of simplicity, we
also identify nodes of the parse tree with their twins in the evaluation tree of the current
subproblem. We assume that the hypergraph G is represented as a full parse tree T .
Let ϕ ∈ ΦR be a CMS formula that characterizes a subproblem P , and let x be a pivot
feature of P . If x is a source vertex of G, the two subproblems of P can again be characterized
by formulas in ΦR , namely ϕ ∧ (x ∈ X1 ) and ϕ ∧ (x ∈
/ X1 ), respectively. However, if x is a
hyperedge or a vertex that is not a source vertex of G, there are no such formulas in general.
Therefore, not all subproblems can be characterized by a CMS formula, and we have to
generalize the mapping sat to cover those subproblems. We define the set satP (G(u), ψ)
to contain all solutions in sat(G(u), ψ) that satisfy the constraints imposed by the binary
subproblem tree. Note that h(satP (G, ϕ)) is the solution of 2-val(P ).
Let S 1 and S 2 be the optimal and second-best solution of P , respectively. To find a pivot
feature x for P , we maintain a current parse tree node uj , two formulas ψj1 and ψj2 , and the
invariants S 1 (uj ) ∈ satP (G(uj ), ψj1 ), S 1 (uj ) ∈ satP (G(uj ), ψj2 ), and S 1 (uj ) 6= S 2 (uj ). In
each iteration, we choose uj+1 to be a child node of uj in the parse tree. Initially, u1 is the
root of T , and ψ11 = ψ12 = ϕ. The invariant holds trivially because of h(satP (G(u1 ), ϕ)) =
h(satP (G, ϕ)), and because the optimal solution differs from the second-best one by definition.
If uj is a leaf, it is possible to construct the fixed-size solutions S 1 (u) and S 2 (u) explicitly.
If the invariant holds, these solutions are distinct, and we can determine a pivot feature in

David Eppstein and Denis Kurz

constant time. Otherwise, uj is an inner node with child nodes v1 and v2 . Let ρ1 (ρ2 ) be a
fitting pair of child formulas for ψj1 (ψj2 ) for which solution IDs match. If the invariant holds
for j, the solutions S 1 (uj ) and S 2 (uj ) differ, their subsolutions at v1 (S 1 (v1 ) and S 2 (v1 )) or
1
2
those at v2 have to differ as well. We choose uj+1 , ψj+1
and ψj+1
accordingly. The invariant
for j + 1 then holds by construction.
I Lemma 5. Given an evaluation tree of depth d for a subproblem P , the above algorithm
finds a pivot feature for P in time O(d).
Proof. In each iteration, uj has depth j in the parse tree, so the algorithm has to terminate
after d iterations. Each iteration can be performed in constant time. In the last iteration, we
choose an element in the symmetric difference of S 1 (uj ) and S 2 (uj ), which is guaranteed to
be a pivot feature if the invariant holds. We already showed by induction that the invariant
stays intact.
J
Next, we describe the update process to transform the evaluation tree for P into the
evaluation tree for one of its two subproblems. The process is symmetric for both subproblems, so we only describe it for the subproblem P 0 that requires feasible solutions to contain
the pivot feature.
First, we execute the query algorithm to find a pivot feature x, and push each node it
visits to a stack. The pivot query algorithm can only terminate at leaf nodes, so the last
node u that is pushed to the stack is a leaf. Recall that for each leaf node u and each relevant
formula ψ, we store satP (G(u), ψ) explicitly. We enumerate this solution set and remove
every solution that does not contain x to obtain S(ψ) = satP 0 (G(u), ψ). To re-evaluate ψ,
we apply h to S(ψ).
Any other node u on the stack is an inner node of the full parse tree, and an ancestor
of u(x). Re-evaluation works the same as the original evaluation in the CM algorithm, by
evaluating Equation 2 with operators min2 , +2 instead of min, + as in Theorem 3.
I Lemma 6. Given an evaluation tree of depth d for a subproblem P , the above algorithm
updates the evaluation tree to match a subproblem P 0 of P in time O(d).
Proof. After re-evaluating all formulas at the leaf node u(x), all solutions at u(x) contain
x. Let u be an inner node with a child node v such that all solutions at v contain x. Since
all solutions at u are unions of one solution at v and one other solution, all solutions at u
also contain x. Every ancestor of u(x) is re-evaluated after u(x) itself, so every solution at
the root of the evaluation tree of P 0 contains x by induction.
Filtering solutions of fixed size from a solution set of fixed size, using a criterion that can
be checked in constant time, takes again constant time. Only a fixed number of solution sets
need to be filtered. At inner nodes, we simulate the CM algorithm, which takes constant
time per node. We process the same number nodes as the pivot query algorithm, which is
bounded by d.
J
Let S be the optimal or second-best solution of P , whichever remains feasible in P 0 . We
do not require optimal solutions for subproblems to be unique, so we might find two optimal
solutions for P 0 that both differ from S. Alternatively, S might turn up as the second-best
solution for P 0 . Although these results would be valid outcomes of the update procedure,
the k-best algorithm based on the binary subproblem tree as described in subsection 2.1
would still break. Once we lose track of S by choosing two other solutions as the optimal
and second-best solution for P 0 , we cannot detect whether we find S in a subproblem of
P 0 again, leading to (the value of) S being output twice. That is because solution IDs are

XX:11

XX:12

K-Best Solutions of MSO Problems on Tree-Decomposable Graphs

not suitable to check two solutions with respect to different evaluation trees for equality
efficiently. Therefore, we need to make sure that S is the optimal solution of P 0 as encoded
by the solution IDs for P and P 0 . Fortunately, the update procedure can trivially enforce
this property.
Now consider a problem that is characterized by n free variables, with n > 1. We may
consider n a constant, as it only depends on the problem at hand. Recall that two solutions
S, S 0 are considered distinct if there is a discriminating index i with Si 6= Si0 . The pivot
query algorithm has to take this into account. For inner nodes, it solely relies on solution
IDs to choose a successor of the current parse tree node. For leaf nodes, there is still a fixed
number of feasible solutions for a fixed-size hypergraph. We can apply the same arguments
as above to once more obtain running time O(d). Similarly, we only have to adapt the
processing of nodes for the update algorithm. For n = 1, we always imposed the new
subproblem constraint on the first and only set of a solution, because the discriminating
index was always the same. Now, we have to take into account the discriminating index as
determined during the pivot query phase. Using the same arguments, updates can still be
performed in time O(d). We can now state our main result.
I Theorem 7. Let P be a LinCMS problem. Given a graph G with bounded treewidth and a
number k, computing the values of the k best solutions for P on G requires O(|G| + k log |G|)
time and space.
Proof. In linear time, we compute a shallow tree decomposition, transform it into a full parse
tree T of depth d ∈ O(log |G|), and apply the CM algorithm to T according to Theorem 3.
With the results, we initialize a binary subproblem tree. We perform a best-first search
to find the k best subproblems with respect to their second-best solution as described in
subsection 2.1, which requires us to solve O(k) subproblems. Using the persistent tree
technique from subsection 2.2 in conjunction with the update operation above, we need
O(d) additional time and space per subproblem.
J

5

Fixed numbers of solutions

We generalize here our algorithm for the second best solution to any fixed number of solutions, and to low-space and parallel complexity classes. We note that similar results could
be obtained by expressing the k-best solution problem (for a constant k) as a formula in
MSO with k set variables, all constrained to be solutions, to be different from each other,
and with minimum total weight; however, this would give a significantly worse dependence
on k than the solution we describe. It would also require additional complication to recover
the differences between the solutions (needed for the algorithm in the previous section for
non-constant values of k).
Now let k ∈ N be fixed. The operators mink and +k can be defined analogously to
the operators min2 and +2 , respectively. Evaluating the terms mink (x, y) and x +k y for
k-tuples x, y ∈ Rk still requires constant time. Hence, the CM algorithm in conjunction with
the evaluation structure h(R ∪ ∞)k , +k , mink , (0, . . . , 0), (∞, . . . , ∞)i solves k-val(P ) for any
problem P in LinCMS. Let T be a parse tree with depth d, and let ≤post be a postordering
of T . To solve k-val(P ), we propose to evaluate the nodes of T according to ≤post . As soon
as a parse tree node has been evaluated, the evaluations of its child node can be dropped.
This way, the number of nodes we store evaluations for never exceeds d + 1.
I Theorem 8. Let P be a LinCMS problem, and let k, w ∈ N be fixed. Given a graph G
with treewidth w, the problem k-val(P ) on G can be solved using logarithmic memory space.

David Eppstein and Denis Kurz

Proof. Elberfeld et al. [11] demonstrated that a shallow tree decomposition T can be computed with logarithmic memory space. Using a depth-first search from an arbitrarily chosen
root node, we process the bags of T according to its postordering. A bag is processed by
replacing it with its fixed-size portion of the parse tree, which is then evaluated bottom-up.
The evaluations of all parse tree nodes corresponding to a bag require constant memory
space, and we store O(log |G|) of them at a time.
J
Further, the CM algorithm can be parallelized as follows.
I Theorem 9. Let P be a LinCMS problem, and let k, w ∈ N be fixed. In the EREW PRAM
model, given a shallow tree decomposition T of graph G with treewidth w, the problem kval(P ) on G can be solved in time O(log |G|) by O(|G|) processors.
Proof. We allocate one processor p(u) for each node u of T , which is responsible for computing the portion of the parse tree corresponding to its bag, and for evaluating all nodes
of that portion of the parse tree. The processor p(u) has to wait until all processors p(v)
of child nodes v of u have finished. The processor of the root node of T therefore has to
wait O(log |G|) time. Only processor p(u) writes solutions for node u, and only the parent
u0 of u reads them. The p(u0 ) idles until p(u) finishes computation, resulting in exclusive
read/write access at any time.
J
Finally, using the algorithm of Bodlaender [4] on O(|G|3w+4 ) processors to compute a
shallow tree decomposition, we obtain the following.
I Corollary 10. Let P be a LinCMS problem, and let k, w ∈ N be fixed. In the CRCW
PRAM model, given a graph G with treewidth w, the problem k-val(P ) on G can be solved
in time O(log |G|) by O(|G|3w+4 ) processors.

Acknowledgements
This research was performed in part during a visit of Denis Kurz to UC Irvine, supported
by DFG GRK 1855 (DOTS). The research of David Eppstein was supported in part by NSF
grants CCF-1228639, CCF-1618301, and CCF-1616248.
References
1
2
3
4

5
6

Stefan Arnborg, Bruno Courcelle, Andrzej Proskurowski, and Detlef Seese. An algebraic
theory of graph reduction. J. ACM, 40(5):1134–1164, 1993. doi:10.1145/174147.169807.
Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable
graphs. J. Algorithms, 12(2):308–340, 1991. doi:10.1016/0196-6774(91)90006-K.
Michel Bauderon and Bruno Courcelle. Graph expressions and graph rewritings. Math.
Syst. Theory, 20(1):83–127, 1987. doi:10.1007/BF01692060.
Hans L. Bodlaender. NC-algorithms for graphs with small treewidth. In Jan van Leeuwen,
editor, Graph-Theoretic Concepts in Computer Science, 14th International Workshop, WG
’88, Amsterdam, The Netherlands, June 15-17, 1988, Proceedings, volume 344 of Lecture
Notes in Computer Science, pages 1–10. Springer, 1989. doi:10.1007/3-540-50728-0_32.
Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small
treewidth. SIAM J. Comput., 25(6):1305–1317, 1996. doi:10.1137/S0097539793251219.
Hans L. Bodlaender and Torben Hagerup. Parallel algorithms with optimal speedup
for bounded treewidth. SIAM J. Comput., 27(6):1725–1746, 1998. doi:10.1137/
S0097539795289859.

XX:13

XX:14

K-Best Solutions of MSO Problems on Tree-Decomposable Graphs

7

8

9

10

11

12
13
14

15
16
17
18
19

20

21

Chandra R. Chegireddy and Horst W. Hamacher. Algorithms for finding K-best perfect
matchings. Discrete Applied Math., 18(2):155–165, 1987. doi:10.1016/0166-218X(87)
90017-5.
Bruno Courcelle. Graph rewriting: An algebraic and logic approach. In Handbook of
Theoretical Computer Science, Volume B: Formal Models and Sematics (B), pages 193–
242. 1990.
Bruno Courcelle and Mohamed Mosbah. Monadic second-order evaluations on treedecomposable graphs. Theor. Comput. Sci., 109(1&2):49–82, 1993. doi:10.1016/
0304-3975(93)90064-Z.
James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, and Robert Endre Tarjan.
Making data structures persistent. J. Comput. Syst. Sci., 38(1):86–124, 1989. doi:
10.1016/0022-0000(89)90034-2.
Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace versions of the theorems of
bodlaender and courcelle. In 51th Annual IEEE Symposium on Foundations of Computer
Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 143–152. IEEE
Computer Society, 2010. doi:10.1109/FOCS.2010.21.
David Eppstein. Finding the k shortest paths. SIAM J. Comput., 28(2):652–673, 1998.
doi:10.1137/S0097539795290477.
David Eppstein. K-best enumeration. Bull. EATCS, 115, 2015. URL: http://eatcs.org/
beatcs/index.php/beatcs/article/view/322.
David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification—
a technique for speeding up dynamic graph algorithms. J. ACM, 44(5):669–696, 1997.
doi:10.1145/265910.265914.
Greg N. Frederickson. An optimal algorithm for selection in a min-heap. Inf. Comput.,
104(2):197–214, 1993. doi:10.1006/inco.1993.1030.
Harold N. Gabow. Two algorithms for generating weighted spanning trees in order. SIAM
J. Comput., 6(1):139–150, 1977. doi:10.1137/0206011.
H. W. Hamacher and M. Queyranne. K best solutions to combinatorial optimization
problems. Ann. Oper. Res., 4(1-4):123–143, 1985. doi:10.1007/BF02022039.
Naoki Katoh, Toshihide Ibaraki, and Hisashi Mine. An efficient algorithm for K shortest
simple paths. Networks, 12(4):411–427, 1982. doi:10.1002/net.3230120406.
Edo S. van der Poort, Marek Libura, Gerard Sierksma, and Jack A. A. van der Veen.
Solving the k-best traveling salesman problem. Computers & OR, 26(4):409–425, 1999.
doi:10.1016/S0305-0548(98)00070-7.
Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path,
matrix and triangle problems. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 645–654.
IEEE Computer Society, 2010. doi:10.1109/FOCS.2010.67.
Jin Y. Yen. Finding the K shortest loopless paths in a network. Manag. Sci., 17(11):712–
716, 1971. URL: http://www.jstor.org/stable/2629312.

