arXiv:1704.02939v2 [] 4 Jul 2017

Minor-matching hypertree width
Nikola Yolov
nikola.yolov@cs.ox.ac.uk
Department of Computer Science
University of Oxford
March 30, 2018
Abstract
In this paper we present a new width measure for a tree decomposition, minor-matching
hypertree width, µ-tw, for graphs and hypergraphs, such that bounding the width guarantees
that set of maximal independent sets has a polynomially-sized restriction to each decomposition bag. The relaxed conditions of the decomposition allow a much wider class of graphs
and hypergraphs of bounded width compared to other tree decompositions. We show that,
n
1
for fixed k, there are 2(1− k +o(1))( 2 ) n-vertex graphs of minor-matching hypertree width at
most k. A number of problems including Maximum Independence Set, k-Colouring, and
Homomorphism of uniform hypergraphs permit polynomial-time solutions for hypergraphs
with bounded minor-matching hypertree width and bounded rank. We show that for any
given k and any graph G, it is possible to construct a decomposition of minor-matching hy3
pertree width at most O(k 3 ), or to prove that µ-tw(G) > k in time nO(k ) . This is done by
presenting a general algorithm for approximating the hypertree width of well-behaved measures, and reducing µ-tw to such measure. The result relating the restriction of the maximal
independent sets to a set S with the set of induced matchings intersecting S in graphs, and
minor matchings intersecting S in hypergraphs, might be of independent interest.

1

Introduction

In his classical paper [Tar85], Tarjan discusses divide and conquer algorithms for solving
problems on chordal graphs using a tree decomposition where every bag is a clique. Since
chordality is independent of the much more widely used notion of treewidth [RS84], it is
a natural question to unify the two tree decompositions into a single one. For instance,
we may consider a tree decomposition of a graph, with width measured as the maximum
independence number of a bag, say α-tw(G), instead of the maximum number of vertices in
a bag less 1, tw(G). This indeed unifies the two decompositions, as a graph G is chordal if
and only if α-tw(G) = 1 and clearly α-tw(G) ≤ tw(G) + 1.
However, it turns out that α-tw(G) is often not general enough. For instance, consider
the k-Colouring problem. It is possible to determine if χ(G) ≤ k in polynomial time for
graphs with bounded α-tw(G), since there are polynomially many distinct colourings of each
bag, we may enumerate all of them and apply dynamic programming. Nevertheless, the
class of graphs {G : α-tw(G) ≤ k} is not a new polynomial case of the problem, because
tw(G) ≤ α-tw(G)χ(G). However, with little more effort we can describe a much more relaxed
tree decomposition measure.
The trace (or restriction) of a set system F over a set S, denoted trS (F ) is defined as
{F ∩ S : F ∈ F }. Let us denote the set of all independent and all maximal independent sets
of a graph G by î(G) and i(G) respectively. Solving problems on graphs with α-tw(G) ≤ k

1

exploits the property that trB (î(G)) has polynomially-bounded size for each bag B of a tree
decomposition of G with bounded α-width, but it often suffices to require that trB (i(G)) has
bounded size. Let µ(G) denote the maximum size of an induced matching in G. Results in
graph theory [Far89, FHT93, Ale07] show that the relation between |î(G)| and α(G) is similar
v(G) 
to the relation between |i(G)| and µ(G): 2α(G) ≤ |î(G)| ≤ ≤α(G)
and 2µ(G) ≤ |i(G)| ≤

e(G)
. Now let the S-intersecting induced matching number, µG (S), be the maximum size
≤µ(G)
of an induced matching M of G such that every edge of M intersects S ⊆ V (G). Clearly
α(G[S]) ≥ µG (S), since taking a vertex from every edge of an induced matching forms an
independent set. On the contrary, µG (S) cannot be bounded from below using α(G[S]), since
α(En ) = n, while µ(En ) = 1, where En is the n-vertex empty graph. In this paper we show
that trS (i(G)) is polynomially bounded if µG (S) is bounded. This result is of independent
interest, but in particular it motivates the parameter that is discussed in this paper, µ-tw(G),
a width measure of graphs, defined as the minimum over all tree decompositions of G of the
maximum intersecting induced matching number over the bags of the decomposition.
Hypergraphs often have much more expressive power for modelling problems compared
to graphs. All results above generalise to hypergraphs H, but the definition of µH (S) is too
technical to be defined here, so we postpone it to § 2.
When comparing different tree decompositions, usually the following four questions are
considered. The first one is on what structures does the decomposition work. The original
treewidth decomposition is defined on graphs, but later work introduces tree decompositions for hypergraphs, for example Hypertreewidth [GLS99] and Fractional hypertree width
decompositions [GM06]. The decomposition in this paper yields efficient algorithms for hypergraphs with hyperedges of bounded size. It is not clear whether or not the restriction on
the size of the hyperedges is necessary, but so far we can only guarantee polynomial-time
solutions when the condition holds.
The second question is what is the number of structures with bounded width. Here minormatching hypertree decompositions really stand out, as most graphs and hypergraphs have
much lower minor-matching hypertree width compared to other width measures. We show
n
1
that, for fixed k, there are 2(1− k +o(1))( 2 ) n-vertex graphs with minor-matching hypertree
n
width at most k (the number of all n-vertex graphs is 2( 2 ) ). In comparison, most tree
decompositions permit 2O(n ln n) n-vertex graphs of width at most k. More detail is given at
the end of § 2.
The next question is what family of problems can be solved in polynomial time provided
a decomposition of the instance with bounded width is given as input. For the moment there
is no meta-theorem similar to Courcelle’s theorem [Cou90], describing classes of computable
problems, and instead we give examples how to solve Maximum Weighted Independent
Set, k-Colouring and Homomorphism of Uniform Hypergraphs in § 2. Other problems, like Set Cover and k-SAT, also have natural solutions using the developed methods.
The final question is is it possible to efficiently construct a tree decomposition of width
k, or more generally f (k), given a structure of width at most k. This problem is essential,
as it allows us to drop the requirement to provide a tree decomposition in the input of the
problem, and find truly polynomial cases of hard problems. A tree decomposition without
this property has limited use, since it may be as hard to find a decomposition as to solve the
problem. Given a fixed k and a problem P that permits a polynomial solution of instances
(I, T ), where T is a decomposition of width at most k, it suffices to construct decomposition
3
of width f (k) to solve P (I), as f (k) is also bounded from above. In § 4 we present an nO(k ) time algorithm that given a graph G either finds a tree decomposition of G with µ-width
O(k 3 ), or proves that µ-tw(G) > k. An intermediate step is a similar result for α-tw(G) of
hypergraphs.
The paper is organised as follows. In § 2 we present minor-matching hypertree width and
its preliminaries, discuss how it compares with other treewidth measures, present the Intersecting Minor-Matching Theorem, which is the main tool that makes dynamic programming

2

over minor matching hypertree decompositions possible, explain how to use the Intersecting
Minor-Matching Theorem, and give examples how to solve problems using a minor-matching
hypertree decomposition. In § 3 we prove the Intersecting Minor-Matching Theorem, and in
§ 4 we explain how to approximate µ-tw, and more generally, well-behaved hypertree width
measures.

2

Minor-matching treewidth and preliminaries

2.1

Notation

All graph-theoretic notation is standard. The induced subgraph of G by a set S of vertices
is denoted by G[S]. A set of vertices is called independent or stable if it contains no edge.
The independence number of a graph G is the maximum size of an independent set, and
it is denoted by α(G). A hypergraph H = (V, E) is a pair of a set of vertices V and
a set E of subsets of V called edges or sometimes hyperedges. We also use V (H) and
E(H) to denote the sets of vertices and edges of H respectively. Independent sets and
the independence number of hypergraphs are defined the same way as in graphs, that is
sets that do not contain a hyperedge and the maximum size of such set respectively. If H
is a hypergraph, and S ⊆ V (H), we sometimes write trS (H) instead of trS (E(H)). For
a hypergraph H and S ⊆ V (H), we define the induced subhypergraph of H by S to be
H[S] = (S, {h ∈ E(H) : h ⊆ S}).

2.2

Tree decompositions

Definition 2.1 (Tree decomposition [BB72, Hal76, RS84]). We say that the pair T =
(T, {Bt : t ∈ V (T )}) is a tree decomposition of a graph G if T is a tree, Bt , called the bag
of t, is a subset of V (G) for each node t of T , and
1. for each vertex x of G, the nodes t of T such that x ∈ Bt , denoted Tx , induce a connected
subtree of T , and
2. every edge of G is contained in some bag Bt , where t ∈ V (T ).
We sometimes shorten (T, {Bt : t ∈ V (T )}) to (T, {Bt }) or even (T, Bt ). Instead of tree
decomposition we sometimes just say decomposition.
Definition 2.2 (λ-treewidth). Suppose that λG is a real-valued function on the subsets of
V (G) for each graph G. Given a graph G and a tree decomposition T = (T, {Bt }t∈V (T ) ) of
G, we define
λG (T ) = max λG (Bt ) and λ-tw(G) = min
λG (T ′ ),
′
T

t∈V (T )

