BOOLEAN DIMENSION AND TREE-WIDTH

arXiv:1707.06114v1 [math.CO] 19 Jul 2017

STEFAN FELSNER, TAMÁS MÉSZÁROS, AND PIOTR MICEK
Abstract. The dimension of a partially ordered set P is an extensively studied parameter.
Small dimension allows succinct encoding. Indeed if P has dimension d, then to know
whether x < y in P it is enough to check whether x < y in each of the d linear extensions
of a witnessing realizer. Focusing on the encoding aspect Nešetřil and Pudlák defined the
boolean dimension so that P has boolean dimension at most d if it is possible to decide
whether x < y in P by looking at the relative position of x and y in only d permutations of
the elements of P .
Our main result is that posets with cover graphs of bounded tree-width have bounded
boolean dimension. This stays in contrast with the fact that there are posets with cover
graphs of tree-width three and arbitrarily large dimension.
As a corollary, we obtain a labeling scheme of size log(n) for reachability queries on
n-vertex digraphs with bounded tree-width. Our techniques seem to be very different from
the usual approach for labeling schemes which is based on divide-and-conquer decompositions
of the input graphs.

(S. Felsner) Institut für Mathematik, Technische Universität Berlin,
(T. Mészáros) Institut für Mathematik, Freie Universität Berlin,
(P. Micek) Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków and Freie Universität Berlin,
E-mail addresses: felsner@math.tu-berlin.de, meszaros.tamas@fu-berlin.de,
piotr.micek@tcs.uj.edu.pl.
Key words and phrases. posets, tree-width, reachability, labeling scheme.
Piotr Micek was partially supported by the National Science Center of Poland, grant no.
2015/18/E/ST6/00299.
Tamás Mészáros was supported by the DRS POINT Fellowship Program at Freie Universität Berlin.
1

2

S. FELSNER, T. MÉSZÁROS, AND P. MICEK

1. Introduction
Partially ordered sets, called posets for short, are combinatorial structures with applications
in various mathematical fields, e.g. set theory, topology and algebra, and theoretical computer
science. The most important measure of a poset’s complexity is its dimension. The dimension
dim(P ) of a poset P is the least integer d such that points of P can be embedded into Rd in
such a way that x < y in P if and only if the point of x is below the point of y with respect
to the product order of Rd . Though this definition justifies the geometric intuition behind
the notion of dimension usually we work with the following equivalent. A realizer of a poset
P is a set {L1 , . . . , Ld } of linear extensions of P such that for every x, y ∈ P
x 6 y in P ⇐⇒ (x 6 y in L1 ) ∧ · · · ∧ (x 6 y in Ld ),
and the dimension of P is the minimum size of its realizer.
This reveals the second nature of the dimension: Realizers provide a way of succinctly
encoding posets. Indeed if a poset is given with a realizer witnessing dimension d, then a
query of the form ”is x 6 y?” can be answered by looking at the relative position of x and y
in each of the d linear extensions of the realizer. This application motivates the following
more powerful encoding of posets proposed by Nešetřil and Pudlák [8] in 1989.
The boolean realizer of a poset P is a set of permutations {L1 , . . . , Ld } of elements of P
for which there exists a d-ary boolean formula φ such that
x 6 y ⇐⇒ φ((x 6 y in L1 ), . . . , (x 6 y in Ld )) = 1,
and the boolean dimension of P , denoted bdim(P ), is the minimum size of its boolean realizer.
Clearly, for every poset P we have
bdim(P ) 6 dim(P ).
The usual dimension of a poset on n elements may be linear in n. The so called, standard
example Sn , for n > 2, is a poset on 2n elements a1 , . . . , an , b1 , . . . , bn with ai 6 bj in Sn if
and only if i =
6 j, and with no other comparabilites (see Figure 1). It was already observed
in the seminal paper by Dushnik and Miller [3] that dim(Sn ) = n. It is a nice little exercise
to show that bdim(Sn ) 6 4 for every n. In general, Nešetřil and Pudlák show that boolean
dimension of posets on n elements is O(log n). They also provide an easy counting argument
showing that there are posets on n elements with boolean dimension at least c n log n.
b5
b4
b1

b2

b3

b4

b5
b1
a1

a1

a2

a3

a4

a5
a4
a5

Figure 1. The standard example S5 (left). Kelly’s planar poset containing
an induced S5 (right).

BOOLEAN DIMENSION AND TREE-WIDTH

3

Let P be a poset, the cover graph of P is the graph on the elements of P with edge set
{xy | x < y in P and there is no z with x < z < y in P }. A poset is planar if it has a planar
diagram, i.e., its cover graph has a non-crossing upward drawing in the plane. This means
that every edge xy with x < y is drawn as a curve that goes monotonically up from the
point of x to the point of y. Somewhat unexpectedly planar posets have arbitrarily large
dimension. Kelly [7] gave a construction that embeds a standard example as a subposet into
a planar poset (see Figure 1). Another property of Kelly’s construction is that the cover
graphs of resulting posets have tree-width (and even path-width) at most 3. Still, the boolean
dimension of standard examples and Kelly’s construction is at most 4. There is a beautiful
open problem posed in [8] that remains a challenge with essentially no progress over the
years.
Problem 1 (Nešetřil and Pudlák (1989)). Is the boolean dimension of planar posets bounded?
Nešetřil and Pudlák suggested an approach for the negative resolution of this problem
that involves an auxiliary Ramsey-type problem for planar posets. From the positive side,
Brightwell and Franciosa [2] proved that spherical posets with a least element have bounded
boolean dimension, contrary to ordinary dimension. Recently, Trotter and Walczak [11]
studied the interplay of boolean dimension with yet another concept the local dimension.
They propose constructions of families of posets where one of the parameters stays bounded
while the other goes to infinity.
The contribution of our paper is the following result.
Theorem 2. Posets with cover graphs of bounded tree-width have bounded boolean dimension.
The usual dimension is known to be at most 3 for posets with cover graphs being forests
(Trotter, Moore [12]) and at most 1276 for posets with cover graphs of tree-width 2 (Joret
et al. [5]). As mentioned before Kelly’s examples have tree-width 3 and arbitrarily large
dimension. This certifies that boolean realizers are capable to represent natural classes of
posets that are out of reach in the default setting.
It is tempting to speculate, if a similar result to Theorem 2 hold for broader classes of
sparse posets. Besides planar posets, it might be true even for posets whose cover graphs
exclude a fixed graph as a (topological) minor, or even whose cover graphs belong to a fixed
class with bounded expansion. This line resembles the series of papers where poset dimension
is bounded in terms of poset height for posets with cover graphs that are planar [9], or have
bounded tree-width [4], or exclude a fixed graph as a minor [13], or belong to a fixed class
with bounded expansion [6].
A boolean realizer is very much related with a labeling scheme for reachability queries.
Let G be a digraph. A labeling of G is a non-negative integer function L that assigns a
label L(v, G) to each vertex v of G. Formally we see labels as binary strings. A reachability
decoder is a function f that given two labels λ1 , λ2 returns a binary value f (λ1 , λ2 ). Now, a
pair (L, f ) is a reachability labeling, if for every u, v in G
there is a path from u to v in G

⇐⇒

f (L(u, G), L(v, G)) = 1.

Let |L(v, G)| be the length of L(v, G) as a binary string. The size of a labeling scheme (L, f )
for a graph G is maxv∈G |L(v, G)|.

4

S. FELSNER, T. MÉSZÁROS, AND P. MICEK

Bonichon et al. [1] developed a reachability labeling of size O(log n) for trees and caterpillars
on n vertices. Thorup [10] presented a reachability labeling of size O(log2 n) for planar digraphs
on n vertices. It remains a challenge to verify the following.
Problem 3. Is there a reachability labeling of size O(log n) for planar digraphs on n vertices?
Our construction of a boolean realizer directly implies a labeling scheme.
Theorem 4. For every k > 1, there is a reachability labeling of size O(log n) for digraphs on
n vertices with tree-width at most k.

