For my PhD research, I had to investigate various notions of (hyper)graph tractability,
such as treewidth, cliquewidth, pathwidth, etc. Here is a very terse summary of
what I have found about them. It is mostly my personal summary of reading
this survey and some other
papers, but maybe it may interest others.
To give the broad context: computer scientists are interested in solving
problems on
graphs, e.g., given a
graph, does it have a
specific property (for instance,
can it be
drawn without edge crossings,
can it be
colored with 3 colors, etc.).
Some of these problems are known to be
intractable in the sense of
complexity theory,
which means that there is probably no fast algorithm to solve them.
However, many of those hard problems can be solved efficiently in the specific
case of graphs that are
forests, i.e., that do
not have
cycles.
Graph theorists have tried to understand what makes trees tractable, and to
extend the notion of acyclicity ("being a forest") in two broad respects.
First, by identifying broader notions for graphs, which are parameterized:
a parameter k indicates how much the graph deviates from acyclicity, and the
notion should collapse to acyclicity for small k. The hope is then that,
for fixed k (i.e., for graphs that are not-acyclic only by a small margin), we
can still enjoy tractability, for instance in the sense of parameterized
complexity.
Second, theorists have tried to extend acyclicity
from graphs to the more expressive formalism of
hypergraphs, i.e., graphs where
edges can connect an arbitrary number of vertices.
In all this post except where explicitly stated
otherwise, we consider undirected graphs, i.e.,
a pair (V,E) of a set of vertices and a set of edges which are pairs of
vertices.
Roadmap:
- Section 1 presents treewidth,
branchwidth (essentially equivalent), and pathwidth (more restrictive, i.e., a
graph's pathwidth is more than its treewidth), and
treedepth, which is more restrictive than pathwidth in the same sense.
- Section 2 presents rankwidth and cliquewidth
(equivalent, and less restrictive than the previous ones).
- Section 3 discusses preservation under subgraphs,
minors, and other operations.
- Section 4 discusses extended definitions for
hypergraphs.
- Section 5 discusses the complexity of
computing these parameters.
- Section 6 discusses their applicability for the
decidability of logical theories, the tractability of model checking and
other such problems for expressive languages.
- Section 7 studies their use for less expressive
languages: the problems of CSP, query evaluation and homomorphisms.
- Section 8 is an appendix with a remark about
partial orders.
All links to scientific works are
open-access, i.e., available
without a subscription. I give them as direct links, but I also give the
DOI of each link at
the end.
Related work: one interesting related resource is the Information
System on Graph Classes and their Inclusions.
Warning:
Please be aware
that this summary are my personal notes: it may contain errors and should not be
taken at face value. Please let me know if you find any bugs.
Acknowledgements: Thanks to Pierre
Senellart,
Mikaël Monet and Robin Morisset for proofreading and comments.
Treewidth, pathwidth, branchwidth
Treewidth (tw)
Treewidth is the most common measure,
and can be defined in multiple different ways.
The treewidth of a graph G is the smallest k such that it admits a tree
decomposition of width k in one of the following senses:
-
Formally: we can associate a
tree T to G (called
the tree decomposition), with each node of T (called bag) labeled by a
subset of the graph vertices, such that:
- for each edge of G, its endpoints co-occur in some bag of T
- for each vertex of G, the nodes of T where it occurs form a
connected subtree in T
The width of the tree decomposition T is k−1 where k is the maximal
number of vertices in a bag of T.
While tree decompositions are not oriented, it is often convenient to
pick a root and see them as rooted trees.
-
As a decomposition scheme. Trees can be decomposed by picking a
separator formed of two adjacent
vertices, removing the edge between them, and decomposing
recursively each connected component: in each component, you can pick a
separator that includes the vertices of the parent separator which are also in
that component.
As a generalization, graphs of treewidth k can
be decomposed by picking a separator of k+1 vertices, removing edges between
them, and decomposing recursively each connected component,
requiring that each component's separator includes the vertices
of the parent separator which are part of the component.
The tree of the separators chosen in this process is a tree decomposition of
the instance, because the separators have the right size, cover all edges,
and whenever a vertex occurs in a separator it will occur in all descendent
separators until we reach a component where the vertex no longer occurs.
Conversely, when looking at any non-root bag b of a tree decomposition T, considering
the subgraph G1 of the decomposed graph formed of the vertices occurring
in b and its descendants (the subtree Tb of b rooted at T), and
G2 the subgraph of the vertices occurring in the other bags, the common
vertices between G1 and G2 are those shared between b and its
parent (often called an interface), and removing those in G disconnects G1 and G2 (any other
path connecting them could not be legally reflected in the decomposition).
So Tb can be recursively understood as a tree decomposition of G1,
which has been disconnected from the rest of G.
This explanation with pictures
may help you understand what I mean.
-
As a divide and
conquer
scheme.
Many problems on a rooted tree can be solved by a dynamic
programming algorithm
that solves the problem on any subtree given the solution to its child
subtrees; this is usually just thought of as a bottom-up computation. In
graphs of treewidth k, following the above scheme (or a rooted tree
decomposition) gives you a way to solve problems on the graph with a similar
divide-and-conquer dynamic programming scheme.
Again, this is nicely covered by the explanation linked above.
-
As a pursuit-evasion game,
where "cops" use a decomposition of the graph to corner and catch a
"robber". For more details, see
hlineny2007width,
Section 5.7.
Forests have treewidth 1 (so "having treewidth 1" means "being acyclic"),
cycles have treewidth 2,
cliques with k
vertices have treewidth k−1, but
grids illustrate that
graphs may be planar but have a
high treewidth: a k by k grid has treewidth k.
In terms of structural assumptions, it is easily seen that tree decompositions
can be rewritten to ensure that each tree node has degree at most 3, i.e.,
degree at most 2 when we see T as a rooted tree. Further, tree decompositions
can be rewritten to have logarithmic height, at the cost of multiplying the
treewidth by a constant; see bodlaender1988nc.
A variant of tree decompositions are simplicial
decompositions (see diestel1989simplicial),
where we additionally require that for every pair of adjacent
bags in the tree decomposition T, letting X be the vertices that occur in
both bags, then X is a complete subgraph of the graph G.
Pathwidth (pw)
Pathwidth
is a variant of treewidth where the underlying tree in the formal
definition is required to be a path
graph rather than a general tree. It has many
alternative
characterizations,
in particular in terms of overlapping intervals.
I won't be coming back to pathwidth later, but to contrast it with treewidth,
for any graph G:
- tw(G)≤pw(G): immediate as one notion is more restrictive
than the other;
- pw(G)=O(tw(G)log|G|): see
bodlaender1998partial, Corollary 24.
So "having bounded pw" is strictly more restrictive than "having bounded tw".
Branchwidth (bw)
Branchwidth can be defined
as follows. Let G=(V,E) be a graph. Given a partition of its edges E=E1⊔E2, call its weight the number of vertices incident both to an edge
in E1 and an edge in E2. A branch decomposition of width k of G is a
subcubic tree (nodes have degree either 1 or 3)
where each leaf is labeled bijectively by an edge of G, and for each edge of the
tree, considering E1⊔E2 where E1 and E2 are the edges that
annotate each half of the tree, the weight of this partition is at most k.
Branchwidth is less used than treewidth in computer science, but it has the nice
property that a variant of the definition yields
the notion of rankwidth (see later). Further, it generalizes to
hypergraphs (see later), and it generalizes to
matroids (I won't give more details).
hlineny2007width
(Section 3.1.1) gives a description of graphs of bw
≤2.
Further, from
robertson1991graph10,
cited and proved in hlineny2007width,
Theorem 3.1, we have, for any graph G with branchwidth >1: bw(G)≤tw(G)+1≤⌊1.5⋅bw(G)⌋. Hence, "having
bounded tw" and "having bounded bw" are equivalent.
Treedepth
This is an addition to the original post
Treedepth is defined as follows. An
elimination forest F of a graph G=(V,E) is a forest (i.e., a collection of
rooted trees) on V that ensures that for any {x,y}∈E, one of the
nodes for x and y in F is an ancestor of the other in F (or, equivalently,
there is a path from the root of F to a leaf that covers both x and y).
The depth of an
elimination forest F is the height of F in the standard sense (i.e., the maximal height
of a tree of F). The treedepth of G is the minimal depth d such that
G has an elimination forest F of depth d.
I will not describe the notion of treedepth in more detail, but, to connect it with the
previous notions, we know, by Lemma 11 of
bodlaender1995approximating,
that, for any graph G, we have pw(G)≤td(G). However,
path graphs have treedepth which is logarithmic in their size (with the
elimination forest given as the tree of a binary
search), but have
constant pathwidth.
So "having bounded td" is strictly more restrictive than "having bounded pw"
which is strictly more restrictive than "having bounded tw".
Rankwidth and cliquewidth
Rankwidth (rw)
Rankwidth is defined just like branchwidth, except that we consider vertex
partitions V=V1⊔V2, whose weight is the
rank of the
adjacency matrix from V1 to
V2 (taken as a
submatrix of
the full graph's adjacency matrix): and we consider subcubic trees where leaves are
labeled by graph vertices rather than graph edges.
Rankwidth is less than branchwidth: rw(G)≤max(1,bw(G))
as shown in oum2007rank.
Hence, "having bounded bw" implies "having bounded rw".
Graphs with rankwidth 1 are the distance-hereditary
graphs,
as shown in oum2005rank.
Cliquewidth (cw)
A clique decomposition of width k, or k-expression, in an expression over
the following operations, i and j
denoting any colors in
{1,…,k}:
- create the graph with one isolated vertex labeled by i
- change all vertices of color i to color j
- connect all vertices of color i to those of color j (with j≠i, so no
self-loops)
- take the disjoint union of two graphs constructed by such an expression
A graph has cliquewidth k if some coloring of it can be obtained by a clique
decomposition.
Graphs with cliquewidth 1 are those with no edges, and graphs with cliquewidth
2 are the cographs.
The k by k grid has cliquewidth k+1 by
(golumbic2000clique).
Cliquewidth can be connected to the modular
decomposition of graphs.
Further, there are variants such as symmetric cliquewidth, with "bounded cw" equivalent
to "bounded scw", see
hlineny2007width, section
4.1.3.
Cliquewidth is connected to rankwidth
(oum2006approximating):
rw(G)≤cw(G)≤21+rw(G)−1. Hence, "having bounded
cw" and "having bounded rw" are equivalent, though the rank-width bound can be
exponentially larger.
Cliquewidth is connected to treewidth: we have cw(G)≤3⋅2tw(G)−1
by hlineny2007width,
section 4.2.6.
Hence, "having bounded tw" implies "having bounded cw", though the bound may
again be
exponential.
Conversely, tw(G) can be bounded as a function of cw(G) and of
the degree of G
(kaminski2009recent, Proposition 2 a),
so "having bounded cw" and "having bounded tw" are
equivalent on graph families of bounded degree. The dependence on degree
disappears for graph families that exclude any fixed graph as a minor
(Proposition 2 b).
Preservation under graph operations
Subgraphs and induced subgraphs
A subgraph
of a graph G is obtained by keeping a subset of the edges and vertices of G.
Further, it is an induced subgraph if the edges kept are exactly the
restriction of those of G to the kept vertices (i.e., no edge between kept
vertices was removed).
A property is S-closed (resp. I-closed) if, when a graph has it,
every subgraph (resp. induced subgraph) also does.
Minors and topological minors
A minor of a graph can be obtained
from that graph by removing edges and vertices and contracting
edges. Alternatively, it is
witnessed by mapping the vertices v
of the minor G′ to disjoint subsets
s(v) of vertices of the graph G, and mapping each edge (u,v) of G′ to an edge between
s(u) and s(v) in G.
A
topological minor
maps each vertex v of G′ to a
single vertex s(v) of G, and maps edges (u,v) of G′ to vertex-disjoint
paths from s(u) to s(v) in G: equivalently, a
subdivision
of G′ is isomorphic to a subgraph of G.
Clearly if G′ is a topological minor of G then it is a minor of G.
We define M-closed and T-closed for minors and topological minors as we defined
S-closed and I-closed.
In summary, from
makowsky2003tree:
- M-closed implies T-closed, S-closed, I-closed;
- T-closed implies S-closed, I-closed;
- S-closed implies I-closed;
- No other implication holds.
Monotonicity of our definitions
Standard graph acyclicity is M-closed.
Hence, it is natural to wonder whether our other parameters also are.
- "having treewidth ≤k" is M-closed (as can be seen by applying deletions
and merges to the tree decomposition).
- "having pathwidth ≤k" is M-closed (same argument).
- "having branchwidth ≤k" is M-closed
(hlineny2007width, Prop
3.2).
- "having cliquewidth ≤k" is I-closed
courcelle1990upper
but obviously not S-closed (complete graphs have cliquewidth ≤2 but their
subgraphs cover all graphs)
nor T-closed.
- "having rankwidth ≤k" is I-closed but not S-closed for the same
reasons.
Rankwidth is, however, preserved by the graph operation of vertex-minor
(oum2005rank).
Other operations
Cliquewidth and rankwidth behave well under graph complementation: complementing
can at most double the cw, and adds or removes at most 1 to the rw (quoted in
hlineny2007width, section 4.2.1).
By contrast, no such bounds are possible for treewidth and hence rankwidth
(consider the graphs with no edges).
Treewidth, branchwidth, pathwidth, cliquewidth, rankwidth, can be computed on a
graph with multiple connected components as the max of the same measure over each of the
connected components.
Adding or deleting k vertices or k edges can only make rankwidth
and cliquewidth vary by at most k
(hlineny2007width). The same
holds for treewidth (immediate as each vertex addition in a tree
decomposition can only affect the width by at most 1).
For S-closed families, "having bounded cw" and "having bounded tw" are
equivalent
(makowsky2003tree,
Proposition 7, attributed to courcelle1995logical which seems unavailable
online).
Hypergraphs
Hypergraphs generalize graphs by allowing hyperedges that include an arbitrary number
of vertices.
We will sometimes consider instances, whose hyperedges (called facts) are
allowed to have a label (called the predicate or relation, which has a fixed
arity) and where the occurrences of vertices in facts may be labeled as well:
a fact is written A(a1,…,an), where A is the predicate, n is the
arity, and the ai need not be all
different. Hence, an instance in logical terms is a
structure
for some
relational signature.
In this context it is natural to assume that the maximal arity (number of
vertices per hyperedge) is bounded by a constant, though this assumption is not
usually done when working on vanilla hypergraphs.
From hypergraphs to graphs
The following discussion of how to get from a hypergraph to a graph is from
hlineny2007width. The second
and third method can be applied to (non-hyper)graphs rather than hypergraphs, to get a
different graph.
-
The primal graph or Gaifman graph P(H) of a hypergraph H is the graph
on the vertices of H where two vertices are connected iff they co-occur in
a hyperedge. In other words, hyperedges are encoded as cliques.
The primal graph of a (non-hyper)graph is the graph itself.
-
The incidence graph I(H) of a
hypergraph H is the bipartite graph
on the vertices and edges of H where a vertex is connected to an edge if
the vertex occurs in that edge. In other words, hyperedges are encoded as a
vertex connected to all the vertices that it contains.
The incidence graph
of a (non-hyper)graph amounts to
subdividing
each edge once.
-
The line graph L(H) of a hypergraph H is the graph on the hyperedges of
H where two hyperedges are connected iff they share a vertex. In other
words, the vertices are encoded as cliques on the hyperedges. Alternatively,
the line graph is the primal graph of the dual
hypergraph.
This construction
also makes sense (i.e., is not the identity) for (non-hyper)graphs, where it
is also called the line graph.
We will see in a
later section
how bounds on various width notions can be obtained through these
transformations (for graphs and hypergraphs).
Hypergraph acyclicity
Before trying to come up with parameterized notions, there have been attempts to
formalize crisp acyclicity notions for hypergraphs. See
Wikipedia or
fagin1983degrees
for sources to the claims and more details. Each notion in the list is implied
by the next notion (so they are given from the least restrictive to the most
restrictive) and none of the reverse implications hold
(fagin1983degrees,
Theorem 6.1). Further, they all collapse to the usual notion of acyclicity
(i.e., "being a forest") for hypergraphs that are actually (non-hyper)graphs
(i.e., all hyperedges have size 2).
-
α-acyclicity: we can reduce the hypergraph to the empty hypergraph with four
operations: remove an isolated vertex; remove a vertex in a single hyperedge;
remove a hyperedge contained in another; remove empty hyperedges.
Equivalently, a hypergraph is α-acyclic iff it has a join forest, which is
a forest of join trees, which are a
special form of tree decomposition: we require that, for each bag, there
is a hyperedge containing exactly the elements of the bag. There are other
equivalent characterizations of α-acyclicity which I will not define.
We can test in linear time whether an input hypergraph is α-acyclic, and if
so compute a join forest: see
Theorem 5.6 of flum2002query.
Counter-intuitively, α-acyclicity can be gained when adding hyperedges (think
of a hyperedge covering all vertices), and hence also lost when removing
vertices.
-
β-acyclicity: all sub-hypergraphs of the hypergraph (including itself) are
α-acyclic; this is obviously more restrictive than α-acyclicity, in fact
strictly so. It is testable in PTIME: see fagin1983degrees Section 9.3.
-
γ-acyclicity: I won't define it here; see
fagin1983degrees. It is
testable in PTIME: see fagin1983degrees Section 9.4.
-
Berge-acyclicity: the incidence graph of the hypergraph is acyclic in the standard sense;
this is obviously testable in linear time and is strictly more restrictive than
γ-acyclicity.
We now turn to acyclicity definitions with a parameter k.
Following standard usage, we will talk of the treewidth of a hypergraph H
to mean the treewidth of its primal graph P(H).
However, by
hlineny2007width, Section
5.2, there are α-acyclic hypergraphs which have unbounded treewidth, i.e., their
primal graphs have unbounded treewidth;
and ditto for the notions of incidence graphs and of line graphs.
This motivates the search for specific hypergraph definitions of treewidth (and
of the other notions presented before).
Querywidth, hypertreewidth, generalized hypertreewidth
A decomposition of a hypergraph,
for all three notions of width presented here,
is a tree decomposition of its primal
graph: however, the vertices of each bag are additionally covered by a set of
hyperedges, and the width of the decomposition is redefined to mean the maximal number of
hyperedges in a bag (where we do not subtract 1, unlike in the definition of
treewidth). The differences are:
- querywidth: the hyperedges of each bag must exactly cover the vertices
of the bag.
- hypertreewidth: the hyperedges of each bag must cover the vertices of the
bag and they cannot include additional vertices if those occur in strict
descendants of the bag.
- generalized hypertreewidth: the hyperedges must cover the vertices, no
further restriction is imposed.
Thus ghtw(H)≤tw(P(H)) and ghtw(H)≤htw(H)≤qw(H). In fact qw(H)≤1+tw(I(G))
(chekuri2000conjunctive, Lemma 2): a tree
decomposition of the incidence graph is in particular a query decomposition when
restricting the attention to the vertices of the incidence graph that code
hyperedges, and the "+1" is because the definition of treewidth subtracts 1 to
bag sizes.
Further, all three notions are within a factor 3 of each other
(adler2007hypertree,
gottlob2007generalized),
so that "having bounded qw", "having bounded htw", and "having bounded ghtw" are
all equivalent.
A (non-empty) hypergraph H is α-acyclic iff ghtw(H)=htw(H)=qw(H)=1 as mentioned in
gottlob2014treewidth.
All three notions are bounded by ⌊n/2⌋+1 on hypergraphs with
n vertices
(gottlob2005computing,
Theorem 3.5 and subsequent remarks).
From the join tree definition, it is obvious that a hypergraph is α-acyclic iff
it has querywidth equal to 1.
Last, it is obvious by definition that if the arity
is bounded by a constant a,
then we have ⌊tw(P(H))/a⌋≤ghtw(H). Hence,
in this case, "having bounded tw" is equivalent to "having bounded htw" (and
ditto for the other two hypergraph notions).
Fractional hypertreewidth
This is an addition to the original post
The notion of fractional hypertreewidth is defined in
grohe2014constraint (not available online) and in
marx2009approximating.
It is again defined via tree decompositions of the primal graph of the hypergraph,
but this time we annotate them with weighting sets of hyperedges: for each bag b of the tree decomposition,
we have a weighting function wb for bag b that maps each hyperedge e of the hypergraph
to a nonnegative real number wb(e). We require that, for every bag b,
the function wb covers the set S of the vertices contained in b, namely, for each v∈S, the sum
wb(e) over all hyperedges e of the hypergraph that contain v must be at
least 1. The width of these augmented tree decompositions is the maximum,
over all bags b, of the sum wb(e) over all hyperedges; and the fractional
hypertreewidth of a hypergraph is the smallest possible width of such a
decomposition.
Of course, the fractional hypertreewidth is less than the generalized
hypertreewidth, as generalized hypertreewidth is obtained by restricting the
decompositions to use weight functions having values in {0,1}.
Hyperbranchwidth
Hyperbranchwidth
(adler2007hypertree)
is defined like branchwidth, with partitions of hyperedges, except that the
weight of a hyperedge partition is not its number of incident vertices, but the number of
hyperedges required to cover its incident vertices (not necessarily exactly,
i.e., we may cover a superset of them). We have
(adler2007hypertree,
Lemmas 16 and 17):
- hbw(H)≤ghw(H) for any hypergraph H
- ghw(H)≤2hbw(H) for any non-trivial hypergraph H (not all
hyperedges are pairwise disjoint)
Hence "bounded hyperbranchwidth" and "bounded generalized hypertreewidth" are
equivalent.
Apparently hyperbranchwidth is a problematic function because it is not
submodular, unlike the
functions used for branchwidth and rankwidth.
I do not know whether we can define variants of hyperbranchwidth with partition
weight counted as the number of hyperedges required to cover exactly the
vertices, and connect this to querywidth.
Cliquewidth
Cliquewidth is usually defined for hypergraphs as that of the incidence graph,
in which case we have qw(H)≤cw(H), and there are
hypergraphs with bounded querywidth but unbounded cliquewidth. Hence "having
bounded querywidth" (and the other notions) is weaker than "having bounded
cliquewidth".
(gottlob2004hypergraphs)
Connections via transformations
In some cases, bounds on graphs or hypergraphs relate to bounds on the incidence, line,
and primal graph.
The branchwidth of a (non-hyper)graph G is the rankwidth of its incidence graph, up to
removing 1: bw(G)−1≤rw(I(G))≤bw(G)
(oum2007rank).
The treewidth of a (non-hyper)graph can be used to bound the cliquewidth of its
line graph: .25⋅(tw(G)+1)≤cw(L(G))≤2tw(G)+2
(gurski2007line,
Corollary 11 1., and Theorem 5).
The treewidth of a (non-hyper)graph is exactly that of its incidence graph:
tw(G)=tw(I(G))
(kreutzer2009algorithmic, Theorem 3.22).
A similar result for cliquewidth is known assuming bounded vertex degree
(kaminski2009recent,
Proposition 8).
Further, for any hypergraph H, we have tw(H)≤tw(I(H))+1
(gradel2002back),
where we recall that the treewidth of a hypergraph was defined as that of its primal
graph.
I am not aware of results connecting width measures on hypergraph to measures
on the dual hypergraph.
Directed graphs
I file "directed graphs" in the same category as "hypergraphs", because it is
about having a richer incidence relation. Width definitions for directed graphs
are interesting because the usual acyclicity notion for directed graphs is
different from that of undirected graphs (i.e., "being a forest", which we
studied so far). This is an interesting area with lots of recent research that I
will not attempt to summarize here.
See hlineny2007width for a survey.
I will just note that clique decompositions can extend to directed graphs, where the operation that
creates edges is meant to create directed edges
(hlineny2007width, section
4.1.1).
Complexity of recognition
Definitions
Having studied all of these definitions, it is a natural question to ask, given
an (hyper)graph, how can we compute its *-width. I will only deal with the
parameterized width notions; for the crisp acyclicity definitions, I have
already given
the complexity of recognition when defining them in this
section.
For the parameterized notions, we must be careful in the problem
definition. There are two possible tasks:
- Just determine the *-width of the input (hyper)graph
- Determine the *-width and compute a *-decomposition of the input
Further, it is often useful to study a parameterized version of these decision
problems. Hence, we consider two possible kinds of inputs; the first is of
course harder than the second:
- We are only given an input (hyper)graph and the algorithm must solve the task.
- We have fixed k∈N; the algorithm is given a (hyper)graph with
the promise that its *-width is at most k. In other words, if
its width is >k the algorithm may do anything, otherwise it must solve the task.
In the second phrasing, example situations are:
- the problem gets NP-hard whenever the parameter k is given a sufficiently
large value;
- for every k, the problem can be solved in PTIME, i.e., for some function f:N→N, in
O(nf(k)); this is the parameterized complexity class
XP if f is
computable (in our case it always will be);
- the problem can be solved in complexity O(f(k)⋅nc) for a fixed
(computable) function f and a fixed constant c∈N independent of k, in which case we say that the problem is
fixed-parameter tractable
(FPT) (and we may talk of linear-FPT, quadratic-FPT,
etc., to reflect the value c).
Robertson-Seymour
The well-known Robertson-Seymour
theorem shows
that any M-closed property can be characterized by a finite set of forbidden
minors. As
testing whether a fixed graph G′ is a minor of an input graph G can be
performed in quadratic time
(kawarabayashi2012disjoint);
this implies the existence of a quadratic time test for any M-closed property.
We will use this general result later.
Results
When k is fixed and a graph G is given as input:
- For treewidth, branchwidth, pathwidth:
- Determining the value of the treewidth, branchwidth, and pathwidth are
quadratic FPT
because "having treewidth ≤k" and "having branchwidth ≤k" are
M-closed, so we can apply the Robertson-Seymour-based reasoning above.
- For treewidth and pathwidth, there is a linear FPT algorithm to compute the
width and a decomposition
(bodlaender1996linear,
the parameter being exponential in the width). The algorithm is
infeasible in practice due to huge constants. For treewidth, it is preferable in practice to use an
algorithm that computes a decomposition of a graph G of treewidth k in time
O(|G|k+2)
(flum2002query, end
of Section 3), or various heuristics for approximation (see at the end of
the section).
- Branchwidth can be computed, along with an optimal branch decomposition, in FPT linear
time (bodlaender1997constructive)
- For rankwidth, cliquewidth:
- Rankwidth, and an optimal decomposition, can be computed in cubic FPT time
(hlineny2007finding).
- It is PTIME to determine the cliquewidth for k≤3
(corneil2012polynomial, requires a subscription); otherwise this is still
open.
For hypergraph acyclicity measures (α-acyclicity, etc.), refer back to the
paragraph where they are defined.
For hypergraph measures, when k is fixed and a hypergraph H is given as input:
- It is NP-complete to decide whether an input hypergraph H has generalized
hypertreewidth 3
(gottlob2007generalized).
For 2, the complexity was
open
but NP-completeness is shown in the recent preprint
fischl2016general
- It is NP-complete to decide whether an input hypergraph H has querywidth 4
(gottlob2002hypertree).
- For any k, we can determine in PTIME whether an input hypergraph H has
hypertreewidth ≤k, and if so compute a decomposition
(gottlob2002hypertree);
however this is
unlikely to be in FPT
(gottlob2005hypertree).
- We can test in linear time whether it has generalized hypertreewidth 1,
querywidth 1, or hypertreewidth 1, because this is equivalent to it being
α-acyclic (mentioned in gottlob2014treewidth).
- It is NP-complete to test whether an input graph has fractional
hypertreewidth ≤2, as shown in the recent preprint
fischl2016general
When a graph G is given as input, with no bound on the parameter k:
- Treewidth is NP-hard to compute on general graphs; it is computable in PTIME
on chordal graphs
(bodlaender2007combinatorial,
after Lemma 11); on planar graphs,
this is
open.
- Branchwidth is NP-hard on general graphs, but on planar graphs it can be
determined and a decomposition constructed in PTIME
(seymour1994call;
cubic bound shown in gu2005optimal, unavailable without subscriptions).
- Cliquewidth is NP-hard to compute
(fellows2009clique).
- Fractional hypertreewidth can be approximated in PTIME: given a hypergraph
H, we can compute in PTIME a fractional hypertree decomposition of width
O(w3) of H, where w is the real fractional hypertreewidth: see
marx2009approximating.
There are practical implementations
to compute tree decompositions of graphs, trying to compute the optimal treewidth or an approximation
thereof. A fellow student of mine successfully used
libtw.
See Section 4.2 of
bodlaender2007combinatorial
for more details about how treewidth can be approximated (including, e.g., the
use of
metaheuristics).
See also bodlaender2009treewidth.
Logical problems
Logics
Propositional logic
(Boolean connectives) is the logic allowing variables and
Boolean connectives:
negation, conjunction, disjunction. Propositional logic formulae are often given
in conjunctive normal
form (CNF), i.e., a
conjunction of clauses which are disjunctions of literals (variables or negated
variables); or in
disjunctive normal
form (a disjunction of
conjunctions of literals).
(Function-free) first-order logic
(FO)
is the
logic obtained from propositional logic by allowing
existential
and universal
quantifiers.
Monadic second-order logic
(MSO) is the logic obtained from FO by further allowing existential and
universal quantification over sets (unary relations).
Monadic second-order logic with edge quantification
(MSO2) is the logic on graphs that further allows quantification over sets of
edges. Its generalization to hypergraphs (quantifying over relations of
arbitrary arity) is called
guarded second-order logic (GSO). In GSO, quantifications
over relations of arity >1 are semantically restricted to always range over guarded tuples,
i.e., tuples of values that already co-occur in a hyperedge. Likewise,
quantification over sets of edges in MSO2 means quantifications over edges in
the actual structure, not quantification over arbitrary pairs. However, this
should not be confused with
guarded logics, where
first-order quantification is restricted as well: MSO2 and GSO without
second-order quantification is exactly FO, it is not restricted to the guarded
fragment of FO.
It turns out that MSO2 over graphs is equivalent to MSO over the
incidence graph of these graphs, where the incidence graph is assumed to be
labeled in a way that allows the logic to distinguish between vertices and
edges. More generally, GSO over hypergraphs (or labeled hypergraphs, i.e.,
relational signatures) is equivalent to MSO on the incidence instance
(gradel2002back,
Proposition 7.1).
An example of a proposition that can be expressed in MSO2 but not MSO is the
existence of a
Hamiltonian cycle in a graph
(see kreutzer2009algorithmic, Section 3.2).
Problems
The
satisfiability problem for a
logic L and class of (hyper)graphs C asks,
given a formula ϕ∈L, whether it has a model in C.
The satisfiability problem for MSO2 sentences, MSO sentences, and actually FO
sentences is undecidable over
general graphs (even over finite graphs, in fact; see
Trakhtenbrot's theorem
which is the corresponding result for
validity, i.e., the negation of
satisfiability of the negated formula).
For propositional logic, the problem
SAT
of deciding whether a
propositional formula is satisfiable is NP-complete.
The
model-checking problem for a
logic L and class of (hyper)graphs C, asks
for a fixed formula ϕ∈L with no free variables, given an
input (hyper)graph G∈C, whether G
satisfies ϕ in the logical sense.
I will not study the version of model checking where both the formula and
(hyper)graph are given as input, which is of course considerably harder.
The model-checking problem for MSO in general is hard for every level of the
polynomial hierarchy
(ajtai2000closure).
A simple example that shows NP-hardness on graphs is asking whether an input
graph can be colored with 3
colors, which is MSO-expressible.
A variant of the model-checking problem is the counting problem that asks,
for a formula with free variables, given a (hyper)graph, how many assignments of
the free variables satisfy the formula; and the enumeration problem, that
requests that the satisfying assignments be computed (with complexity measured
as a function of the size of the
output, or measured
as the maximum delay between two enumerated outputs).
Monadic second order
For satisfiability, it is known that, for any k, satisfiability for MSO2 over the class of
graphs of treewidth ≤k is decidable
(seese1991structure);
this implies the same for branchwidth (an equivalent claim) and pathwidth (a
weaker claim). Conversely, it is known that for any class of graphs of unbounded
treewidth, satisfiability for MSO2 is undecidable: this relies on a different
result by Robertson and Seymour, the
grid minor theorem, to
extract large grid minors from unbounded treewidth graphs, and using the fact
that the MSO theory of grids is undecidable. For details see
kreutzer2009algorithmic, Section 6.
Further, it is known that, for any k, satisfiability for MSO over the class of
graph of cliquewidth ≤k is decidable. The converse result was conjectured
in
seese1991structure
and a weakening was proven in
courcelle2007vertex:
it shows the converse result but for a logic further allowing to test that a set
variable of MSO is interpreted by a set of even cardinality. Also, it is already
known that a class of graphs has bounded cliquewidth iff it is interpretable in
the class of colored trees (cited as Lemma 4.22 in
kreutzer2009algorithmic).
For model checking, it is known that the problem for MSO2 on bounded treewidth
structures is FPT linear (with the formula and the width bound as parameter),
see
kreutzer2009algorithmic, Section 3.4; this is
what is known as Courcelle's
theorem.
The
model checking problem for MSO on bounded cliquewidth structures is FPT cubic,
the bottleneck being the computation of the rank decomposition:
see kreutzer2009algorithmic, Section 4.3; this
is also due to Courcelle.
The FPT tractability (not linearity) of MSO2 on bounded treewidth reduces to the
same result for MSO and bounded cliquewidth by going through the incidence graph
(see these
slides, slide 8).
The tractability of MSO on bounded cliquewidth does not extend to MSO2. Indeed,
some problems definable in MSO2 but not in MSO are known to be W[1]-hard when
parameterized by clique-width, e.g., Hamiltonian cycle, see
fomin2009clique
and
fomin2010algorithmic.
Further, it is known that there is a MSO2 formula such that model checking on
the class of all unlabeled cliques (which has bounded cliquewidth) is not in
PTIME, assuming P1≠NP1 (those are unary
languages):
see Theorem 6 of
courcelle2000linear.
For model-checking, the constant factor that depends on the fixed formula ϕ is
nonelementary even for
a formula in FO
(frick2004complexity).
The tractability results for model checking on bounded treewidth structures are
usually shown using interpretability results to translate the logic on the
instances to a logic on the (suitably annotated) tree decompositions (see
kreutzer2009algorithmic),
and using a connection from MSO on trees to
tree automata that originated in
thatcher1968generalized (subscription required). See
flum2002query for a
summary.
A connection to automata for bounded rankwidth structures was more recently
investigated in
ganian2010parse.
The necessity of bounded treewidth for the tractability of model-checking under
closure assumptions (i.e., S-closed, M-closed, etc.) was studied in
makowsky2003tree.
The S-closed case was
refined in
kreutzer2011lower (for MSO2), and in
ganian2012lower (for MSO but additionally assuming closure
under vertex labellings).
The problem of counting the number of assignments to a MSO formula is also known
to be linear on bounded treewidth (hyper)graphs
(arnborg1991easy),
and computing the assignments (the enumeration problem) can be
done in time linear in the input and in the output
(flum2002query).
For results on constant-delay enumeration, see, e.g.,
segoufin2012enumerating.
First-order
I am not aware of conditions that try to ensure decidability of FO
satisfiability (in the spirit of those for MSO and MSO2 above), so I focus on model checking.
The model-checking problem for FO is in PTIME, in fact in
AC0, but this does not imply
that it is FPT (where the query is the parameter): the degree of the polynomial
in the (hyper)graph depends in general on the formula.
It is more complicated for FO than for MSO to find criteria that
guarantee that FO model checking is FPT, because of locality properties of FO. In
particular, there are notions of locally tree-decomposable structures
(frick2001deciding), which ensure FPT
linearity of FO model checking in more general situations.
For more about FO, see Section 7 of
kreutzer2009algorithmic, noting that Open
Problem 7.23 has now been solved in the affirmative
(dvorak2013testing).
The problem of enumeration for first-order is also studied in
segoufin2012enumerating.
Propositional logic
The model-checking problem for propositional formulae is obviously always
tractable.
However, it is more interesting, given a propositional formula in normal form,
encoded as an instance, to determine whether it is satisfiable
(SAT), and count the
number of satisfying assignments (#SAT).
The standard way to represent a
conjunctive normal form
formula is as a bipartite graph between clauses and variables with colored edges
indicating whether a variable occurs positively or negatively in a clause
(see ganian2010better, Definition 2.7).
It is then known that SAT and #SAT are FPT if this graph has bounded treewidth
or if it has bounded rankwidth (see
ganian2010better and references therein).
Tractability for #SAT is known for other cases, e.g., when the
standard representation of the formula as a hypergraph is β-acyclic
(brault2014understanding).
Query evaluation and constraint satisfaction problems
Problems
This section studies the constraint satisfaction
problem,
formalized as the problem CSP of deciding, given two relational instances I1 and
I2,
whether there is a homomorphism from I1 to I2, i.e., an application
mapping the elements of I1 to those of I2 such that each fact (hyperedge)
of I1 exists in I2 when mapped by the homomorphism; as well as a
counting variant that asks how many such homomorphisms exist.
The CSP problem is also studied in
database theory,
seen as Boolean
conjunctive query (CQ)
evaluation: a
Boolean CQ is an FO sentence consisting of an existentially quantified
conjunction of atoms. It is clear that a CQ Q is satisfied in an instance I iff there
is a homomorphism from IQ to I where IQ is the canonical instance
associated to Q.
One problem phrasing is when both I1 and I2 are given as input, which I
will call the combined complexity approach. In this case, it is sensible to
restrict I1 and I2 to live in fixed (generally infinite) classes C1 and C2,
and study how the choice of class influences the complexity.
Another problem phrasing, common in database theory, is when one of C1 and
C2 is a singleton class, so we are in one of two settings:
- data complexity: I1 is a fixed structure and I2 is the input
- query complexity: I2 is a fixed structure and I1 is the input
The question then becomes how the complexity of the CSP problem evolves depending on
the fixed structure, and on the class in which the input structures may be
taken; so this is really the combined complexity approach but with one of the
classes being a singleton (so the corresponding structure is effectively fixed
rather than given as input).
Results
Without any restriction, the CSP problem is clearly in NP in combined complexity
(guess the homomorphism and check it) and its counting variant is in #P (count
nondeterministically over all mappings that are checked to be homomorphisms).
The CSP problem is easily seen to be NP-hard in
query complexity for very simple I2, even when C1 is the class of graphs:
fixing I2 to be a triangle,
an input I1 has a homomorphism to I2 iff it is
3-colorable. For any fixed
I1, the data
complexity of the CSP problem when C2 is all structures is in
AC0 from FO model checking, but
it is
W[1]-complete
(papadimitriou1999complexity, Theorem 1)
and hence unlikely to be in FPT.
For arbitrary I1, data complexity becomes FPT when the input instances I2
are restricted to have bounded treewidth or bounded cliquewidth, from the
results on FO.
Combined complexity becomes
LOGCFL-complete (and hence in PTIME) when
C2 is a class of bounded querywidth structures, or structures of
bounded degree of cyclicity (yet another definition),
and they are given with a suitable decomposition
(gottlob2001complexity).
This generalizes an earlier analogous result for α-acyclic queries
(yannakakis1981algorithms, seems unavailable online).
For bounded treewidth or bounded hypertreewidth,
the same result holds but the decomposition can even be computed in LOGCFL, so
it doesn't need to be given.
The PTIME membership still holds when C2 is a class of bounded fractional
hypertreewidth structures (grohe2014constraint, unavailable online).
For hypergraphs of fixed arity, assuming that FPT≠W[1], it is
known that the combined complexity where C2 is all structures is in PTIME iff
C1 has bounded treewidth modulo homomorphic equivalence. This result
generalizes to the problem of counting the number of homomorphisms
(dalmau2004counting).
In cases where C1 satisfies this condition, the CSP problem is FPT with the
parameter being the size of I1. A trichotomy result for the complexity in
such cases is given in chen2013fine, including
for counting.
When restricting C1 and C2 to
graphs (not hypergraphs), an analogous result is known for combined complexity
when C1 is all structures:
tractability holds iff C2 is bipartite
(grohe2007complexity),
otherwise NP-completeness holds. The Feder-Vardi conjecture claims that there is
an analogous
dichotomy even when C1 and C2 can be hypergraphs rather than graphs (i.e., the query complexity
of CSP is never, e.g., in
NPI). Solutions to the problem have been proposed: see
here.
Partial order theory
As bonus material, because I love
partial order (poset) theory:
an unconventional way to look for tractability parameters on graphs is to look at
tractability parameters on posets and look at the (directed) graphs defined by
the transitive reduction
of these posets, namely, their
Hasse diagrams; and look at the
cover graph which is the undirected version of the Hasse diagram.
There has been recent work connecting the tractability measure of
order dimension on posets to
graph measures on the cover graph. Here are results, for any poset P with
cover graph G:
Last, a note about something that confused me: imposing that a poset is
series-parallel
is not the same as imposing that its cover graph is a
series-parallel graph.
The N-shaped poset, which is the standard example of a non-series-parallel
poset, but its cover graph is just a
path graph. Hence series-parallel
posets intrinsically rely on directionality.
List of DOIs
To ensure that the references in this article can still be followed even if some
preprints are removed from the Web, here is the DOI of the citations, in
the order in which they appear in the text.
- hlineny2007width:
10.1093/comjnl/bxm052
- bodlaender1988nc:
10.1007/3-540-50728-0_32
- diestel1989simplicial:
10.1016/0012-365X(89)90084-8
- bodlaender1998partial:
10.1016/S0304-3975(97)00228-4
- robertson1991graph10:
10.1016/0095-8956(91)90061-N
- oum2007rank:
10.1002/jgt.20280
- oum2005rank:
10.1016/j.jctb.2005.03.003
- golumbic2000clique:
10.1142/S0129054100000260
- oum2006approximating:
10.1016/j.jctb.2005.10.006
- kaminski2009recent:
10.1016/j.dam.2008.08.022
- makowsky2003tree:
10.1016/S0304-3975(02)00449-8
- courcelle1990upper:
10.1016/S0166-218X(99)00184-5
- courcelle1995logical: I couldn't locate the article or a DOI. Full reference
from makowsky2003tree: B. Courcelle, J. Engelfriet, A logical
characterization of the sets of hypergraphs defined by hyperedge
replacement grammars, Math. Systems Theory 28 (1995) 515–552.
- fagin1983degrees: 10.1145/2402.322390
- chekuri2000conjunctive:
10.1016/S0304-3975(99)00220-0
- adler2007hypertree:
10.1016/j.ejc.2007.04.013
- gottlob2007generalized:
10.1145/1265530.1265533
- gottlob2014treewidth:
in a book with ISBN 978-1107025196
- gottlob2005computing:
10.1145/1065167.1065187
- grohe2014constraint: not available online, DOI 10.1145/2636918
- marx2009approximating:
Full reference: D. Marx, Approximating fractional hypertree width,
SODA 2009. DOI of proceedings: 10.1137/1.9781611973068
- gottlob2004hypergraphs: 10.1137/S0097539701396807
- gurski2007line:
10.1016/j.disc.2007.01.020
- kreutzer2009algorithmic: arXiv:0902.3616
(not a DOI)
- gradel2002back:
10.1145/507382.507388
- kawarabayashi2012disjoint:
10.1016/j.jctb.2011.07.004
- bodlaender1996linear:
10.1145/167088.167161
- flum2002query:
10.1145/602220.602222
- bodlaender1997constructive:
10.1007/3-540-63165-8_217
- hlineny2007finding:
10.1137/070685920
- corneil2012polynomial: 10.1016/j.dam.2011.03.020
- gottlob2002hypertree:
10.1006/jcss.2001.1809
- fischl2016general: arXiv:1611.01090 (not a
DOI)
- gottlob2005hypertree:
10.1007/11604686_1
- bodlaender2007combinatorial:
10.1093/comjnl/bxm037
- bodlaender2009treewidth:
10.1016/j.ic.2009.03.008
- seymour1994call:
10.1007/BF01215352
- gu2005optimal: 10.1145/1367064.1367070
- fellows2009clique:
10.1137/070687256
- ajtai2000closure:
10.1006/jcss.1999.1691
- seese1991structure:
10.1016/0168-0072(91)90054-P
- courcelle2007vertex:
10.1016/j.jctb.2006.04.003
- fomin2009clique:
No DOI. Full reference: F. V. Fomin, P. A. Golovach, D. Lokshtanov, S.
Saurabh, Clique-width: on the price of generality, 2009. DOI of
proceedings: 10.1137/1.9781611973068.
- fomin2010algorithmic:
10.1137/1.9781611973075.42
- courcelle2000linear:
10.1007/s002249910009
- frick2004complexity:
10.1016/j.apal.2004.01.007
- thatcher1968generalized: 10.1007/BF01691346
- ganian2010parse:
10.1016/j.dam.2009.10.018
- kreutzer2011lower: arXiv:1001.5019 (not a
DOI)
- ganian2012lower: arXiv:1109.5804 (not a
DOI)
- arnborg1991easy:
10.1016/0196-6774(91)90006-K
- segoufin2012enumerating:
10.1145/2448496.2448498
- frick2001deciding: arXiv:cs/0004007 (not
a DOI)
- dvorak2013testing: arXiv:1109.5036 (not a
DOI)
- ganian2010better: arXiv:1006.5621 (not a
DOI)
- brault2014understanding: arXiv:1405.6043
(not a DOI)
- papadimitriou1999complexity:
10.1006/jcss.1999.1626
- gottlob2001complexity:
10.1145/382780.382783
- yannakakis1981algorithms: I couldn't locate the article or a DOI. Full
reference from
gottlob2001complexity: M.
Yannakakis, Algorithms for acyclic database schemes, Proc. VLDB, 1981. In
C. Zaniolo and C. Delobel, eds, pages 82-94.
- dalmau2004counting:
10.1016/j.tcs.2004.08.008
- grohe2007complexity:
10.1145/1206035.1206036
- joret2015dimension: arXiv:1406.3397 (not a
DOI)
- joret2015tree: arXiv:1301.5271 (not a DOI)
- corneil2005relationship: 10.1137/S0097539701385351