to be the λ-width of T , and the λ-treewidth of G respectively, where the minimum is taken
over all tree decompositions T ′ of G.
If G is clear from the context, we normally abbreviate λG (T ) to λ(T ). Technically, we
ought to use inf instead of min in the definition of λ-tw, since the set of tree decompositions
is infinite, but by restricting the definition to decompositions with distinct bags, we obtain a
finite set. The nodes associated with the same bag induce a connected subtree, and hence we
may identify them to create a new decomposition with the same width. We may also require
that the set of bags forms a Sperner family without changing the width, and it is easy to see
that the size of the tree in such decomposition is at most n for an n-vertex graph. Therefore
we assume that every tree decomposition is either of this form, or implicitly converted to
this form, and do not pay close attention to the size.
Definition 2.3 (Treewidth). The treewidth [BB72, Hal76, RS84] of a graph G, tw(G), is
defined as κ-tw(G) for the function κG (S) = |S| − 1.

3

Treewidth plays a central role in the study of graph minors, but we are mainly interested
in applications to algorithms. It is NP-complete to determine the treewidth of a graph G,
but for fixed k there are linear-time algorithms, with an exponential dependency on k, to
construct a tree decomposition of width at most k or to decide that tw(G) > k [Bod96].
Definition 2.4 (Clique-width). The clique-width of a graph G, cw(G), is the minimum
number of labels needed to construct G from the following operations:
1. creating of a new vertex with label i,
2. disjoint union of two labelled graphs,
3. joining by an edge every vertex with label i to every vertex of label j, for given j 6= i,
and
4. renaming every label i to j.
A sequence of these operations creating a graph G using at most k labels is called k-expression
of G.
In contrast to treewidth, dense graphs may have low clique-width. For example, the
complete graph Kn has treewidth n − 1, while cw(Kn ) = 2 for n > 1. Moreover, a family
of graphs with bounded treewidth also has bounded clique-width; more precisely, as shown
in [CR05],
cw(G) ≤ 3 · 2tw(G)−1 .
The example with the complete graph shows that no general bound exists for the other
direction, but nevertheless, interesting special bounds do exist:
1. tw(G) ≤ f (∆(G), cw(G)) [CO00],
2. tw(G) ≤ g(k, cw(G)) for Kk -minor-free graphs G [CO00],
3. tw(G) ≤ 3 · cw(G)(t − 1) − 1 for Kt,t -free graphs G [GW00].
Similarly to treewidth, finding the clique-width of a graph is NP-complete, [FRRS06].
There is an O(f (k)v(G)3 )-time algorithm finding a (2k+1 − 1)-expression for a given input
graph G with clique width at most k [HO08].
Rank-width is a closely related width measure to clique-width.
Definition 2.5 (Rank-width). Suppose G is a graph and A is a subset of V (G). The cutrank of A, cutrkG (A), is the linear rank of the matrix {1ij∈E(G) : i ∈ A, j 6∈ A}. A ternary
tree is a tree where all non-leaves have degree 3. A pair (T, L) is called rank-decomposition
of G if T is a ternary tree and L is a bijection from the leaves of T to the vertices of G.
For every edge of e of T the connected components of T − e induce a partition (A, B) of the
leaves of T . Define the width of e to be cutrkG (L(A)) = cutrkG (L(B)), the width of (T, L)
to be the maximum width of an edge, and the rank-width of G, rw(G), to be the minimum
width of a rank-decomposition of G.
A key link between rank-width and clique-width has been established in [OS06]:
rw(G) ≤ cw(G) ≤ 2rw(G)+1 − 1.
The inequalities reveal that a family of graphs has bounded rank-width if and only if it has
bounded clique-width.
The importance of the width parameters above is best illustrated by Courcelle’s theorem.
Definition 2.6 (MSO1 , MSO2 ). A graph can be seen as a finite model with its vertices as
universe, and a single symmetric relation indicating adjacency. The monadic second-order
graph logic, MSO1 , consists of formulae for this model with quantifiers over vertices and
sets of vertices. A graph can also be seen as a finite model with its vertices and edges as
universe, and two symmetric relations indicating adjacency between vertices and edges. The
extended monadic second-order graph logic, MSO2 , consists of formulae for this model with
quantifiers over vertices, edges, sets of vertices and sets of edges.

4

Theorem 2.7 (Courcelle’s theorem [Cou90, BPT92, CMR00]). For every MSO1 formula ψ1
and every MSO2 formula ψ2 , there are functions f1 and f2 , such that there are O(f1 (cw(G))n)time and O(f2 (tw(G))n)-time algorithms to test if G |= φ1 and G |= φ2 respectively for every
n-vertex graph G.
We now turn our attention to tree decompositions of hypergraphs.
Definition 2.8 (Gaifman graph). The Gaifman graph H of a hypergraph H is a graph over
the same vertex set as H with two vertices joined by an edge whenever they appear in the
same hyperedge of H.
Definition 2.9 (Tree decomposition and width of hypergraphs). A pair T = (T, {Bt }t∈V (T ) )
is a tree decomposition of a hypergraph H whenever it is a tree decomposition of its Gaifman
graph. Given a real-valued function λH on the subsets of V (H) for every hypergraph H,
define λH (T ) and λ-tw(H) the same way they are defined for graphs.
The first hypergraph treewidth measure for which it is possible to construct a tree decomposition efficiently and it is not bounded in terms of the treewidth of the Gaifman graph
is generalized hypertree width.
Definition 2.10. [Generalized hypertree width [GLS99]] The generalized hypertree width of
a hypergraph H is defined as ̺-tw(H), where ̺H (S) is the minimum size of a cover of S by
edges of H.
As the name suggests, there is a notion called hypertree width. Hypertree width, ̺′ -tw(H),
involves an additional technical restriction on the tree decomposition, but as shown in [AGG07],
̺-tw(H) ≤ ̺′ -tw(H) ≤ 3̺-tw(H), and hence the two notions are essentially equivalent.
There is a polynomial-time algorithm to determine if ̺′ -tw(H) ≤ k for fixed k, therefore it
is possible to approximate ̺-tw within a factor of 3 for small k.
Definition 2.11. [Fractional cover number] A fractional cover
Pof S ⊆ V (H) by H, is a
function γ : E(H) → [0, 1], such that for each s ∈ S we have h∈E(H):s∈h γ(h) ≥ 1. The
P
∗
weight of a fractional cover γ is
h∈E(H) γ(h). The fractional cover number, ̺H (S), is
defined as the minimum weight of a fraction cover.
Definition 2.12 (Fractional hypertree width [GM14]). We define ̺∗ -tw to be fractional
hypertree width.
Clearly, ̺∗H (S) ≤ ̺H (S), and hence ̺∗ -tw(H) ≤ ̺-tw ≤ ̺′ -tw. Given a hypergraph H
and a constant k, it is possible to construct a tree decomposition of H of ̺∗ -width O(k 3 ), or
3
to prove that ̺∗ -tw(H) > k in time ||H||O(k ) [Mar10].
A critical property of generalised hypertree width and fractional hypertree width is that
constraint satisfaction problems can be solved efficiently on instances of bounded width.
Definition 2.13. A constraint satisfaction problem (CSP) is a triple of variables V , a
domain D, and a set C of constraints, where each constraint is a relation on a subset of the
variables. The task is to assign a value from D to each variable so that each constraint is
satisfied.
For instance, graph colouring can be expressed as a CSP. The domain D is the set of
available colours and there is a constraint requiring each edge to be coloured properly. We
can also interpret 3-SAT as a CSP: the domain is D is {0, 1} and each constraint corresponds
to a clause.
Definition 2.14 (Constraint hypergraph). The hypergraph with the variables of an instance
I of CSP as vertices and a hyperedge of each constraint is called constraint hypergraph of
I, C(I).

5

Theorem 2.15. Given a tree decomposition T of C(I), it is possible to solve an instance I
∗
of a CSP in time ||I||̺(T )+O(1) [GLS99] and ||I||̺ (T )+O(1) [GM14]. Here ||I|| is the sum of
the number of variables, the number of tuples in each constraint relation, and the size of the
domain.
The rank of a hypergraph H, rk(H), is the maximum size of an edge of H. It is easy to
see that
̺-tw(H) + 1 ≤ tw(H) ≤ rk(H)(̺∗ -tw(H) + 1) ≤ rk(H)(̺-tw(H) + 1),
and hence the classes of hypergraphs with restricted rank and width in either notion are
essentially equivalent.
Theorem 2.16. Let CSP(H) denote all CSP instances with constraint graph in a recursively
enumerable class H of bounded rank. Assuming FTW 6= W[1], the following two conditions
are equivalent:
1. CSP(H) is polynomially solvable,
2. H has bounded treewidth.
The condition FTW 6= W[1] is a widely assumed hypothesis in parameterised complexity.
On the contrary, minor-matching hypertree width cannot be bounded from below in terms
of rk(H) and tw(H), and therefore CSPs are computationally unfeasible.

2.3

Minor-matching hypertree width