2. Preliminaries
2.1. Tree- and path-decompositions. Let G be a graph. A tree-decomposition of G is a
pair (T, (Bt )t∈T ) where T is a tree and (Bt )t∈T is a family of subsets of V (G), satisfying:
(i) for each v ∈ V (G) there exists t ∈ V (T ) with v ∈ Bt ;
(ii) for every edge uv ∈ E(G) there exists t ∈ V (T ) with u, v ∈ Bt ;
(iii) for each v ∈ V (G), if v ∈ Bt ∩ Bt00 for some t, t00 ∈ V (T ), and t0 lies on the path in T
between t and t00 , then v ∈ Bt0 .
By property (iii) we have that for every vertex v ∈ V (G) the vertices t ∈ V (T ) for which
v ∈ Bt form a subtree of T , called the subtree of v.
The quality of a tree-decomposition (T, (Bt )t∈T ) is usually measured by its width, i.e. the
maximum of |Bt | − 1 over all t ∈ V (T ). Then the tree-width tw(G) of G is the minimum
width of a tree-decomposition of G. The concept of path-decomposition and path-width can
be defined similarly by restricting T above to be a path.
We will call a tree-decomposition nice if for every t, t0 adjacent in T we have |Bt − Bt0 | 6 1
, moreover we have equality only if the degree of both t and t0 is at most two. Note that in
case of path-decompositions the second assumption is automatically guaranteed. It is an easy
observation that every graph has a nice tree-decomposition witnessing its tree-width.
Given a tree-decomposition (T, (Bt )t∈T ) of a graph G of width k, one can color the vertices
of G with k + 1 colors in such a way that if two vertices v, v 0 ∈ V (G) appear together in Bt
for some t ∈ V (T ) then they have different color. We will call such a coloring of G with a
fixed tree-decomposition the ground-coloring of G. (We will have more colorings within the
proof.) When a ground coloring is fixed, for a vertex t ∈ V (T ) and i ∈ [k + 1] we will call the
vertex of ground-color i in Bt the representative of the ground-color i at t, and denote it by
repri (t) (if such a vertex exists).
2.2. Branching programs. To show that a poset P has bdim(P ) 6 d one should provide d
permutations π1 , . . . , πd of the elements of P and a boolean formula φ(ξ1 , . . . , ξd ). It will be
convenient to describe the formula φ as a branching program.
We think of a branching program B as a rooted tree. The nodes of the tree are subprograms.
The task of a subprogram at node N is to return a boolean value to its parent, this boolean
value is called the evaluation of N . The actions taken by the subprogram depend on the
values of some of the input variables ξ1 , . . . , ξd of B. On the basis of these values the program
at N may call some of its children for evaluation and ignore some other children. The

BOOLEAN DIMENSION AND TREE-WIDTH

5

evaluation of N is a function of the values returned from the children and the values of some
further input variables.
The evaluation eval(B) of the branching program B(b1 , . . . , bd ) with inputs b1 , . . . , bd is the
evaluation of its root node.
A branching program B is said to represent a boolean formula φ(ξ1 , . . . , ξd ) if for all inputs
b1 , . . . , bd we have eval(B) = φ(b1 , . . . , bd ). Our informal description of a branching program
is not emphasizing the existence of a corresponding boolean formula, however, such a formula
exists when the evaluation of each node N is only depending on the input variables and the
evaluations of the children.
Therefore we can prove bdim(P ) 6 d by describing a branching program that answers
queries ‘(x < y)?‘ using variables ξ1 , . . . , ξd which depend on x being left or right of y in the
permutations π1 , . . . , πd respectively.
Next we develop some tools that will be useful to define such a branching program.
2.3. Tools for partitions. The tools of this subsection are related to the localization of x
and y in a partition.
Tool 1 (Relative membership in a block). Let A be a set and let {C1 , . . . , Cm } be a partition
of A. Then there are two permutations π1 , π2 of A such that for every distinct x, y ∈ A
x < y both in π1 and π2
or
⇐⇒ x and y belong to different blocks of the partition .
x > y both in π1 and π2
Proof. For i ∈ [m] let σi and σi∗ be an arbitrary permutation of the elements of Ci and its
∗
reversal respectively. Now π1 = σ1 σ2 · · · σm and π2 = σ1∗ σ2∗ · · · σm
are suitable permutations.

Tool 2 (Block identification). Let A be a set and let {C1 , . . . , Cm } be a partition of A. Then
there are 3 · dlog me permutations of A such that for every x, y ∈ A by looking at the order of
x and y in this set of permutations the indices i and j such that x ∈ Ci and y ∈ Cj can be
identified.
Proof. Setting r = dlog me, we can re-index the sets in the partition by subsets of [r]. After
possibly adding empty sets to the partition, we may assume that the partition has the form
{CH : H ⊆ [r]}.
S This induces a dual set system {D1 , . . . , Dr } of A, where for each i ∈ [r]
we have Di = i∈H⊆[r] CH .
Now fix an arbitrary permutation σ of A. For a subset B ⊆ A let σ(B) and σ ∗ (B) denote
the restriction of σ to B and its reversal respectively, and let B be the complement of B in A.
For each i ∈ [r] set
π1i = σ(Di )σ(Di ),

π2i = σ ∗ (Di )σ(Di ),

π3i = σ(Di )σ(Di ),

Suppose x ∈ CHx and y ∈ CHy for Hx , Hy ⊆ [r]. Now for fixed i ∈ [r] look at the order of the
pair (x, y) in the permutations π1i , π2i , π3i . Writing a 1 if x comes before y and a 0 otherwise
we get (1, 0, 1) or (0, 1, 0) if both are in Di ; (1, 1, 0) if only x is in Di ; (0, 0, 1) if only y is in
Di ; and (0, 0, 0) or (1, 1, 1) if neither is in Di . Hence, boolean formulae can decide whether i
is an element of Hx or not and whether i is an element of Hy or not. This shows that the
3r = 3dlog me permutations identify Hx and Hy .


6

S. FELSNER, T. MÉSZÁROS, AND P. MICEK

For m = 2 as a direct corollary we obtain the following statement.
Tool 3 (Set membership). Let A be a set and let C ⊆ A. Then there are three permutations
of A such that for every distinct x, y ∈ A by looking at the order of x and y in these three
permutations one can decide whether x (resp. y) belongs to C or not.
2.4. Red-Green detection on a path in a tree. The tools in this subsection are more
involved then the ones earlier. Here x and y are vertices of a rooted tree with some edges of
the tree being colored with colors Red and Green. For the first question here we assume
that x is an ancestor of y and ask whether the first colored edge on the path from x to y is
Red or Green or there is no colored edge on this path.
Given a rooted tree T and a vertex v of T we denote the subtree of T rooted at v as Tv .
For two vertices u, v we denote the path from u to v in T as [u, v].
Tool 4. Let T be a rooted tree with some edges colored either with Red or Green. Let x, y
be two distinct vertices in T such that x is an ancestor of y, and let π be a permutation of
vertices of T produced by Algorithm 1. Then
y < x in π ⇐⇒ the first colored edge on the path from x to y in T is Red.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Algorithm 1: Red-Green detection for x being an ancestor of y in T
Procedure process(v)
C(v) = {u ∈ Tv | the path [v, u] has no colored edges}
R(v) = {u ∈ Tv | the path [v, u] has a unique colored edge,
this edge is the last edge and it is Red }
G(v) = {u ∈ Tv | the path [v, u] has a unique colored edge,
this edge is the last edge and it is Green }
for u ∈ R(v) do
process(u)
L = list of all vertices in C(v) in a topological order in T
append L to π
for u ∈ G(v) do
process(u)
π = empty
process(root(T ))
return π
Proof. We start the proof with two simple observations.
• During the algorithm every vertex of T is a member of C(v) for a unique v ∈ T .
• A call of process(v) appends all elements of Tv to π before returning.
Now consider two vertices x, y in T such that x is an ancestor of y in T . We distinguish
three cases.
(i) The path [x, y] has no colored edges.
(ii) The first colored edge (v, w) on the path [x, y] is Green.

BOOLEAN DIMENSION AND TREE-WIDTH

7

(iii) The first colored edge (v, w) on the path [x, y] is Red.
Let z be the node of T for which x ∈ C(z) during the algorithm.
Case (i) In this case y ∈ C(z) and in the topological order L of the elements in C(z) we
have x before y, therefore, x < y in π.
Case (ii) We append the list L containing x before calling process(w). However as
process(w) is the one which puts y in the permutation, we again have x < y in π.
Case (iii) We call process(w), and so put y in the permutation, before appending the list
L containing x, so now we have y < x in π.

For the second question we assume that our rooted tree T is given with a planar upward
drawing with lowest vertex being the root. This implies that at every vertex u there is a
fixed left-to-right order of its subtrees. For two vertices u, v in T we say that u is left of v if
there is a vertex w which has two children u0 6= v 0 such that u ∈ Tu0 and v ∈ Tv0 and in the
left-to-right order at w the subtree Tu0 is left of Tv0 . If u, v, w are as above, then we call w
the meet of u and v and denote it by u ∧ v. It is the last common vertex on the paths from
the root of T to u and v.
Tool 5. Let T be a rooted tree with some edges colored either with Red or Green. Let x,
y be two distinct vertices in T such that x is left of y in T and let π be a permutation of
vertices of T produced by Algorithm 2. Then
y < x in π ⇐⇒ the first colored edge on the path from x ∧ y to x in T is Red.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Algorithm 2: Red-Green detection for x left of y in T
Procedure process(v)
append v to π
for each w child of v in T taken in left-to-right-order do
if (v, w) is uncolored then
process(w)
if (v, w) is Red then
S.push(w)
if (v, w) is Green then
S.push(v)
// marking the beginning of the local stack of v
process(w)
while S.top() 6= v do
process(S.pop())
S.pop()
// taking off the marker
π=∅
S=∅
process(root(T ))
while S 6= ∅ do
process(S.pop())
return π
Proof. Again we begin with some simple observations.

8

S. FELSNER, T. MÉSZÁROS, AND P. MICEK

• For each vertex v in T there is a unique call of process(v), i.e., the resulting π is a
permutation of the vertices of T .
• If u and v are vertices of T such that there are vertices u0 and v 0 with u ∈ Tu0 and v ∈ Tv0
and u0 is on the current stack when process(v 0 ) is called, then v < u in π.
• If [u, u0 ] is a path of uncolored edges in T and v is a vertex such that u is an ancestor of
v and u0 is left of v, then u0 < v in π.
• If (v, w) is Green, then the local stack makes the procedure behave as if Algorithm 2 had
been called for the tree Tw . In particular all the vertices of Tw appear in a consecutive
block of π.
Let m = x ∧ y be the meet of x and y, we distinguish three cases.
(i) The path [m, x] has no colored edges.
(ii) The first colored edge (v, w) on the path [m, x] is Green.
(iii) The first colored edge (v, w) on the path [m, x] is Red.
Case (i) x < y in π follows from the third item above.
Case (ii) From the third item above we obtain v < y in π. The call of process(w) appends
all vertices of Tw to π and the vertex x is among them so that x < y in π.
Case (iii) w is put on the stack and remains on the stack until all children of m have
been processed. If v 0 is the child of m with y ∈ Tv0 , then w is on the stack when process(v 0 )
is called. The second item above shows that in this case y < x in π.

3. The proof
Let P be a poset with tw(cover(P )) 6 k. Fix a nice tree-decomposition (T, (Bt )t∈V (T ) )
of width at most k. We imagine the tree T to be rooted and being drawn upwards with
lowest vertex the root. In particular at every vertex t there is a fixed left-to-right order of its
subtrees. For z ∈ P let root(z) denote the root (i.e. the lowest point) of the subtree of z in
T . Since our tree-decomposition is nice we know that all the root(z) for z ∈ P are distinct.
To prepare for the design of the branching program we next define a companion structure
of the tree-decomposition.
3.1. The accompanying dag. Fix a ground-coloring col : P → [k + 1]. For a vertex
t ∈ V (T ) and an element x ∈ P such that root(x) is an ancestor of t in T we define the
vector vec(x, t) of length k + 1 such that for i ∈ {1, . . . , k + 1} the ith coordinate is


< if x < repri (t) in P



 > if x > repri (t) in P
k if x k repri (t) in P
veci (x, t) =
.


= if x = repr (t)


 ∗ if repr (t) iis undefined
i
For a vertex t ∈ V (T ) we define the active set of t as
Active(t) = {vec(x, t) : x ∈ P such that root(x) is an ancestor of t}.
Here we remark that above we allow root(x) = t. Note that for every t ∈ V (T ) there are at
most 5k+1 such possible vectors, so in particular | Active(t)| 6 5k+1 .

BOOLEAN DIMENSION AND TREE-WIDTH

9