To define minor-matching hypertree width, we need some blocker machinery. The first
observation is that non-minimal edges of a hypergraph play no role in whether a set of
vertices is independent or not.
Definition 2.17 (Clutter). A hypergraph is called clutter if no edge is a proper subset of
another. Given a hypergraph H, we define cl(H) to be the clutter containing all inclusionwise minimal edges.
Note that the complement of each independent set is a hitting set, also called transversal.
Definition 2.18 (Blocker). A transversal of a clutter H is a set intersecting every edge of
H. The blocker of H, denoted b(H), is the clutter consisting of all inclusion-wise minimal
transversals of H.
One reason why b(H) is more natural to work with compared to i(H) is that b(b(H)) = H,
while it is not generally true that i(i(H)) = H.
Definition 2.19 (Deletion and Contraction). Suppose H is a clutter and v ∈ V (H). We
define H\v, called H with v deleted, to be the clutter (V (H) \ {v}, {h ∈ E(H) : v ∈
/ h}). We
define H/v, called H with v contracted, to be the clutter cl(V (H)\{v}, {h\{v} : h ∈ E(H)}).
Definition 2.20 (Minor). We say that F is a minor of H, denoted F ⊆M H, if F can be
obtained from H through a series of deletions and contractions.
We note that this notion of clutter minor is different from the more widely used notion
of graph minor. By “minor”, in this paper, we always mean clutter minor and never graph
minor. The names coincide because a graph minor renders a clutter minor in the graphic
matroid.
A critical property of minors is that deletion and contraction commute, that is H\v/u =
H/u\v, H\v\u = H\u\v and H/v/u = H/u/v, and therefore the order of the operations in
the definition of minor does not matter. Even though the objects above have a rich algebraic
structure, we only use some very basic observations: b(b(H)) = H, b(H\v) = b(H)/v,
b(H/v) = b(H)\v and F ⊆M H if and only if b(F ) ⊆M b(H).

6

A minor F of a graph G contains edges of size 0, 1 and 2. In case F contains the empty
set as an edge, then F contains no other edges and has no independent sets. If F contains
an edge of size 1, say {v}, no other edge contains the vertex v, since F is a clutter, so these
vertices play no significant role in the structure of F , and we may ignore them. The rest of F
is an induced subgraph of G. In particular, we see that if F is a graph, then F is an induced
subgraph of G. We conclude that the minor and induced subgraph relations coincide over
the set of graphs.
A clutter F is called matching if it is isomorphic to a graph matching, F ∼
= kK2 , that is
F contains k parallel edges of size 2 and no other edges.
Definition 2.21. Denote by µ(H) the maximum number of edges in a matching which is
a minor of cl(H); and by µH (S) the maximum number of edges in a matching F which is
a minor of cl(H), and every edge of F intersects S, called S-intersecting minor-matching
number.
Similarly to induced subgraphs, if kK2 ⊆M H, then b(kK2 ) ⊆M b(H), and hence |i(H)| =
|b(H)| ≥ |b(kK2 )| = 2k . In addition, if F ⊆M H, then |trS (F )| ≤ |trS (H)|, so |trS (i(H))| ≥
2µH (S) . In this work we give a bound in the other direction, namely:
Theorem 2.22. [Intersecting Minor-Matching Theorem] There exists a function f
such that for every n-vertex hypergraph H and any set of vertices S we have
|trS (b(H))| ≤ nµH (S)f (rk(H)) .
Additionally, if µH (S) and rk(H) are bounded, then trS (b(H)) can be computed in polynomial
time.
The theorem is of independent interest. Its proof is postponed to § 3.
We are now ready to state the definition of minor-matching hypertree width.
Definition 2.23 (Minor-matching hypertree width). We define µ-tw(H) to be the minormatching hypertree width of H.

2.4

Solutions that can be read from the blocker

Suppose H, H1 and H2 are hypergraphs. We write H = H1 ∪ H2 if V (H1 ) ∪ V (H2 ) = V (H)
and E(H1 ) ∪ E(H2 ) = E(H). If H = H1 ∪ H2 , we say that S is an (H1 , H2 )-separator if
V (H1 ) ∩ V (H2 ) ⊆ S.
Suppose we want to compute a parameter fH . If it is possible to generalise fH to a
∅
S
function fH
over trS (i(H)), say fH = fH
(∅), for any S ⊆ V (H), and it is possible to
S
S
S
compute fH from fH1 and fH2 , where S is an (H1 , H2 )-separator, then, roughly speaking,
we can compute fH given a tree decomposition T with µ(T ) ≤ k. The next lemma formalises
the discussion above.
S
S
Definition 2.24. We say that a function fH
: trS (i(H)) → Q, or more generally, fH
:
p
trS (i(H)) → Q, can be read from the blocker if it has the following properties:
V (H)

1. it is possible to compute fH

from i(H) efficiently,
′

S
S
efficiently if S ⊆ S ′ ,
from fH
2. it is possible to compute fH
S∪{v}

S
, where H + v is a hypergraph obtained from
3. it is possible to compute fH+v from fH
H by adding a new isolated vertex, v,
S
S
S
from trS (i(H)), fH
4. it is possible to compute fH
and fH
efficiently if V (H1 )∩V (H2 ) ⊆
1
2
S and H = H1 ∪ H2 ,

for every hypergraph H and set S ⊆ V (H). Here efficiently means in polynomial time with
respect to the size of the input, including trS (i(H)), and the size of the output where all
functions are represented in table form.

7

Lemma 2.25. Suppose r and k are fixed constants. Let H be a hypergraph of rank at most
S
r, T = (T, {Bt }) be a tree decomposition of H with µ(T ) ≤ k, and fH
be a function that can
Bt
be read from the blocker. It is possible to compute fH from (H, T ) in polynomial time w.r.t.
∅
||H|| for every bag Bt , t ∈ T . In particular, it is possible to compute fH
in polynomial time.
Proof. Given a bag Br , pick r as the root of T and orient every edge from the root towards
the leaves. Let Tt be the subtree of T composed of descendants of t, and let Ht be the
Bt
subhypergraph of H induced by the vertices contained in bags of Tt . We compute fH
t
Bl
recursively, from the leaves towards the root. We can compute fH
for
each
leaf
l
of
T
using
l
Bt ∩Bti

property 1. of f . Given a node t with direct descendants t1 . . . tm , first compute fHt

i

using

Bt
property 2., then add each vertex in Bt \ Bti as an isolated vertex to compute fH
ti +(Bt \Bti )
Bt
Bt
using property 3., and finally merge sequentially fBBtt with fH
to
construct
fH
.
t
ti +(Bt \Bti )

Theorem 2.22 guarantees that trBt (i(H)) is polynomially sized and that it can be computed
in polynomial time, and hence the input and the output of each step is polynomially sized.

2.5
2.5.1

Examples of functions that can be read from the blocker
Maximum Weighted Independent Set

Our first example is Maximum Weighted Independent Set. On instance hypergraph
H and a weight function w : V (H)
P → Q, the problem is to find an independent set J of
H with maximum value w(J) = j∈J w(j). Delete all vertices v with w(v) < 0, and now
S
we may restrict our attention to maximal independent sets J ∈ i(H). Define fH
(A) :=
S
max{w(J) : J ∈ i(H), A = S ∩ J}. It suffices to show that fH
can be read from the
blocker in order to prove that the problem can be solved in polynomial time using a tree
decomposition of bounded µ-width. Properties 1.-3. are easy to verify. Suppose H = H1 ∪H2
S
and V (H1 ) ∩ V (H2 ) ⊆ S and that fH
(A) is witnessed by J ∈ i(H). Since J is stable in H1
and H2 , we may find Ji ∈ i(Hi ) such that J ∩ V (Hi ) ⊆ Ji . In particular, A ⊆ Ji ∩ S. We
have
w(J) = w(J1 ) + w(J2 ) − w(J1 ∩ S) − w(J2 ∩ S) + w(A).
S
It follows that w(Ji ) = fH
(Ji ∩ S), and hence
i
S
S
S
(A2 ) − w(A1 ) − w(A2 ) + w(A) :
(A1 ) + fH
fH
(A) = max{fH
2
1
A1 ∈ trS (i(H1 )), A2 ∈ trS (i(H2 )), A = A1 ∩ A2 }.

2.5.2

k-Colouring

A more interesting example is k-Colouring. A colouring with k colours is a function c :
V (H) → [k]. A colouring c is called proper if no edge is monochromatic, that is all of its
vertices are coloured the same. The chromatic number of H, χ(H), is the minimum number
of colours in a proper colouring.
We need to phrase the problem is terms of maximal independent sets in order to tackle
it. Suppose c : V (H) → [k] is a proper colouring. Observe that c−1 (a) is an independent
set for each colour a. Therefore χ(H) is the minimum size of a cover of H with independent
sets. We may assume that each independent set in the cover is maximal. Given i(H), we
can easily see if χ(H) ≤ k: simply check if any k-tuple (I1 , I2 , . . . , Ik ) of independent sets
covers H.

8

Consider the function

S
fH
(A1 , A2 , . . . , Ak ) =


1








0

if (A1 , A2 , . . . , Ak ) covers S and
there exists a cover (I1 , I2 , . . . , Ik ) of H,
s.t. Ii ∈ i(H) and Ai ⊆ Ii for 1 ≤ i ≤ k;
otherwise.

S
It is easy to see that fH
satisfies properties 1.-3. of Definition 2.24.

Lemma 2.26. Suppose H = H1 ∪H2 , V (H1 )∩V (H2 ) ⊆ S, and {Ai ∈ trS (i(H))}i∈[k] covers
S. The following two conditions are equivalent:
S
1. fH
(A1 , A2 , . . . , Ak ) = 1,
S
2. we can find Aji ∈ trS (i(Hj )), i ∈ [k], j ∈ [2], such that Ai ⊆ A1i ∩A2i , and fH
(Aj1 , Aj2 , . . . , Ajk ) =
j
1 for j ∈ [2].
S
Proof. First suppose that fH
(A1 , A2 , . . . , Ak ) = 1 and that it is witnessed by (I1 , I2 , . . . , Ik ).
j
We see that Ji = V (Hj )∩Ii is stable in Hj , hence we may find Iij ∈ i(Hj ) such that Jij ⊆ Iij .
S
Observe that (I1j , I2j , . . . , Ikj ) covers Hj . Therefore fH
(I1j ∩ S, I2j ∩ S, . . . , Ikj ∩ S) = 1.
j