Next we define an auxiliary directed graph D accompanying our fixed tree-decomposition
and
set of D
Sground-coloring, that will play a key role in the remaining argument. The vertex
0
is t∈V (T ) {t} × Active(t). The edges in D are of the form: from (t, vec(x, t)) to (t , vec(x, t0 )
for every t, t0 ∈ T with t being a parent of t0 in T and every x ∈ P with root(x) being an
ancestor of t in T .
Lemma 5. For every two distinct vertices t, t0 ∈ T such that t is an ancestor of t0 in T and
every v ∈ Active(t) there is exactly one v 0 ∈ Active(t0 ) such that there is a path from (t, v) to
(t0 , v 0 ) in D.
Proof. Let’s first start with two adjacent vertices t, t0 in T with t being the parent of t0 . First,
we show that for every two elements x, y ∈ P with root(x) and root(y) being ancestors of t
in T , and vec(x, t) = vec(y, t), we have
vec(x, t0 ) = vec(y, t0 ).

(1)

Since our tree-decomposition is nice we either have Bt0 ⊆ Bt or there is exactly one element
z 0 ∈ P such that z 0 ∈ Bt0 − Bt (this clearly means that root(z 0 ) = t0 ).
If Bt0 ⊆ Bt then for every z ∈ Bt0 , say of a ground-color i, we have repri (t0 ) = z = repri (t).
Therefore, whenever repri (t0 ) is defined, we have veci (x, t0 ) = veci (x, t) = veci (y, t) =
veci (y, t0 ). Thus vec(x, t0 ) = vec(y, t0 ) as required.
Otherwise let z 0 be the unique element in Bt0 − Bt , say with col(z 0 ) = j. For every
ground-color i 6= j, if repri (t0 ) exists then as before veci (x, t0 ) = veci (y, t0 ). Now, suppose that
vecj (x, t0 ) = ‘ < ‘. This by definition means that x < z 0 in P . Let us consider a cover chain
of this relation in P . By the properties of our tree-decomposition this chain must contain
an element z with x 6 z < z 0 in P such that z is in both Bt and Bt0 . Say col(z) = i0 . As
clearly i0 =
6 j we already know that veci0 (x, t0 ) = veci0 (y, t0 ), hence we conclude y 6 z < z 0
in P and therefore vecj (y, t0 ) = ‘ < ‘ as required. Along the very same line we can prove
that if vecj (x, t0 ) = ‘ > ‘, then vecj (y, t0 ) = ‘ > ‘. As z 0 6= x, y and repri0 (t0 ) = z 0 we know
that vecj (x, t0 ) and vecj (x, t0 ) can take only three possible values ‘ < ‘, ‘ > ‘, ‘ k ‘ and as the
argument was symmetric for x and y, this completes the proof of (1).
The lemma now follows with an easy induction on the distance between t and t0 in T . We
proved before the statement for t, t0 at distance 1 in T . For larger distances, we pick the last
vertex t00 before t0 on a unique t-t0 path in T . Now by the induction hypothesis there is a
unique v 00 ∈ Active(t00 ) such that there is a path from (t, v) to (t00 , v 00 ) in D. And again there
is a unique v 0 ∈ Active(t0 ) such that there is a path from (t00 , v 00 ) to (t0 , v 0 ) in D. This proves
the lemma.

For z ∈ P let source-vec(z) denote the unique vertex (root(z), v) in {root(z)} ×
Active(root(z)) with no in-edge, i.e. v is the unique vector in Active(root(z)) which has a
0
=0 in coordinate col(z). Further let dest-vec(< z) (resp. dest-vec(> z)) denote the set of all
vertices (root(z), v) of D with vcol(z) =0 <0 (resp. vcol(z) =0 >0 ).
By Lemma 5, for every t ∈ T , v ∈ Active(t) and every descendant t0 of t in T there is
a unique directed path in D, denoted by path((t, v), t0 ), that starts at (t, v) and for every
t00 on the path from t to t0 intersects Active(t00 ) in exactly one element. If v = vec(x, t)
for some element z ∈ P with root(z) an ancestor of t, then this element is (t00 , vec(z, t00 )).
To simplify notation, if (t, v) = source-vec(z) for some element z ∈ P , the instead of
path(source-vec(z), t0 ) we will simply write path(z, t0 ).

10

S. FELSNER, T. MÉSZÁROS, AND P. MICEK

Given a subgraph F of D we define the projection proj(F ) of F to T as the subgraph of
T obtained by restricting the elements of F to their first component. Formally, if a vertex
(t, v), v ∈ Active(t) belongs to F , then t belongs to proj(F ), and if ((t, v), (t0 , v 0 )) is an edge
of F , then (t, t0 ) is an edge of proj(F ).
Next we define a coloring of the vertices and edges of D with colors from Γ = [5]k+1 .
1
2
3
4
5
6
7
8
9

Algorithm 3: Γ-coloring of D
Initialization let t0 , t1 , . . . , tm be the vertices of T in left-to-right topological order
and color all vertices of D in Active(t0 ) with distinct colors
for i = 0, . . . , m do
color each edge of D leaving Active(ti ) with the color of its source vertex in
Active(ti )
for each child t of ti do
color each vertex of D in Active(t) according to the following rule
if the in-degree of the vertex is positive then
color it with the smallest of the colors of its incoming edges
if all vertices with positive in-degree have been colored and there exists a vertex
with no incoming edge then
color it with a color different from all those used on Active(t) so far
For z ∈ P let source-col(z) denote the color of source-vec(z) under this coloring. Further
let dest-col(< z) (resp. dest-col(> z)) be the set of colors of vertices in dest-vec(< z) (resp.
dest-vec(> z)).
Note that the colors (of the vertices) along any directed path in D are always non-increasing.
We say that a color sequence (γ0 > γ1 > · · · > γ` ) is the signature of a directed path Q in
D if {γ0 , γ1 , . . . , γ` } is the set of colors of the vertices in Q. In fact this means that Q is a
concatenation Q0 Q1 · · · Q` of subpaths where all vertices in Qi have color γi for every i.

t

Active(t)
Figure 2. A sketch of a path-decomposition and an associated dag. Vectors
of the same color are horizontally aligned such that colors increase vertically.
The following two lemmas are the key to the usage of the dag in the branching program.
They provide necessary and sufficient conditions for two queried elements x and y of P to be
in relation x < y in P .
For an element (t, v) in D with t ∈ V (T ) and v ∈ Active(t), we define tree((t, v)) of
all elements of D that are reachable from (t, v) with a directed path in D. Indeed, as
suggested by the notation, tree((t, v)) is a directed subtree in D rooted at (t, v). By Lemma 5
proj(tree((t, v))) is exactly Tt , i.e. the whole subtree rooted at t in T .

BOOLEAN DIMENSION AND TREE-WIDTH

11

To simplify notation, if (t, v) = source-vec(z) for some element z ∈ P then we simply write
tree(z) for this subtree.
Lemma 6 (x is below y). Let x, y be two distinct elements in P such that root(x) is an
ancestor of root(y) in T . Then
x < y in P ⇐⇒ tree(source-vec(x)) contains a vector from dest-vec(< y).
Proof. Note that tree(source-vec(x)) contains elements of the form (t, vec(x, t)) for all t below
root(x) in T . If t = root(y), then veccol(y) (x, root(y)) ∈ {<, >, k} indicates the comparability
status of x and y. By definition this status is 0 <0 if and only if (root(y), vec(x, root(y))) ∈
dest-vec(< y).

Lemma 7 (x is left of y). Let x, y be two distinct elements in P such that root(x) is left of
root(y) in T and let mxy = root(x) ∧ root(y). Then
x < y in P ⇐⇒ there is a vector v ∈ Active(mxy ) such that tree((mxy , v)) contains
•

a vector from dest-vec(> x) and

•

a vector from dest-vec(< y).

Proof. First we prove the backwards implication. Suppose that there is a vector v ∈
Active(mxy ) such that tree((mxy , v)) intersects both dest-vec(> x) and dest-vec(< y). Let z
be an element of P such that root(z) is an ancestor of mxy in T and vec(z, mxy ) = v. Note
that all the elements in tree((mxy , v)) are of the form vec(z, t) for all t descendants of mxy
in T . This yields that vec(z, root(x)) ∈ dest-vec(> x) and vec(z, root(y)) ∈ dest-vec(> x),
which implies x < z < y in P as required.
Now assume that x < y in P . There is a chain x = z0 < · · · < z` = y with all zi < zi+1 being
cover relations in P . By the properties of the tree-decomposition we know that the union of
subtrees of z1 , . . . , z` form a subtree of T . In particular there must be zi such that zi ∈ Bmxy
Since root(zi ) is an ancestor of mxy the vectors vec(zi , root(x)) and vec(zi , root(y)) are defined.
From x < zi < y it follows that tree(zi ) contains vectors from dest-vec(> x) and dest-vec(< y).
Let v = vec(zi , mxy ) and note that tree((mx,y , v)) is a subtree of tree(source-vec(zi )) that
still intersects both dest-vec(> x) and dest-vec(< y). This completes the proof.

3.2. The initial nodes of the branching process. The colored dag D provides the
structure needed to devise a branching program B and a set of permutations π1 , . . . , πd
(with d being a function of k only) such that for every query ‘(x < y)?‘, when we set
bi = [x < y in πi ] then the evaluation of B with the variables being set to b1 , . . . , bd is 1 if
and only if x < y in P . As discussed before this will prove bdim(P ) 6 d.
The root node Nroot of B first of all quickly separates the case x = y. This can be done with
two initial permutations where one is reversal of the other. If x 6 y in both permutations
then it must be that x = y and Nroot outputs 1. Therefore, in the following we assume that
the queried elements are distinct.
So now the root node Nroot is used to branch into the appropriate subprograms depending
on the relative position of root(x) and root(y) in the tree T .
Since we assume a nice tree-decomposition we know that root(x) 6= root(y), hence their
relative position is one of the following four:

12

S. FELSNER, T. MÉSZÁROS, AND P. MICEK

• x is below y,
i.e., root(x) is an ancestor of root(y).
• x is above y,
i.e., root(y) is an ancestor of root(x).
• x is left of y,
i.e., at their meet node t the subtree of root(x) is left of the subtree of root(y).
• x is right of y,
i.e., at their meet node t the subtree of root(x) is right of the subtree of root(y).
To decide on the relative position it is enough to look at the relative position of root(x)
and root(y) in the left-first-search and the right-first-search order of the vertices of T .
Note that vertices of T are not quite elements of P , hence, for example the left-first-search
order of the vertices of T is not a valid permutation for the branching program. However,
restricting the left-first-search order of the vertices of T to those vertices which are of the
form root(z) for some z ∈ P we obtain a permutation of P which can be used to decide on
the relative position of x and y.
In the remaining part of this paper, just as above, instead of constructing permutations of
P we frequently construct permutations of the vertices of T and understand without saying
that the corresponding permutation of P is the induced permutation of the vertices which
are of the form root(z) for some z ∈ P .
Below, in Subsection 3.4 and 3.5 we describe the branching (sub)programs for the cases
where x is below y and where x is left of y. The other two cases are symmetric to these and
can thus be ommitted. As a warmup, in Subsection 3.3 we deal with the special case where
the tree-decomposition is in fact a path-decomposition, i.e., T is a path.

3.3. The case where T is a path. Throughout this subsection T is a path. We think of
this path drawn horizontally with the root being its leftmost vertex, i.e., the edges of the
underlying dag are directed left-to-right. We also assume that for the vertices queried we
have root(x) left of root(y) on T . This instance can be identified with a single permutation,
and the other case when root(x) is right of root(y) is symmetric.
One advantage of being in the path case is that for every z ∈ P there is a unique directed
path, denoted by path(z), in D that starts in source-vec(z). This path contains the vertices
(t, vec(z, t)) for all t to the right of root(z) in T .
A direct corollary of Lemma 6 in this case is the following.
Corollary 8. Let x, y be different elements in P such that root(x) is left of root(y) in T .
Then x < y in P if and only if there exists a color sequence (γ0 > γ1 > · · · > γ` ) such
that γ0 = source-col(x), γ` ∈ dest-col(< y) and the portion of path(x) from source-vec(x) to
dest-vec(< y) has signature (γ0 , γ1 , . . . , γ` ).
k+1