Conversely, suppose that the second condition holds and that it is witnessed by (I1j , I2j , . . . , Ikj ).
We may write Ji = (Ii1 ∪Ii2 )\S ∪Ai to cover H with k (not necessarily maximal) independent
sets. Extend each Ji to a maximal independent set Ii ∈ i(H) to complete the proof.
∅
S
The lemma proves that fH
satisfies condition 4. of Definition 2.24. Clearly fH
(∅k ) = 1
if and only if χ(H) ≤ k.

2.5.3

Hypergraph Homomorphism

Suppose H and F are hypergraphs. A (not-necessarily injective) mapping f : V (H) → V (F )
is called homomorphism if the image of each edge of H is an edge of F . The existence of a
homomorphism between H and F is denoted by H → F . The framework of homomorphisms
has a rich expressive power to describe graph-theoretic properties. For instance, χ(H) ≤ k
if and only if H → Kk , where Kk is the complete k-vertex graph.
As usual, we start by formulating the problem is terms of maximal independent sets. A
hypergraph is called uniform if all edges have the same size.
Lemma 2.27. Suppose H and F are r-uniform hypergraphs. A mapping f : V (H) → V (F )
is a homomorphism if and only if f −1 (I) ∈ î(H) for every I ∈ i(F ).
Proof. If f is a homomorphism, then clearly f −1 (I) is stable for each I ∈ i(F ), as otherwise
the image of any edge contained in f −1 (I) is not an edge.
Suppose f : V (H) → V (F ) is a function such that f −1 (I) ∈ î(H) for every I ∈ i(F ). Let
h be an edge of H and let f (h) be its image. Since H and F are r-uniform, f (h) is either
an edge of F or stable. If f (h) is stable, let I ∈ i(F ) be a maximal independent set of F
containing f (h). But now we see that h ⊆ f −1 (I), which is a contradiction, and hence f (h)
is an edge for every h ∈ E(H).
Lemma 2.28. Suppose H and F are r-uniform hypergraphs. The following two statements
are equivalent:
1. H → F ,

9

2. there exists a function g : i(F ) → i(H) such that




\
g(I) : x ∈ V (F )
Ax =


I∈i(F ),x∈I

covers V (H).

Proof. First suppose f : H → F is a homomorphism. Each f −1 (I) is stable in H for I ∈ i(F ),
so we may set g(I) = J, where J ∈ i(H) is an arbitrary maximal independent set containing
f −1 (I). Let v be an arbitrary vertex of H. We have v ∈ Af (v) , and therefore the sets Ax
cover V (H).
Now suppose g is a function satisfying condition 2. in the statement. For each vertex v of
H pick some arbitrary vertex x of F such that v ∈ Ax and set f (v) = x. Such a vertex exists,
because {Ax }x∈V (F ) covers V (H). Let I ∈ i(F ) be arbitrary. We see that f −1 (I) ⊆ g(I) is
stable in H, and therefore f is a homomorphism.
Now suppose F is a fixed r-uniform hypergraph and on instance r-uniform hypergraph
S
H we have to decide if H → F . Suppose i(F ) = {I1 , . . . , Ik }. Let fH
: trS (i(H))k → {0, 1}
be defined as follows:
S
fH
(A1 , . . . , Ak ) = 1 iff
1. there exists a k-tuple (J1 , . . . , Jk ) ∈ i(H)k such that {∩i:x∈Ii Ji }x∈V (F ) covers H;
2. {∩i:x∈Ii Ai }x∈V (F ) covers S; and
3. Ai ⊆ Ji .
∅
S
Clearly fH
(.) = 1 iff H → F and fH
satisfies properties 1. - 3. of Definition 2.24. Property
4. follows from the following lemma.

Lemma 2.29. Suppose H = H1 ∪ H2 , V (H1 ) ∩ V (H2 ) ⊆ S, Ai ∈ trS (i(H)) for 1 ≤ i ≤ k
and {∩i:x∈Ii Ai }x∈V (F ) covers S. The following two conditions are equivalent:
S
1. fH
(A1 , . . . , Ak ) = 1,
S
2. we can find Aji ∈ trS (i(Hj )), i ∈ [k], j ∈ [2], such that Ai ⊆ A1i ∩A2i , and fH
(Aj1 , . . . , Ajk ) =
j
1 for j ∈ [2].
S
Proof. First suppose (J1 , . . . , Jk ) witnesses fH
(A1 , . . . , Ak ) = 1. We can find (J1j , . . . , Jkj ) ∈
j
k
S
i(Hj ) such that Ji ∩ V (Hj ) ⊆ Ji . It can be checked that fH
(J1j ∩ S, . . . , Jkj ∩ S) = 1.
j
Now suppose the second condition in the statement holds and that it is witnessed
by (J1j , . . . , Jkj ) ∈ i(Hj )k and (Aj1 , . . . , Ajk ) ∈ trS (i(Hj ))k . Find a k-tuple (J1 , . . . Jk ) ∈
i(H)k such that (Ji1 ∪ Ji2 ) \ S ∪ Ai ⊆ Ji . It is easy to check that (J1 , . . . Jk ) witnesses
S
fH
(A1 , . . . , Ak ) = 1.

2.6

Comparison with other tree decompositions

As discussed before, treewidth, hypertree width and fractional hypertree width are functionally bounded to each other for hypergraphs of bounded rank, while minor-matching hypertree
width cannot be bounded from below by treewidth even for graphs. For instance, consider
the complete graph, Kn . Since Kn is 2K2 -free, we have µ-tw(Kn ) = 1, while tw(Kn ) = n−1.
As for clique-width (or equivalently rank-width), it cannot be bounded functionally by
µ-tw. For instance, consider the graph G over Z4k+1 where i ∼ j if i > k + j mod 4k + 1.
We have that G is 2K2 -free, hence µ-tw(G) = 1, while cr(G) ≥ k. In the other direction, let
G0 = K1 , let G2n+1 be a complete union of two copies of G2n and let G2n+2 be a disjoint
union of two copies of G2n+1 . Clearly rkw(Gn ) = 1, while using the tools developed in § 4
we can see that µ-tw(G2n+1 ) = n.

10

Nevertheless, minor-matching hypertree width permits many more graphs of bounded
width and additionally it applies to hypergraphs as well as graphs. Indeed, every co-bipartite
2
graph (graph G with χ(G) ≤ 2) is 3K2 -free, and there are eΘ(n ) n-vertex co-bipartite graphs,
while the number of graphs with bounded clique-width by a fixed constant is eO(n ln n) .
We can give a more precise estimate on the size of the class of n-vertex graphs G with
µ-tw(G) ≤ k, call it Mn,k . Note that Mn,k contains all graphs G with χ(G) ≤ k, since
µ(G) ≤ α(G) ≤ χ(G) ≤ k; does not contain all bipartite graphs, not all split graphs, and not
all graphs with χ(G) ≤ k + 1 (for large n); and therefore the colouring number of Mn,k is
n
1
exactly k (for large n) and |Mn,k | = 2(1− k +o(1))( 2 ) by the colouring number theorem [Ale93,
BT97, BBS09, ABBM11]. Similar argument holds for graphs G with α-tw(G) ≤ k.
Lemma 2.30. The number of n-vertex graphs G with µ-tw(G) ≤ k (α-tw(G) ≤ k) is
n
1
2(1− k +o(1))( 2 ) .

3

Proof of the Intersecting Minor-Matching Theorem

This section is dedicated to proving the Intersecting Minor-Matching Theorem, Theorem 2.22.
We use the machinery developed in [Yol16]. We need preliminary definitions first.
Definition 3.1 (Join and Meet). Suppose H and F are clutters. Define
H ∨ F := cl(V (H) ∪ V (F ), E(H) ∪ E(F )),
H ∧ F := cl(V (H) ∪ V (F ), {h ∪ f : h ∈ E(H), f ∈ E(F )}).
Join and meet are dual: b(H ∨ F ) = b(H) ∧ b(F ) and b(H ∧ F ) = b(H) ∨ b(F ); and
they commute with deletion and contraction: (H ∨ F )\v = (H\v) ∨ (F \v). For a pair of
disjoint sets of vertices S and T of H, we denote the minor of H obtained by deleting S and
contracting T by H[S; T ].
Definition 3.2. Given a clutter H, and edge h ∈ E(H) and v, u 6= v ∈ h, define H ◦
(h, u, v) = H[u; h \ {u}] ∨ H[v; h \ {v}]. We call a sequence Π = {(hi , ui , vi )}ni=1 a quasimatching if
1. {vi , ui } ⊆ hi and vi 6= ui for each i ∈ [n],
2. hi+1 is an edge of (H ◦ (h1 , v1 , u1 )) ◦ . . . ◦ (hi , vi , ui ).
A quasimatching Π is called S-intersecting if each pair {vi , ui } intersects S ⊆ V (H).
Lemma 3.3. Suppose we are given a clutter H, a minimal transversal T of H, a set S ⊆
V (H) and a vertex x of H. Either
1. (i) there exists a minimal transversal T ′ ⊆ T \ {x} of H\x such that T ′ ∩ S = (T \
{x}) ∩ S; or
2. (ii) there exists a vertex z ∈ S \ {x} and an edge h ∈ E(H) such that x ∈ h, h∩T = {z}
and T \ {z} ∈ b(H ◦ (h, x, z)).
Proof. Case 1: For each z ∈ (T \ {x}) ∩ S there exists h ∈ E(H\x) such that h ∩ T = {z}.
Let T ′ ⊆ T \ {x} and T ′ ∈ b(H\x). Clearly T ′ ∩ S ⊆ (T \ {x}) ∩ S. To prove the opposite
direction, suppose t ∈ (T \ {x}) ∩ S. We can find h ∈ E(H\x) such that h ∩ T = {t}. But
since T ′ is a transversal of H\x – hence h ∩ T ′ is non-empty – and T ′ ⊆ T , it follows that
h ∩ T ′ = {t}, and therefore t ∈ T ′ ∩ S.
Case 2: There exists z ∈ (T \ {x}) ∩ S such that for each h ∈ E(H) if h ∩ T = {z}, then
x ∈ h.
Since z ∈ T and T is minimal, there is h ∈ E(H) such that h ∩ T = {z}. It is easy
to see that T \ {z} ∈ b(H[z, h \ {z}]). Let f ∈ H[x, h \ {x}], and let fb ∈ H be such that

11

f ⊆ fb ⊆ f ∪ (h \ {x}). Since x 6∈ fb we have fb ∩ T 6= {z}. Let y ∈ fb ∩ (T \ {z}), and hence
y ∈
/ h, so y ∈ f . But then (T \ {z}) ∩ f is non-empty, and f is arbitrary, so we conclude
that T \ {z} is (possibly non-minimal) transversal of H[x, h \ {x}]. The last statement in
conjunction with T \ {z} ∈ b(H[z, h \ {z}]) implies that T \ {z} ∈ b(H ◦ (h, x, z)).
Lemma 3.4. The size of trS (b(H)) is at most the number of S-intersecting quasimatchings.
Proof. We argue by induction. The claim trivially holds for clutters with one vertex. Suppose
the statement holds for clutters with less than n vertices.
If V (H) 6⊆ S, pick some x ∈ V (H) \ S, otherwise pick arbitrary x ∈ V (H). Let T1 ⊆
E(b(H)) be the set of minimal transversals of the first type described in Lemma 3.3, and let
T2 = E(b(H)) \ T1 .
If x ∈
/ S, then clearly trS (T1 ) ⊆ trS (b(H\x)). On the other hand, let A ∈ trS (b(H\x)) and
let T ′ ∈ b(H\x), such that T ′ = A ∩ S. In particular, we can find T ∈ {T ′ , T ′ ∪ {x}} ∩ b(H).
It follows that T ∈ T1 , A ∈ trS (T1 ) and finally trS (b(H\x)) ⊆ trS (T1 ). We conclude that
trS (T1 ) ≡ trS (b(H\x)), and therefore |trS (T1 )| = |trS (b(H\x))|.
If V (H) ⊆ S, then the mapping T 7→ T \ {x} is a bijection between T1 and b(H\x), and
hence
|trS (T1 )| = |T1 | = |b(H\x)| = |trS (b(H\x))|.
We see that |trS (T1 )| = |trS (b(H\x))| in either case.
The transversals of T2 fall in the second case of Lemma 3.3. Each A ∈ trS (T2 ) can be
found in trS (b(H ◦ (h, x, z))) + {z}, where “+” is an abuse of notation meaning that the
vertex z is added to each set in the trace, for an appropriate choice of a triple (h, x, z).
Finally we have
X
X
|trS (b(H ◦ (h, x, z)))|.
|trS (b(H))| ≤ |trS (b(H\x))| +
z∈S\{x} h∈E(H):{x,z}⊆h

Let qmS (H) denote the set of S-intersecting quasimatchings of H. By induction we have
|trS (b(H\x))| ≤ |qmS (H\x)|, and |trS (b(H ◦ (h, x, z)))| ≤ |qmS (H ◦ (h, x, z))|. In addition,
for every Π′ ∈ qmS (H ◦ (h, x, z)) we may construct Π = {(h, x, z)} ∪ Π′ ∈ qmS (H). Any
two quasimatchings constructed this way are distinct, as they either disagree on the triple
(h, x, z) (or the lack of such triple containing x) or are constructed from distinct members
qmS (H ◦ (h, x, z)) (or qmS (H\x)), and hence are distinct. We conclude that |trS (b(H))| ≤
|qmS (H)|.
Lemma 3.5. Suppose H is a rank r clutter and Π = {(hi , ui , vi )}ℓi=1 is a quasimatching of
size ℓ. There exists a subsequence j1 , . . . , jk of size k ≥ ℓ2−(r−2) /(2r − 3), such that
kK2 ∼
= {{uji , vji }}ki=1 ⊆M H.
Proof. It suffices to verify that quasimatchings are semi-matchings as defined in [Yol16],
Definition 3.1, and the lemma follows from Theorem 3.4 of [Yol16].
Proof of the Intersecting Minor-Matching Theorem, Theorem 2.22. Suppose m = µH (S) and
r = rk(H). The number of choices for a triple (h, v, u) is bounded by nr . The number of seP
quences of such triples of length at most ℓ is ℓk=1 nrk ≤ nr(ℓ+1) . If we set ℓ to be the length
of the longest S-intersecting quasimatching, we see by Lemma 3.5 that ℓ ≤ m2r−2 (2r − 3).
By Lemma 3.4 we conclude that
r−2

|trS (b(H))| ≤ nm2

(2r 2 −3r)+r

.

To make the theorem algorithmic, one may consider a branching algorithm, exploring all
cases of Lemma 3.3. The size of the recursion tree is bounded by the number of quasimatchings, hence the total running time is polynomial.

12

4 Approximation of µ-tw for graphs and α-tw for hypergraphs
This section is organised as follows. We start by arguing that finding decompositions of low
α and µ width for graphs is essentially equivalent. In § 4.1 we explain how to reduce a graph
G to a graph M (G) such that α-tw(G) = µ-tw(M (G)). Moreover, for every decomposition
T of M (G) we can find a decomposition M −1 (T ) of G such that α(M −1 (T )) ≤ µ(T ). The
main result of § 4.2 states that a reduction from µ-tw to α-tw exists with the same properties.
Recall that H is the Gaifman graph of H.
Definition 4.1. We say that a hypergraph width measure λH is well-behaved if
1. λH ({x}) ≥ 1 for each vertex x ∈ V (H),
2. λH (S ∪ T ) ≤ λH (S) + λH (T ),
3. λH (S ∪ T ) = λH (S) + λH (T ) for disjoint sets S and T such that EH (S, T ) = ∅,
4. λF (S) ≤ λH (T ) for each pair of hypergraphs F ⊇ H and sets S ⊆ T , and
5. λH (S) ≤ k can be decided in ||H||O(k) time.
Note that the independence number αH , the edge covering number ̺H (Definition 2.10),
and the fractional edge covering number ̺∗H (Definition 2.11), are all well-behaved, while µH
is not. The following theorem is proved in § 4.3.
Theorem 4.2. Suppose λH is a well-behaved width measure for hypergraphs. There exists
3
an algorithm with running time ||H||O(k ) that given a hypergraph H and an integer k as
input, either
• finds a tree decomposition T of H with λ(T ) = O(k 3 ), or
• correctly concludes that λ-tw(H) > k.
Note the lack of restrictions on the rank.
The overall approximation for µ-tw is a follows: staring from a graph G and a number
k, build a graph L = L(G) as in § 4.2. We have µ-tw(G) = α-tw(L), so the algorithm
in Theorem 4.2 either finds a decomposition T of L such that α(T ) = O(k 3 ), or declares
α-tw(L) > k. In former case we get a decomposition L−1 (T ) of G such that µ(L−1 (T )) =
O(k 3 ), in the latter we deduce that µ-tw(G) > k.

4.1

Reducing α-tw to µ-tw

Given a graph G let M = M (G) be obtained from G by adding a new vertex v ′ and an edge
vv ′ for each v ∈ V (G). The key observation here is that given a set S ⊆ V (G) ⊆ V (M ), we
have αG (S) = µM (S).
Lemma 4.3. We have α-tw(G) = µ-tw(M ).
Proof. If µ-tw(M ) = 0, then M contains no vertices, but in this case α-tw(G) = µ-tw(M ) =
0. Suppose T = (T, {Bt }) is a tree decomposition of G of α-width at least 1. Extend T
by adding new nodes with bags vv ′ for each vertex v and attached to an arbitrary node
containing v, or an arbitrary node if no such node exists. It is easy to see that M(T ) is a
tree decomposition of M . The µ-width of each new bag is 1, hence a bag of maximum width
can be found among the nodes of T . As noted before, the α-width of a node of T equals
its µ-width in M , hence µ(M(T )) = α(T ), and therefore, since T was arbitrary, we have
α-tw(G) ≥ µ-tw(M ).
Conversely, let Tb be a tree decomposition of M . For each vertex v of G delete v ′ from each
bag of Tb and add a new node with bag vv ′ attached to an arbitrary node of Tb containing v,
or an arbitrary node if no such node exists. We see that the modified tree decomposition is of

13

the form M(T ) for a tree decomposition T of G. It is easy to see that µ(M(T )) ≤ µ(Tb ), and
in the previous paragraph we saw that α(T ) = µ(M(T )), hence µ-tw(M ) ≥ α-tw(G).
Combining µ-tw(G) ≤ α-tw(G) with the lemma above we get
µ-tw(G) ≤ α-tw(G) = µ-tw(M (G)) ≤ α-tw(M (G)).
For completeness, we note
µ(G) ≤ α(G) = µ(M (G)) ≤ α(M (G)).

4.2