Note that the set of possible signatures has cardinality at most 25 . This is a function
of k, hence, we can color elements z of P with the signature of path(z). The first task of the
branching program is to identify the color, i.e., the signature, of x. This can be handled with
k+1
the Block Identification Tool (Tool 2) using at most 3 · dlog 25 e = 3 · 5k+1 permutations.
We will have a separate subprogram NS for every possible signature S.

BOOLEAN DIMENSION AND TREE-WIDTH

13

Consider now a fixed signature S = (s0 > s1 > s2 > · · · > sλ ). In the following we describe
how to build the subprogram NS that allows to decide for the comparability status of x, y
when S is the signature of path(x).
Let ZS be the set of all z ∈ P such that S is the signature of path(z). For z ∈ ZS and i 6 λ
we write pathi (z) to denote the the maximal prefix of path(z) with signature (s0 , s1 , . . . , si ).
Define F0 to be the family of projections of all maximal subpaths of D entirely of color s0
to T . Note that the paths of F0 are pairwise disjoint. In fact F0 is the collection of projections
of the initial parts of path(z) for all z with source-col(z) = s0 .
Starting from F0 = F0∅ we inductively construct families Fiα of paths of T where 1 6 i 6 λ
α,0
and α = α1 , . . . , αi is a binary sequence. The construction is such that the two familes Fi+1
α,1
and Fi+1 depend only on Fiα .
The following properties of the families are essential:
• For each i and α the paths in Fiα are pairwise disjoint.
• For each path Q in Fiα there is an element z ∈ ZS such that proj(pathi (z)) is a postfix of
Q. We call z a witness for Q and let W (Q) be the set of all witnesses of Q.
• For all z ∈ ZS and all i there is some α such that there is a path Q in Fiα which has
proj(pathi (x)) as a postfix.
α,0
α,1
Given Fiα we now show how to construct Fi+1
and Fi+1
. This is done in two steps. First
α
+
we extend each path Q of Fi to a larger path Q . In the second step, after possibly removing
some of the paths, we break the family of extended paths into two subfamilies such that the
paths in each of these subfamilies are disjoint.
For each such Q consider any witness z and define Q+ as Q ∪ proj(pathi+1 (z)). Now
+
whenever there are two paths Q+
1 , Q2 with the same right endpoint, then remove the shorter
from the collection and note that every z ∈ W (Q1 ) ∪ W (Q2 ) is a witness for the larger one.
Let Fiα+ be the family of the remaining extended paths.
To partition Fiα+ into two disjoint subfamilies we first sort the paths in Fiα+ by increasing
right endpoints. Each Q+ ∈ Fiα+ is composed of a path from the disjoint family Fiα and the
projection of a path of color si+1 in D. Note that these latter paths of color si+1 are also
pairwise disjoint. Therefore a path Q+ ∈ Fiα+ can only intersect with its predecessor and
α,0
its successor in the order by right endpoints, see Figure 3. Now let Fi+1
consist of the path
α,1
at even positions in the sorted order and let Fi+1 consist of those at odd positions. Both
families are disjoint.

Paths from Fi
Path of color si+1
Figure 3. Some elements of Fiα+ .
By construction each path in a family Fiα has a nonempty set of witnesses and since each
z ∈ ZS is the witness for a path in F0 it is then necessarily also a witness of a path in Fiα for
all i and some α. This shows that the construction results in families of paths with the three
desired properties.
For each z ∈ ZS there is a unique binary sequence α(z) of length λ 6 5k+1 such that for
each prefix αi (z) of length i of this sequence it holds that z is a witness for some path in

14

S. FELSNER, T. MÉSZÁROS, AND P. MICEK
α (z)