Reducing µ-tw to α-tw

Recall that the line graph of G, denoted L(G), has the edges of G as vertices, and two vertices
of L(G) are adjacent whenever the corresponding edges of G intersect.
Let Lk (G) be the graph with vertices E(G) and edges




E(G)
ef ∈
: 1 ≤ dL(G) (e, f ) ≤ k .
2
Here dG (u, v) is used to denote the distance between u and v in G, that is the length of
the shortest u–v path in G measured in number of edges. If there is no u–v path, we set
dG (u, v) = ∞. Note that L(G) = L1 (G). We focus on L = L2 (G). Two vertices, e and f , of
L are adjacent if G[e ∪f ] is connected, or equivalently G[e ∪f ] 6∼
= 2K2 . Let L : 2V (G) → 2V (L)
map sets S ⊆ V (G) to the edges of G incident with S. We see that µG (S) = αL (L(S)).
Theorem 4.4. We have µ-tw(G) = α-tw(L).
Proof. Suppose T = (T, Bt ) is a tree decomposition of G. Consider L(T ) = (T, {L(Bt )}t∈V (T ) ).
If ef is an edge of L, then either e and f share a vertex, or there is an edge g intersecting
both. Let h be e in the prior case and g in the latter. The edge h must be contained in
some bag Bt0 , and note that L(Bt0 ) contains ef . Denote by Te the nodes of L(T ) with bags
containing e = uv ∈ V (L). Observe that Te = Tv ∪ Tu ; Tv and Tu are trees that touch, hence
Te is connected. We conclude that L(T ) is a tree decomposition of L. For each bag Bt we
have µG (Bt ) = αL (L(Bt )), so µ(T ) = α(L(T )).
Now suppose (T, Bt ) is a tree decomposition of L. Let St be the vertices of G adjacent
only to edges of Bt . Equivalently, L(St ) ⊆ Bt and St is maximal with the property. Let
e = uv be an edge of G. The edges of G adjacent to u or v form a clique in L, hence there
must be a bag Bt0 containing L({u, v}) (by Helly property for trees), and we conclude that
uv is contained in St0 . Suppose a vertex u of G is contained in two bags Sr and Ss . The bags
Br and Bs contain all edges of G incident with u, Eu , hence Eu is contained in all bags Bt
on the unique r-s path in T , and therefore u is contained in the bags St along the same path.
We conclude that (T, St ) is a tree decomposition of G with µ-width at most α(T, Bt ).
Similarly as before, we have that µ-tw(G) ≤ α-tw(G), and combining this with the
theorem above we get
α-tw(G) ≥ µ-tw(G) = α-tw(L2 (G)) ≥ µ-tw(L2 (G)).
For completeness, we note
α(G) ≥ µ(G) = α(L2 (G)) ≥ µ(L2 (G)).

14

4.3

Approximating well-behaved width measures

The overall strategy is similar to other treewidth approximation algorithms, in particular
to the approximation of fractional hypertree width [Mar10]. Suppose λH is a well-behaved
measure throughout.
Theorem 4.5. There exists an ||H||O(k) -time algorithm that on input hypergraph H; sets
of vertices A, B; and an integer k, either

• finds an (A, B)-separator S with λH (S) ≤ k+1
2 k, or
• correctly concludes that A and B cannot be separated by a set S with λH (S) ≤ k or
that λ-tw(H) > k.

We need few preliminary lemmas first. Given a hypergraph H and a decomposition
(T, Bt ) of H, denote the subtree of T induced by the nodes containing v ∈ V (H) by Tv . A
set S is an (A, B)-separator in a hypergraph H if it is an (A, B)-separator in H, that is there
are no edges between A \ S and B \ S and A ∩ B ⊆ S.
Lemma 4.6. For every hypergraph H and set S we have
αH (S) ≤ λH (S).
Proof. Let I ⊆ S be an independent set of H. We have λH ({i}) ≥ 1 for each i ∈ I by
Property 1. of λH . There are no edges
P in H between any pair of vertices i, j ∈ I, hence by
Property 2. of λH we get λH (I) = i∈I λH ({i}) ≥ |I|. By Property 3. of λH we see that
λH (I) ≤ λH (S). Now suppose I ⊆ S is maximum-sized. We get
αH (S) = |I| ≤ λH (I) ≤ λH (S).
Lemma 4.7. Suppose H is a hypergraph with λ-tw(H) ≤ k. Let H0 , H1 , . . . , Hℓ be a sequence
with H0 := H and Hi+1 be obtained from Hi by adding an arbitrary edge uv such that
λH0 (NHi (u) ∩ NHi (v)) > k.
Then every tree-decomposition of H of λ-width at most k is a tree-decomposition of Hℓ .
Furthermore, if S is an (A, B)-separator of H with λH (S) ≤ k, then S is an (A, B)-separator
of each Hi .
Proof. The proof is by induction on ℓ. The claim is trivial for ℓ = 0. Suppose ℓ > 0 and that
the lemma holds for smaller values. Let T = (T, Bt ) be an arbitrary tree decomposition of H
such that λH0 (T ) ≤ k. By the induction hypothesis, T is a decomposition of Hℓ−1 as well.
If T is not a decomposition of Hℓ , then the edge uv added on the ℓ-th step is not covered
in T , hence Tu and Tv are disjoint. Let Z = NHℓ−1 (u) ∩ NHℓ−1 (v) and let x be an arbitrary
vertex of Z. We see that Tx intersects both Tu and Tv . It follows that x is contained in
every bag along the unique shortest Tu –Tv path in T , Puv . Note that Puv is non-empty; it
contains at least two nodes of T . But x was arbitrary, so the entire Z is contained in every
bag Bt , where t ∈ Puv . This is a contradiction, since λH0 (Z) > k and λH0 (T ) ≤ k.
For the second part, suppose S is not an (A, B)-separator of Hi , and let i be minimal
with this property. Clearly i > 0. Suppose the edge uv is added on the i-th step. Since S is
not a separator of Hi , w.l.o.g. we have u ∈ A \ S and v ∈ B \ S. But then every vertex of
Z = NHi−1 (u) ∩ NHi−1 (v) is contained in S in order to prevent an u–v path of length 2 in
Hi−1 , hence Z ⊆ S and k < λH (Z) ≤ λH (S). We arrive at a contradiction, since
λH (S) ≤ k < λH (Z) ≤ λH (S).
Definition 4.8. Let H be a hypergraph and let H be obtained from H by adding edges uv
such that λH (NHi (u) ∩ NHi (v)) > k as in the previous lemma until no longer possible and
in any order, say Lex-first.

15