Fi i . With the Block Identification Tool (Tool 2) we can pass the query for the pair x, y to
a subprogram NS,α with α = α(x). As the total number of possible binary sequences is 2λ
this can be done by using 3 · dlog 2λ e = 3λ 6 3 · 5k+1 permutations.
NS,α has a child NS,α,` for each 1 6 ` 6 λ and it evaluates to 1 if and only if one of its
children evaluates to 1. The node NS,α,` checks whether the right end point of proj(path`−1 (x))
is to the left of root(y) and proj(path` (x)) contains root(y). If one of these test fails then
NS,α,` evaluates to 0. If both tests are passed we know that the vertex (root(y), v) of D
contained in path(x) has color s` . To see whether x < y we thus only have to check whether
s` ∈ dest-col(< y). This is application of the Set Membership Tool (Tool 3), and can be done
using three permutations. If all
What remains is to describe how to decide whether the right endpoint of proj(path` (x)) is
to the left or to the right of root(y). Recall that root(x) is left of root(y) and by construction
α (x)
of the path families F` ` contains some Q witnessed by x, i.e., there is a path Qx which
contains proj(path` (x)) as a postfix. Therfore it is enough to check whether root(y) ∈ Qx .
This can be done using the first version of the Red-Green Detection Tool (Tool 4). Color
α (x)
the edges on the right of the right endpoints of paths in F` ` Red. By Proposition 4 the
positions of x and y in a single permutation of P allows to decide whether there is a Red
edge on the path from root(x) to root(y) on T .
This completes the description of the branching structure for the special case where T is a
path.
3.4. The case when x is below y in T . Recall that when root(z) is an ancestor of t in T
with path(z, t) we denote the directed path in D which starts at source-vec(z) and ends in
some vertex from {t} × Active(t). Clearly path(x, root(y)) is a path in tree(x) and tree(x)
contains a vector from dest-vec(< y) if and only if path(x, root(y)) contains such a vector.
Therefore, we have the following direct corollary of Lemma 6.
Corollary 9. Let x, y be different elements in P such that x is below y in T . Then x < y in
P if and only if there exists a color sequence (γ0 > γ1 > · · · > γ` ) such that γ0 = source-col(x),
γ` ∈ dest-col(< y) and path(x, root(y)) has signature (γ0 , γ1 , . . . , γ` ).
Corollaries 9 and 8 look almost identical at the first glance, however, the path and also the
signature now depend on y in a much stronger way. Therefore, the task of identifying the
relevant signature for a pair x, y is a harder one in this case.
The branching program for this case starts with a major parallel node Nx below y that
has as a child NS for every S a possible signature of a path in D. Recall that the set of
k+1
possible signatures has cardinality at most 25 . Again the output of Nx below y is simply an
alternative of outputs of all NS .
Now we fix a legal signature S = (s0 > s1 > s2 > · · · > sλ ) and we proceed with a
description of the node NS . The node NS is designed in a way that NS outputs a 1 if and
only if the signature of path(x, root(y)) is S and sλ ∈ dest-col(< y).
The subprogram for NS starts with a verification if s0 = source-col(x). This is done
with the Set Membership Tool (Tool 3) using 3 permutations. The node NS returns a 0 if
s0 6= source-col(x) and otherwise it continues with the next step.
At this point we know that s0 is the first color of the signature of path(x, root(y)). We are
going to proceed step by step verifying if consecutive colors of this signature agrees with S.

BOOLEAN DIMENSION AND TREE-WIDTH

15

This check, similarly as in the case of T being a path, is based on families of disjoint subtrees
of T which are defined inductively.
We start with some helpful notation. First let (t, v) be a vertex of color γ in D. We will
denote by tree ((t, v), γ) the directed subtree of D which is rooted at (t, v) and contains all
vertices of color γ in D which can be reached from (t, v) on a directed path of color γ. Let
T (t, γ) be proj(tree ((t, v), γ)).
As a basis for the inductive construction we have a family F(γ) for each γ ∈ [5k+1 ]. This
family is defined to be
F(γ) = {T (root(z), γ) | for every z ∈ P with source-col(z) = γ}
It comes from the basic properties of the dag that trees in F(γ) are pairwise disjoint.
Claim. The family F(γ) is a family of pairwise disjoint subtrees of T , for every γ ∈ [5k+1 ].
Proof. Suppose in contrary that there are distinct Q, Q0 ∈ F(γ) and t ∈ Q ∩ Q0 . Let
root(Q) = root(z) and root(Q0 ) = root(z 0 ) for some elements z, z 0 ∈ P . By the construction
we have source-col(z) = γ = source-col(z 0 ). Let (t, v) be the vertex in D colored with γ.
Since t is in Q and Q0 there are directed paths in D from source-vec(z) to (t, v) and from
source-vec(z 0 ) to (t, v). In particular root(z) and root(z 0 ) must be both ancestors of t in T .
This implies that one of root(z) and root(z 0 ) is an ancestor of the other in T , say root(z) is
an ancestor root(z 0 ). Now the directed path from source-vec(z) to (t, v) in D has all vertices
colored with γ. Since root(z 0 ) is on the directed path from root(z) to t in T the path must
go through a vertex in {root(z 0 )} × Active(root(z 0 )) colored with γ, which is source-vec(z 0 ).
This is a contradiction as source vertices have no incoming edges in D.

Starting from F0∅ = F(s0 ) we inductively construct families Fiα of trees of T where
1 6 i 6 λ and α = α1 , . . . , αi is a ternary sequence, i.e., αj ∈ {0, 1, 2} for all j. An essential
property of the families is that:
For each i and α the trees in Fiα are pairwise disjoint.
α,0
If α is a ternary sequence of length i (with 0 6 i < λ), then we define Fi+1
= F(si+1 ). To
α,1
α,2
α
construct the two other familes Fi+1 and Fi+1 , which depend on Fi , we use an intermediate
family Fiα,+ . The family Fiα,+ is produced by Algorithm 4. For the description of this
algorithm we need additional notation. For γ ∈ [5k+1 ] we call a vertex t in T a γ-break if
vertices in {t} × Active(t) in D are not colored with γ. For an edge (t, t0 ) of T we say that γ
merges into β at (t, t0 ) if

(i) γ > β,
(ii) there is a γ-colored vertex (t, v) ∈ Active(t) and a β-colored vertex (t0 , v 0 ) ∈ Active(t0 ),
(iii) and there is an edge from (t, v) to (t0 , v 0 ) in D.
α,1
α,2
The following claim shows that Fiα,+ can be split into two families Fi+1
and Fi+1
such that
each of them consists of pairwise disjoint trees.

Claim. For every i > 0 and α ∈ {0, 1, 2}i , assuming that the family Fiα consists of pairwise
disjoint subtrees of T , the family Fiα,+ , produced by Algorithm 4, can be split into two blocks
each consisting of pairwise disjoint subtrees of T .

16

S. FELSNER, T. MÉSZÁROS, AND P. MICEK

Algorithm 4: Construction of a family Fiα,+ given Fiα
1
2
3
4
5
6
7
8
9
10

Fiα,+ ← ∅
for each Q in Fiα do
Q+ ← ∅, r ← root(Q)
for each t leaf of Q and edge (t, t0 ) such that
(a) [r, t] contains a si+1 -break
(b) si merges into si+1 at (t, t0 ) do
Q+ ← Q+ ∪ [r, t0 ] ∪ T (t0 , si+1 )
if Q+ 6= ∅ then
add Q+ to Fiα,+
return Fiα,+
Proof. Consider the family Fiα,+ produced by Algorithm 4. Every tree Q+ added into Fiα,+
comes from some tree Q in Fiα,+ . We split each such Q+ into two sections. The primal
section of Q+ is the part that comes from its origin Q, i.e., Q+ ∩ Q, and the extended section
of Q+ is the extended part, i.e., Q+ r Q.
α,+
+
We show that for every two distinct trees Q+
both their primal and extended
1 , Q2 ∈ Fi
sections are disjoint respectively.
+
First, we argue about the primal sections. The primal sections of Q+
1 and Q2 are contained
in their origins Q1 and Q2 , respectively. But since Q1 , Q2 ∈ Fiα they are disjoint by
assumption.
+
Now consider the extended sections R1 , R2 of Q+
1 , Q2 , respectively. In order to get a
contradiction, suppose that t ∈ R1 ∩ R2 . For j = 1, 2 let rj = root(Qj ) and note that
+
0
root(Q+
j ) = root(Qj ). Since t is in the extended section of Qj there must be a leaf tj of Qj
and an edge (t0j , t00j ) with t ∈ T (t00j , si+1 ), moreover there is a break at some vertex tj on [rj , t0j ].
Since Q1 and Q2 are disjoint [r1 , t01 ] and [r2 , t02 ] are disjoint intervals on the path from the
root of T to t. Assuming w.l.o.g. that t01 is an ancestor of r2 in T we see that t2 is an si+1
break in [t01 , t] which is in contradiction to t ∈ T (t00i , si+1 ).
This proves that the extended sections of distinct trees in Fiα,+ are disjoint. Hence, the
family Fiα+ induces a chordal graph with clique number two. This chordal graph is 2-colorable.
A two coloring induces a partition of Fiα+ into two families such that each consists of pairwise
disjoint subtrees of T .

We are now back and continue the definition of NS . Recall that we are at the point when
we do know that s0 is the first color of the signature of path(x, root(y)). We define for every
0 6 i 6 λ and α ∈ {0, 1, 2}i a subprogram W (i, α). The branching program is going to visit
a sequence of these subprograms, starting with W (0, ∅). We always make sure that when
W (i, α) is called then the following invariant has been established:
The sequence (s0 , . . . , si ) is a prefix of the signature of path(x, root(y)). Moreover,
(i) if (s0 , . . . , si ) is a proper prefix of the signature of path(x, root(y)) then
there is a tree Q in Fiα such that root(x) ∈ Q and t is a leaf of Q where

BOOLEAN DIMENSION AND TREE-WIDTH

17

t is the unique vertex in T such that path(x, t) is the maximal prefix of
path(x, root(y)) with signature (s0 , . . . , si ).
(ii) otherwise when the signature of path(x, root(y)) is equal (s0 , . . . , si ) there
is a tree Q in Fiα such that root(x), root(y) ∈ Q
Note that the invariant holds for W (0, ∅) as we already know that source-col(z) = s0 and
the tree T (root(x), s0 ), that lies in the family F0∅ = F(s0 ), witnesses (i) or (ii).
We proceed with the description of W (i, α) (with 0 6 i < λ and α ∈ {0, 1, 2}i ). This
subprogram consists of two steps.
Step 1 The first task of W (i, α) is to establish whether path(x, root(y)) has a prefix with
signature (s0 , . . . , si+1 ). This will be done using a single permutation with the Red-Green
Detection Tool (Tool 4). For all Q ∈ Fiα , all leaves t of Q and all edges (t, t0 ), t being a
parent of t0 , color the edge Red if si merges into si+1 at (t, t0 ), otherwise color it Green.
Looking at the relative positions of x and y in the permutation π generated by the tool
the program learns whether the first colored edge on the path from root(x) to root(y) is
Red or not. If the answer is not (i.e. the first colored edge is Green or there is no colored
edge) path(x, root(y)) contains no merge from si to si+1 and the whole program NS outputs
a 0. On the other hand if the first colored edge is Red, then it has been established that
path(x, root(y)) has a prefix with signature (s0 , . . . , si+1 ).
Note that if this is the case we know that it the item (i) of the invariant that holds. Indeed,
(s0 , . . . , si ) is a proper prefix of (s0 , . . . , si+1 ) which as we learnt is the prefix of the signature
of path(x, root(y)). Let Qx be a tree in Fiα witnessing the item (i) and let tx be the leaf of Q
on the path(x, root(y)).
Step 2 The second task of W (i, α) is to decide which subprogram to continue with, i.e. which
α,0
α,1
α,2
is the relevant family for the (x, y)-query out of Fi+1
, Fi+1
and Fi+1
.
α,0
The family Fi+1
is relevant if there is no si+1 -break on the path from root(x) to the leaf tx
This again can be done using a single permutation with the Red-Green Detection Tool
(Tool 4). Color the edges of T as follows. For all Q ∈ Fiα , all leaves t of Q and all edges
(t, t0 ), where t is a parent of t0 , color the edge (t, t0 ) Green. For each vertex t ∈ T which is a
si+1 -break color all edges from t to its children in T with Red (possibly overriding Green).
From the permutation π generated by the Red-Green Detection Tool the program learns
whether the first colored edge on the path from root(x) to root(y) is Red or not. Note that
as root(y) 6∈ Qx we necessarily have a colored edge on this path.
If the first colored edge on the path from root(x) to root(y) is Green then there is no
si+1 -break on the path from root(x) to tx in T and the next subprogram called is W (i + 1, α0).
Note that the required invariant holds.
If the first colored edge on the path from root(x) to root(y) is Red then there is a si+1 -break
on the path from root(x) to tx in T . In this case we know that Fiα+ contains a tree Q which
contains the maximal prefix of path(x, root(y)) with signature (s0 , . . . , si+1 ). Now it is up to
α,1
α,2
α,1
α,2
deciding whether this tree Q belongs to Fi+1
or to Fi+1
. The set of trees in Fiα+ = Fi+1
∪Fi+1
has been produced as offsprings of trees in Fiα , and Q is actually the offspring Q+
x of Qx in
α
this union. Now consider the partition of Fi into three subfamilies, those with an offspring in
α,1
α,2
Fi+1
, those with an offspring in Fi+1
, and the rest. Since the trees in Fiα are disjoint root(x)
is contained only in Qx which is in one of these three families. With the Block Identification
Tool (Tool 2) we can identify, using 3 · dlog 3e = 6 permutations, the subfamily containing

18

S. FELSNER, T. MÉSZÁROS, AND P. MICEK

Qx . On the basis of this it can be decided whether W (i + 1, α1) or W (i + 1, α2) has to be
called next. Whichever is chosen we have made sure that the invariant holds.
This completes the description of the subprograms W (i, α) for 0 6 i < λ and α ∈ {0, 1, 2}i .
It remains to describe the finishing subprograms W (λ, α) with α ∈ {0, 1, 2}λ . By the
invariant we do know that S = (s0 , . . . , sλ ) is the prefix of the signature of path(x, root(y)).
The subprogram W (λ, α) first checks whether the signature of path(x, root(y)) is actually
equal to S. It happens if and only if root(x) and root(y) belong to the same tree in Fλα .
We check this with the Relative Membership Tool (Tool 1) using two permutations, where
the blocks are sets of elements z of P that have root(z) in the same Q from Fλα . If it turns
out that root(x) and root(y) are in different subtrees from Fλα then the whole program NS
outputs 0. If root(x) and root(y) lie in the same Q ∈ Fλα , W (λ, α) is designed to check
one more, final, thing: whether sλ ∈ dest-col(< y). This is a simple application of the Set
Membership Tool (Tool 3). For this we need again 3 permutations. If sλ 6∈ dest-col(< y)
then NS one more time outputs 0. Otherwise NS outputs 1.
3.5. The case when x is left of y in T . When designing the corresponding branching
program we will closely follow the previous case. Accordingly we start by the appropriate
variant of Corollary 9, namely with a direct corollary of Lemma 7. To simplify notation, for
the meet of root(x) and root(y) we will again write mx,y .
Corollary 10. Let x, y be different elements in P such that x is left of y in T . Then x < y
in P if and only if there exist a vector v ∈ Active(mx,y ) and two color sequences (γ0 > γ1 >
· · · > γ` ), and (δ0 > δ1 > · · · > δm ) such that γ0 = δ0 , γ` ∈ dest-col(> x), δm ∈ dest-col(< y)
and the paths path((mx,y , v), root(x)), path((mx,y , v), root(y)) have signatures (γ0 , γ1 , . . . , γ` )
and (δ0 , δ1 , . . . , δm ) respectively.
Now we are ready to define the corresponding branching program. Just like before the root
node Nx left of y is a major parallel node. It has a child N (S, R) for every possible pair of color
sequences S = (s0 > s1 > · · · > sλ ), R = (r0 > r1 > · · · > rµ ) such that s0 = r0 . It ouptuts a 1
if and only if there is a vector v ∈ Active(mx,y ) such that path((mx,y , v), root(x)) has signature
(s0 , s1 , . . . , sλ ), path(mx,y , v), root(y)) has signature (r0 , r1 , . . . , rµ ), sλ ∈ dest-col(> x) and

2
k+1
rµ ∈ dest-col(< y). The number of such possible pairs is clearly at most 25
.
For given S and R the node NS,R will have two children Nx,S and Ny,R . The task of Nx,S will
be to check whether there is a vector v ∈ Active(mx,y ) such that path((mx,y , v), root(x)) has
signature (s0 , s1 , . . . , sλ ) and sλ ∈ dest-col(> x). The task of Ny,R is defined in a symmetric
manner. If both of these subprograms succeed then NS,R evaluates to 1, otherwise it evaluates
to 0. As the two subprograms at these nodes are by symmetry identical, in what follows we
will only focus on the description of the subprogram rooted at Nx,S .
The subprogram for Nx,S makes use of the families Fiα of trees introduced in Subsection 3.4.
It starts with checking whether there is a vector v ∈ Active(mx,y ) of Γ-color s0 , which happens
if and only if mx,y is a vertex of some tree Q ∈ F(s0 ). This can be verified by the extended
Red-Green Detection Tool (Tool 5) with a single permutation. Thus, color some of the edges
in T as follows: For every Q ∈ F(s0 ) and every vertex t of Q color all edges going from t to
some of its children t0 in T with color Red and all other edges Green. Then mx,y is a vertex
of some tree Q ∈ F(s0 ) if and only if the first colored edge on the path from mx,y to root(x)
is Red. If the answer to this question is no, we return 0. Otherwise Nx,S proceeds step by

BOOLEAN DIMENSION AND TREE-WIDTH

19