Note that H can be built from H in ||H||O(k) time. Indeed, at most O(n2 ) new edges
are added, each step inspects at most O(n2 ) non-adjacent pairs, and for each pair (u, v) it
can be checked if λH (NHi (u) ∩ NHi (v)) > k in ||H||O(k) time, hence the total running time
is ||H||O(k) .
Lemma 4.9. If H is a hypergraph with λ-tw(H) ≤ k, then for every clique C of H we have
λH (C) ≤ k. Furthermore, every (A, B)-separator S of H with λH (S) ≤ k is an (A, B)separator in H.
Proof. Suppose C is a clique in H and let T be a minimum λ-width tree decomposition of
H. Then T is a decomposition of H by Lemma 4.7, and since C is a clique, there must be
a bag B of T containing C by the Helly property for trees. We conclude that
λH (C) ≤ λH (B) ≤ λH (T ) = λ-tw(H) ≤ k.
The second part of the statement follows directly from Lemma 4.7.
Lemma 4.10. [Whi81, Tar85, Mar10] Given a graph G it is possible to construct in polynomial time a set K of at most |V (G)| subsets of V (G) such that
• each clique C of G is contained in a set K ∈ K, and
• K \ C is contained in a connected component of G \ C for each set K ∈ K and every
clique C of G.
Proof of Theorem 4.5. Suppose there is an (A, B)-separator S with λH (S) ≤ k and that
λ-tw(H) ≤ k. Let I be a maximum-sized independent subset of S with respect to H. Note
that |I| = αH (S) ≤ αH (S) ≤ λH (S) ≤ k, hence |I| ≤ k. Let
[

X=

u,v∈I;u6=v




NH (u) ∩ NH (v)

Nv = NH (v) \ X ∪ {v}
[
Y =
Nv .

for v ∈ I, and

v∈I

It follows that S ⊆ X ∪ Y since I is maximal, and that Nv ∩ S is a clique of H since I is
maximum-sized. For v ∈ I, let Kv be the sets of H[Nv ] guaranteed by Lemma 4.10, and pick
a Kv ∈ Kv to contain Nv ∩ S for each v ∈ I. Since Kv \ (Nv ∩ S) = Kv \ S is contained in
a component of H[Nv ] \ S, it follows that Kv \ S is contained in a component of H \ S. By
Lemma 4.9 we have that S is an (A, B)-separator of H, so every vertex of Kv \ S is either
reachable from A in H \ S, or none are. Let J1 ⊆ I be the vertices corresponding to the
prior case, and
S J2 = I \ J1 – the latter. In case Kv \ S is empty, put v in J1 or J2 arbitrarily.
Let Z = X (∪v∈I Kv ). Note that S ⊆ Z. For v ∈ J2 , we call a vertex u ∈ Kv bad if there
is a path PAu from A to u in H such that PAu ∩ Z = {u}, and for u ∈ J1 we call a vertex
u ∈ Kv bad if there is a path PBu from B to u in H such that PBu ∩ Z = {u}. Observe
that by the definition of J1 and J2 , every bad vertex is contained in S. If x ∈ J1 , y ∈ J2 ,
u ∈ Kx and v ∈ Ky , we call the pair {u, v} bad if there is a path Puv from u to v in H, such
that Puv ∩ Z = {u, v}. If {u, v} is a bad pair, then S must contain at least one of the two
vertices, as otherwise u and v are in the same connected component of H \ S, contradicting
the choices for J1 and J2 . To summarise:
• S ⊆ Z,
• S ∩ Kv is a clique in H for each v ∈ I,
• S contains all bad vertices, and
• S intersects all bad pairs.

16

′
Let S ′ be another set with these
 properties. We claim that S ∪ Xkis an (A, B)-separator
k+1
′
in H with λH (S ∪ X) ≤ 2 k. Since X is a union of at most 2 coneighbourhoods of

non-adjacent vertices in H, we have λH (X) ≤ k2 k by the definition of H and Property 2.
P
of λH . Furthermore, λH (S ′ \ X) ≤ v∈I λH (S ′ ∩ Kv ) ≤ k 2 , because S ′ ∩ Kv is a clique in
H, and hence λH (S ′ ∩ Kv ) ≤ k by Lemma 4.9. By putting everything together we conclude


that λH (S ′ ∪ X) ≤ k 2 + k2 k = k+1
2 k.
Now suppose S ′ ∪ X is not an (A, B)-separator in H, and that Pa,b is an a–b path in
H, disjoint from S ′ ∪ X, where a ∈ A and b ∈ B. Clearly, Pa,b is disjoint from X, so
Pa,b ∩ Z = Pa,b ∩ (Z \ X). Let p1 , . . . pm be the vertices of Pa,b ∩ Z, ordered as the path
is traversed from a to b. Since S ⊆ Z is an (A, B)-separator in H, Pa,b ∩ Z ⊇ Pa,b ∩ S is
non-empty. We claim that if p1 ∈ Kv and pm ∈ Ku , then v ∈ J1 and u ∈ J2 . Indeed, if
v ∈ J2 , then stripping Pa,b from a to p1 yields a path P such that P ∩ Z = {p1 }, hence p1
is bad and it must be included in S ′ , a contradiction. Similarly, if u ∈ J1 , then by denoting
the subpath of Pa,b from pm to b by P , we see that P ∩ Z = {pm }, hence pm is bad, a
contradiction. Therefore, there must be a pair {pj , pj+1 } of two consecutive vertices pj , pj+1
of Pa,b ∩ Z, such that pj ∈ Ku with u ∈ J1 and pj+1 ∈ Kv with v ∈ J2 . But then for the
pj –pj+1 subpath, P , of Pa,b , we have P ∩ Z = {pj , pj+1 }, and hence the pair {pj , pj+1 } is
bad, and therefore it cannot be disjoint from S ′ , a contradiction.
Consider a 2-CNF formula ψ

• with variables xv for each vertex v ∈ Z \ X,
• clauses ¬xv ∨ ¬xu for each pair of non-adjacent in H vertices v, u contained in the same
set Kw ,
• with clauses xv ∨ xu for each bad pair {v, u}, and
• set all variables xv corresponding to bad vertices v to true.
Observe that ψ has a satisfying assignment – setting the variables corresponding to vertices
of S \ X to true and the rest to false yields one. Conversely, if S ′ is the set of variables set
to true in a satisfying assignment, then by the discussion above we have that S ′ ∪ X is an
(A, B)-separator in H, and hence also of H, and λH (S ′ ∪ X) ≤ k+1
2 k.
The algorithm to find an (A, B)-separator of bounded λ-width is as follows:
1. Construct H,
2. guess I,
3. build X and Nv for each v ∈ I,
4. build Kv , guess Kv ∈ Kv for each v ∈ I, and build Z,
5. guess a partition (J1 , J2 ) of I (J1 or J2 may be empty),
6. find which vertices are bad, which pairs are bad, and build ψ,
7. if ψ does not have a satisfying assignment, reject the branch; otherwise find a set S ′
corresponding to a satisfying assignment,
8. if for any v ∈ I we have λH (S ′ ∩ Kv ) > k, declare λ-tw(H) > k and terminate; if S ′ ∪ X
is not an (A, B)-separator in H, reject the branch; otherwise return S ′ ∪ X.
As noted before, building H takes ||H||O(k) time. Next, since |I| ≤ k, we may try all
O(nk ) independent sets of size at most k one by one, and thus add a factor of O(nk ) to
the total running time. Constructing each Kv is cheap, but guessing each Kv ∈ Kv adds
one more O(nk ) factor. There are at most 2k choices for (J1 , J2 ), so we get an additional
factor of O(2k ). Step 6. can be done in nO(1) time. Since finding a satisfying assignment or
correctly concluding that a 2-CNF formula is unsatisfiable can be done in linear time with
respect its length [APT79], Step 7. takes O(n2 ) time. The last step takes ||H||O(k) time.
The total running time is ||H||O(k) .

17

Lemma 4.11. Suppose H is a hypergraph with λ-tw(H) ≤ k and W ⊆ V (H). There exists
a set S ⊆ V (H) with λH (S) ≤ k such that for every connected component Ci of H \ S we
have λH (W ∩ Ci ) ≤ λH (W )/2.
Proof. Let (T, Bt ) be a tree decomposition of H of λ-width at most k. If t1 t2 is an edge
of T , T − t1 t2 has two connected components, T1 and T2 respectively, and let us denote
∪{Bt : t ∈ V (Ti )} by Vi . We have that Z := Bt1 ∩ Bt2 = V1 ∩ V2 is a (V1 , V2 )-separator. If
λH (W ∩ (Vi \ Z)) ≤ λH (W )/2 for i ∈ {1, 2}, then we may choose Z as S and we are done.
Otherwise, orient the edge t1 t2 towards ti , where λH (W ∩ (Vi \ Z)) > λH (W )/2.
Suppose S cannot be chosen as Bt1 ∩ Bt2 , and all edges are oriented. Let t be a node of
T with outdegree zero. Let t1 , . . . , tm be the neighbours of t in T , so that each edge ti t is
oriented from ti to t, and let T1 , . . . , Tm be the corresponding components of T \ t. Define Vi
as before. Every connected component of H \ Bt is contained in some set Vi \ Bt , but from
the orientation of ti t we get that
λH (W ∩ (Vi \ Bt )) ≤ λH (W ∩ (Vi \ (Bt ∩ Bti ))) < λH (W )/2,
so we may choose Bt as S.
Theorem 4.12. There is an ||H||O(r+k) -time algorithm that given a hypergraph H and a
set W ⊆ V (H) with λH (W ) ≤ r as input either

• finds a partition (A, B) of W and an (A, B)-separator S of H with λH (S) ≤ k+1
2 k
such that λH (A \ S) ≤ 23 r + k and λH (B \ S) ≤ 32 r + k, or
• correctly concludes that λ-tw(H) > k.
Proof. Suppose that λ-tw(H) ≤ k, let S be the set guaranteed by Lemma 4.11, and let
C1 , . . . Ct be the connected components of H \ S, such that λH (W ∩ Ci ) ≤ r/2, and further
suppose that λH (Ci ∩ W ) ≤ λH (Ci+1 ∩ W ) for each i < t. If V (H) = S there is nothing to
do, so suppose t ≥ 1. We seek to find a partition (Â, B̂) of W \ S such that S is an (Â, B̂)separator and λH (Â), λH (B̂) ≤ 32 r. Let Rj = ∪ji=1 Ci ∩W and suppose ℓ is the last index such
that λH (Rℓ ) ≤ r/2. If ℓ = t, set Â = Rℓ and B̂ = ∅. If ℓ + 1 = t, set Â = Rℓ and B̂ = Ct ∩W .
Otherwise let Q = ∪ti=ℓ+2 Ci ∩ W and note that λH (Q) ≥ λH (Cℓ+1 ∩ W ) from the ordering.
We claim that at least one pair of {(Rℓ ∪ (Cℓ+1 ∩ W ), Q), (Rℓ , (Cℓ+1 ∩ W ) ∪ Q)} is a possible
choice for (Â, B̂). Indeed, if λH (Rℓ ∪ (Cℓ+1 ∩ W )) > 32 r, then 13 r > λH (Q) ≥ λH (Cℓ+1 ∩ W ),
hence λH (Q ∪ (Cℓ+1 ∩ W )) < 32 r.
Let (A, B) be an arbitrary partition of W such that Â ⊆ A and B̂ ⊆ B. The desired separator in the first condition of the statement can be found with the algorithm in Theorem 4.5
with arguments A and B since λH (A) ≤ 32 r + k and λH (B) ≤ 32 r + k. It remains to show that
a partition (A, B) can be found efficiently. Let I be a maximal independent subset of Â in H,
and let Γ(I) be I ∪ {v ∈ V (H) : u ∈ I, uv ∈ E(H)}. We see that Â ⊆ Γ(I) ∩ W ⊆ Â ∪ S, and
B̂ ⊆ W \ Γ(I) ⊆ B̂ ∪ S, so (Γ(I) ∩ W, W \ Γ(I)) is a possible choice for (A, B). Furthermore,
|I| ≤ λH (Â) ≤ 32 r, so I can be found by trying all stable sets of size at most 32 r in time
2
O(n 3 r ). The final algorithm is:
1. Guess I, and independent set of H with |I| ≤ 32 r,
2. construct A = Γ(I) ∩ W and B = W \ Γ(I),
3. reject the branch if λH (A) > 32 r + k or λH (B) > 23 r + k,
4. run the algorithm in Theorem 4.5 with arguments H, A and B.
The total running time is ||H||O(r+k) .
3

Theorem 4.13. There exists a ||H||O(k ) -time algorithm that given a hypergraph H, an
integer k and a set W ⊆ V (H) with λH (W ) ≤ 23 (k 3 + k 2 ) + 3k + 3, either

18

• finds a tree decomposition, T = (T, Bt ), of H, such that λ(T ) ≤ 2k 3 + 2k 2 + 3k + 3 and
W ⊆ Bt for some t ∈ V (T ), or
• correctly concludes that λ-tw(H) > k.
Proof. Let K = 32 (k 3 + k 2 ) + 3k + 3 and s = 21 (k 3 + k 2 ). The algorithm starts by creating
a set W ∗ such that W ⊆ W ∗ and λH (W ∗ ) = min{K, λH (V (H))}. Let S and (A1 , A2 ) be
the separator and the partition of W ∗ from Theorem 4.12; let V1 be the vertices of H \ S
contained in connected components with a non-empty intersection with A1 and let V2 be
V (H) \ (V1 ∪ S). For i ∈ {1, 2}, the algorithm checks if Vi 6⊆ Ai , in which case it makes a
recursive call with arguments Hi = H[Vi ∪ S] and Wi = Ai ∪ S to create a tree decomposition
(Ti , Bt,i ) or conclude that λ-tw(H) > k if λ-tw(Hi ) > k. In case Vi ⊆ Ai , let Ti be the empty
tree. After T1 and T2 have been created, the corresponding node containing Wi in each tree
is joined to a new node with bag W ∗ ∪ S. If either T1 or T2 is empty, ignore it.
If λ-tw(H) ≤ k, then λ-tw(Hi ) ≤ k and
λ(Wi ) ≤ λ(Ai \ S) + λ(S) ≤

2
K + k + s = K − 1,
3

so we can prove by induction that the algorithm creates tree decompositions (T1 , Bt,1 ) of
H1 and (T2 , Bt,2 ) of H2 of width at most K + s. If λ-tw(H) > k, the algorithm will either
create a decomposition of width at most K + s, or find an induced subhypergraph H ′ with
λ-tw(H ′ ) > k, implying λ-tw(H) > k.
The total number of steps can be bounded by the number of recursive calls times the
3
maximum number of steps for each call. The number of steps in each call is clearly ||H||O(k ) .
We claim that the number of calls is bounded by |V (H) \ W ∗ | + 1. The proof is by induction
on |V (H) \ W ∗ |. If |V (H) \ W ∗ | = 0, then λH (V (H)) ≤ K, hence the algorithm creates one
bag and does not make recursive calls.
Now suppose V (H) 6≡ W ∗ . We claim that the number of recursive calls to create Ti is
bounded by |Vi \ W ∗ |. Indeed, if |Vi \ W ∗ | = |Vi \ Ai | = 0, then Ti is empty, and there
are no recursive calls. If |Vi \ W ∗ | > 0, then by the induction hypothesis, there are at most
|V (Hi ) \ Wi∗ | + 1 calls. Since λ(Wi ) ≤ K − 1, either Wi∗ ≡ V (Hi ) or λ(Wi∗ ) = K, and hence
Wi∗ contains a vertex of Vi \ W ∗ , so in either case |V (Hi ) \ Wi∗ | + 1 ≤ |Vi \ W ∗ |. Therefore
the total number of calls is bounded by |V1 \ W ∗ | + |V2 \ W ∗ | + 1 ≤ |V \ W ∗ | + 1.
Overall, the total number of recursive calls, and hence the number of bags crated, is
3
bounded by |V (H)|, and therefore the total running time is ||H||O(k ) .
Theorem 4.2 is the special case of Theorem 4.13 when W = ∅.

5

Open problems and further work

It is not clear whether the restriction on the rank is necessary. We formulate the following
conjectures:
Conjecture 5.1. There exists a function f such that for every clutter H with m edges we
have
|b(H)| ≤ mf (µ(H)) .
Conjecture 5.2. There exists a function f such that for every clutter H with m edges and
any subset S of its vertices we have
|trS (b(H))| ≤ mf (µH (S)) .
It is also interesting to see if the approximation of µ-tw in § 4 can be extended to clutters
of any rank, and if there are efficient reductions of α-tw to µ-tw for clutters and vice-versa.

19

Another question is to find more examples of problems with solutions that can be read
from the blocker. Indeed, b(H) contains a lot of important structural information that is
difficult to access otherwise. Finding an explicit family of problems of this type can lead to
further developments of µ-tw.

References
[ABBM11] Noga Alon, József Balogh, Béla Bollobás, and Robert Morris. The structure of
almost all graphs in a hereditary property. Journal of Combinatorial Theory,
Series B, 101(2):85–110, 2011.
[AGG07]

Isolde Adler, Georg Gottlob, and Martin Grohe. Hypertree width and related
hypergraph invariants. European Journal of Combinatorics, 28(8):2167 – 2181,
2007. EuroComb 05 - Combinatorics, Graph Theory and ApplicationsEuroComb
05 - Combinatorics, Graph Theory and Applications.

[Ale93]

VE Alekseev. On the entropy values of hereditary classes of graphs. Discrete
Math. Appl, 3:191–199, 1993.

[Ale07]

Vladimir Evgenevich Alekseev. An upper bound for the number of maximal independent sets in a graph. Discrete Mathematics and Applications dma, 17(4):355–
359, 2007.

[APT79]

Bengt Aspvall, Michael F. Plass, and Robert Endre Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process.
Lett., 8(3):121–123, 1979.

[BB72]

Umberto Bertele and Francesco Brioschi. Nonserial dynamic programming. Academic Press, 1972.

[BBS09]

József Balogh, Béla Bollobás, and Miklós Simonovits. The typical structure of
graphs without given excluded subgraphs. Random Structures & Algorithms,
34(3):305–318, 2009.

[Bod96]

Hans L Bodlaender. A linear-time algorithm for finding tree-decompositions of
small treewidth. SIAM Journal on computing, 25(6):1305–1317, 1996.

[BPT92]

Richard B. Borie, R. Gary Parker, and Craig A. Tovey. Automatic generation
of linear-time algorithms from predicate calculus descriptions of problems on
recursively constructed graph families. Algorithmica, 7(1):555–581, 1992.

[BT97]

Béla Bollobás and Andrew Thomason. Hereditary and monotone properties of
graphs. pages 70–78, 1997.

[CMR00]

B. Courcelle, J. A. Makowsky, and U. Rotics. Linear time solvable optimization
problems on graphs of bounded clique-width. Theory of Computing Systems,
33(2):125–150, 2000.

[CO00]

Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of
graphs. Discrete Applied Mathematics, 101(1):77–114, 2000.

[Cou90]

Bruno Courcelle. The monadic second-order logic of graphs. i. recognizable sets
of finite graphs. Information and Computation, 85(1):12 – 75, 1990.

[CR05]

Derek G Corneil and Udi Rotics. On the relationship between clique-width and
treewidth. SIAM Journal on Computing, 34(4):825–847, 2005.

[Far89]

Martin Farber. On diameters and radii of bridged graphs. Discrete Mathematics,
73(3):249–260, 1989.

[FHT93]

Martin Farber, Mihály Hujter, and Zsolt Tuza. An upper bound on the number
of cliques in a graph. Networks, 23(3):207–210, 1993.

20

[FRRS06] Michael R Fellows, Frances A Rosamond, Udi Rotics, and Stefan Szeider. Cliquewidth minimization is np-hard. pages 354–362, 2006.
[GLS99]

Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree decompositions
and tractable queries. pages 21–32, 1999.

[GM06]

Martin Grohe and Dániel Marx. Constraint solving via fractional edge covers.
In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete
algorithm, pages 289–298. Society for Industrial and Applied Mathematics, 2006.

[GM14]

Martin Grohe and Dániel Marx. Constraint solving via fractional edge covers.
ACM Trans. Algorithms, 11(1):4:1–4:20, August 2014.

[GW00]

Frank Gurski and Egon Wanke. The tree-width of clique-width bounded graphs
without Kn,n . pages 196–205, 2000.

[Hal76]

Rudolf Halin. S-functions for graphs. Journal of geometry, 8(1-2):171–186, 1976.

[HO08]

Petr Hlinenỳ and Sang-il Oum. Finding branch-decompositions and rankdecompositions. SIAM Journal on Computing, 38(3):1012–1032, 2008.

[Mar10]

Dániel Marx. Approximating fractional hypertree width. ACM Trans. Algorithms, 6(2):29:1–29:17, April 2010.

[OS06]

Sang-il Oum and Paul Seymour. Approximating clique-width and branch-width.
Journal of Combinatorial Theory, Series B, 96(4):514–528, 2006.

[RS84]

Neil Robertson and P.D Seymour. Graph minors. iii. planar tree-width. Journal
of Combinatorial Theory, Series B, 36(1):49 – 64, 1984.

[Tar85]

Robert E. Tarjan. Decomposition by clique separators. Discrete Mathematics,
55(2):221 – 232, 1985.

[Whi81]

Sue Whitesides. An algorithm for finding clique cut-sets. Inf. Process. Lett.,
12:31–32, 1981.

[Yol16]

Nikola Yolov. Blocker size via matching minors. Submitted to Discrete Mathematics, arXiv preprint arXiv:1606.06263, 2016.

21