step verifying whether the consecutive colors of the signature of path((mx,y , v), root(x)) agree
with S.
From now on, to simplify notation, for the dag vertex (mx,y , v) we will use that shorthand
notation m∗x,y .
Following the argumentation from Subsection 3.4 we define now for every 0 6 i 6 λ and
α ∈ {0, 1, 2}i a subprogram W (i, α). The branching program is going to visit a sequence of
these subprograms starting with W (0, ∅). We always make sure that when W (i, α) is called
then the following invariant has been established:
The sequence (s0 , . . . , si ) is a prefix of the signature of path(m∗x,y , root(x)).
Moreover,
(i) if (s0 , . . . , si ) is a proper prefix of the signature of path(m∗x,y , root(x))
then there is a tree Q∗ in Fiα such that mx,y is in Q∗ and t is a leaf of Q∗
where t is the unique vertex in T such that path(m∗x,y , t) is the maximal
prefix of path(m∗x,y , root(x)) with signature (s0 , . . . , si ).
(ii) otherwise when the signature of path(m∗x,y , root(x)) is equal (s0 , . . . , si ),
there is a tree Q in Fiα such that mx,y and root(x) are both in Q.
Note that the invariant holds for W (0, ∅) as we already know that the Γ-color of m∗x,y is s0
and the tree T (root(z), s0 ) ∈ F0∅ = F(s0 ) contains tree(m∗x,y , s0 ) as a subtree for some z ∈ P ,
and so witnesses (i) or (ii).
We proceed with the description of W (i, α) (with 0 6 i < λ and α ∈ {0, 1, 2}i ). This
subprogram consists of two steps.
Step 1 The first task of W (i, α) is to establish whether path(m∗x,y , root(x)) has a prefix with
signature (s0 , . . . , si+1 ). This will be done using a single permutation with the extended
Red-Green Detection Tool (Tool 5). Thus, color some of the edges in T as follows: For
all Q ∈ Fiα , all leaves t of Q and all edges (t, t0 ), t being a parent of t0 , color the edge Red
if si merges into si+1 at (t, t0 ), otherwise color it Green. Looking at the relative positions
of x and y in the permutation π generated by the tool the program learns whether the first
colored edge on the path from mx,y to root(x) is Red or not. If the answer is no (i.e. the
first colored edge is Green or there is no colored edge), then path(m∗x,y , root(x)) contains no
merge from si to si+1 and the whole program Nx,S outputs a 0. On the other hand if the
first colored edge on this path is Red, then it has been established that path(m∗x,y , root(x))
has a prefix with signature (s0 , . . . , si+1 ).
Note that at this point if Nx,S is still running then we know that item (i) of the invariant
holds. Indeed, (s0 , . . . , si ) is a proper prefix of (s0 , . . . , si+1 ) which as we learnt is the prefix
of the signature of path(m∗x,y , root(x)). Let Q∗ be a tree in Fiα witnessing the item (i) and
let t∗ be the leaf of Q∗ on path(m∗x,y , root(x)). In particular, we know that root(y) 6∈ Q∗ .
Step 2 The second task of W (i, α) is to decide which subprogram to continue with, i.e. which
α,0
α,1
α,2
is the relevant family for the (x, y)-query out of Fi+1
, Fi+1
and Fi+1
.
α,0
The family Fi+1
is relevant if there is no si+1 -break on the path from mx,y to the leaf t∗
in Q∗ . This again can be done using a single permutation with the extended Red-Green
Detection Tool (Tool 5). Color the edges of T as follows: For all Q ∈ Fiα , all leaves t of
Q and all edges (t, t0 ), where t is a parent of t0 , color the edge (t, t0 ) Green. For each
vertex t ∈ T which is an si+1 -break color all edges from t going to its children in T with

20

S. FELSNER, T. MÉSZÁROS, AND P. MICEK

Red (possibly overriding Green). From the permutation π generated by the extended
Red-Green Detection Tool the program learns whether the first colored edge from mx,y to
root(x) is Red or not. Note that as root(x) 6∈ Q∗ we necessarily have a colored edge on this
path.
If the first colored edge on the path from mx,y to root(x) is Green then there is no si+1 break on the path from mx,y to t∗ -path in T and the next subprogram called is W (i + 1, α0).
Note that the required invariant holds.
If the first colored edge on the path from mx,y to root(x) is Red then there is an si+1 break on the path from mx,y to t∗ in T . In this case we know that Fiα+ contains a tree Q+
which contains the maximal prefix of path(m∗x,y , root(x)) with signature (s0 , . . . , si+1 ). Now
α,1
α,2
it is up to deciding whether this tree Q+ belongs to Fi+1
or to Fi+1
. The set of trees in
α,1
α,2
α+
α
Fi = Fi+1 ∪ Fi+1 has been produced as an offspring of trees in Fi , and Q+ is actually the
offspring Q∗,+ of Q∗ in this union. Now consider the partition of Fiα into three subfamilies,
α,1
α,2
those with an offspring in Fi+1
, those with an offspring in Fi+1
, and the rest. Since the
α
∗
trees in Fi are disjoint mx,y is contained only in Q which is in one of these three families.
With a repeated application of the extended Red-Green Detection Tool (Tool 5) we can
identify, using only two permutations, the subfamily containing Q∗ . First take the subfamily
α,1
containing those trees from Fiα whose offspring is in Fi+1
. For every tree Q in this family
and every vertex t of Q color all edges going from t to its children in T with Red and color
all the other edges Green. From the permutation provided by the tool the program learns
whether the first edge on the path from mx,y to root(x) is Red or not. The answer is yes
exactly if mx,y is in on of the trees from the first subfamily. After possibly repeating this for
the second subfamily, we will know in which of them is Q∗ .
On the basis of this W (i, α) decides whether W (i + 1, α1) or W (i + 1, α2) has to be called
next. Whichever is chosen we have made sure that the invariant holds.
This completes the description of the subprograms W (i, α) for 0 6 i < λ and α ∈ {0, 1, 2}i .
It remains to describe the finishing subprograms W (λ, α) with α ∈ {0, 1, 2}λ . By the
invariant we do know that S = (s0 , . . . , sλ ) is the prefix of the signature of path(m∗x,y , root(x)).
The subprogram W (λ, α) first checks whether the signature of path(m∗x,y , root(x)) is actually
equal to S. It happens if and only if mx,y and root(x) belong to the same tree in Fλα . We check
this again with the extended Red-Green Detection Tool (Tool 5) using one permutation.
Color all edges of T that do not belong to any tree Q ∈ Fλα with color Red and keep all
the other edges uncolored. Then from the permutation constructed by the tool the program
learns whether the first edge on the path from mx,y to root(x) is Red or not. In our case this
is the same as asking whether there is a Red edge on this path or not, and so the answer is
no exactly if mx,y and root(x) belong to the same tree in Fλα .
If it turns out that mx,y and root(x) are in different subtrees from Fλα then the whole
program Nx,S outputs 0. If they lie in the same Q ∈ Fλα , W (λ, α) is designed to check one
more, final, thing, namely whether whether sλ ∈ dest-col(> x). This is a simple application
of the Set Membership Tool (Tool 3). For this we need 3 permutations. If sλ 6∈ dest-col(> x)
then Nx,S outputs again 0, otherwise it outputs 1.

BOOLEAN DIMENSION AND TREE-WIDTH

21

References
[1] Nicolas Bonichon, Cyril Gavoille, and Arnaud Labourel. Short labels by traversal and jumping. In 6th
Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications,
volume 28 of Electron. Notes Discrete Math., pages 153–160, 2007.
[2] Graham R. Brightwell and Paolo Giulio Franciosa. On the Boolean dimension of spherical orders. Order,
13(3):233–243, 1996.
[3] Ben Dushnik and Edwin W. Miller. Partially ordered sets. Amer. J. Math., 63:600–610, 1941.
[4] Gwenaël Joret, Piotr Micek, Kevin G. Milans, William T. Trotter, Bartosz Walczak, and Ruidong Wang.
Tree-width and dimension. Combinatorica, 36(4):431–450, 2016. arXiv:1301.5271.
[5] Gwenaël Joret, Piotr Micek, William T. Trotter, Ruidong Wang, and Veit Wiechert. On the dimension
of posets with cover graphs of treewidth 2. Order, to appear. arXiv:1406.3397.
[6] Gwenaël Joret, Piotr Micek, and Veit Wiechert.
[7] David Kelly. On the dimension of partially ordered sets. Discrete Math., 35:135–156, 1981.
[8] J. Nešetřil and P. Pudlák. A note on Boolean dimension of posets. In Irregularities of partitions (Fertőd,
1986), volume 8 of Algorithms Combin. Study Res. Texts, pages 137–140. Springer, Berlin, 1989.
[9] Noah Streib and William T. Trotter. Dimension and height for posets with planar cover graphs. European
J. Combin., 35:474–489, 2014.
[10] Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J. ACM,
51(6):993–1024, 2004.
[11] William T. Trotter and Bartosz Walczak. Boolean dimension and local dimension, 2017. arXiv:1705.09167,
accepted at EuroComb 2017.
[12] William T. Trotter, Jr. and John I. Moore, Jr. The dimension of planar posets. J. Combinatorial Theory
Ser. B, 22(1):54–67, 1977.
[13] Bartosz Walczak. Minors and dimension. J. Combin. Theory Ser. B, 122:668–689, 2017. preliminary
version in SODA 2015, arXiv:1407.4066.

