18 votes

Are there interesting graph classes where the treewidth is hard (easy) to compute?

Treewidth is NP-hard to compute on co-bipartite graphs, indeed the original NP-hardness proof of treewidth of Arnborg et al. shows this. Additionally, Bodlaender and Thilikos showed that it is NP-hard ...
daniello's user avatar
  • 3,266
17 votes
Accepted

Treewidth of deep Sierpiński Sieve Graph

You can recursively decompose each triangle into a smaller triangle and a trapezoid, and each trapezoid into two smaller triangles. The corresponding tree decomposition (whose bags contain the corners ...
David Eppstein's user avatar
15 votes
Accepted

Classes of graphs with superconstant treewidth

I believe that the universal graphs for trees constructed by Chung and Graham 1983 have treewidth $\Theta(\log n)$. Or for a slightly simpler but similar example consider the transitive closures of ...
David Eppstein's user avatar
15 votes

Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees

L(2,1)-labeling is such a problem. The input is (just) a graph and we want to color it using the minimum number of colors so that neighboring vertices have colors that differ by at least 2 and ...
Michael Lampis's user avatar
14 votes
Accepted

Finding subgraphs with high treewidth and constant degree

See the paper by Julia Chuzhoy and myself on Treewidth sparsifiers. We show that one can obtain a subgraph of degree at most 3 with treewidth $\Omega(k/polylog(k))$ where $k$ is the treewidth of $G$. ...
Chandra Chekuri's user avatar
11 votes
Accepted

Maximum Treewidth of a Graph with $m$ Edges

There are bounded degree (in fact even cubic i.e. 3-regular) expanders on $m$ vertices with treewidth at least $\epsilon \cdot m$, for some constant $\epsilon > 0$. See Section 2 in: Martin Grohe, ...
PsySp's user avatar
  • 840
10 votes
Accepted

Is bounded-width SAT decidable in logspace?

Indeed, using the resultss in Elberfeld-Jakoby-Tantau-2010 one can show that SAT can be decided in logspace on formulas whose incidence graph has bounded treewidth. Here is a sketch of how the main ...
Mateus de Oliveira Oliveira's user avatar
10 votes
Accepted

Natural (well studied) classes of graphs with treewidth $\Theta(n^\alpha)$ with $1/2 < \alpha < 1$

The intersection graph of interior disjoint balls in $\mathbb{R}^d$, should have treewidth $O(n^{1-1/d})$, if there is justice in the universe (let me think about it - yep - there is). The treewidth ...
Sariel Har-Peled's user avatar
10 votes
Accepted

Tree-decomposition with clique interfaces

See "Decomposition by clique separators", Robert E. Tarjan, Discrete Mathematics 55 (2): 221–232, 1985. If I understand correctly, your notion of width is essentially the size of the largest piece in ...
David Eppstein's user avatar
10 votes
Accepted

Polynomial time solvable in series parallel graph but NP-hard in graph with bounded treewidth

The quadratic traveling salesperson problem takes as input a graph and a cost for each pair of edges, and asks for a Hamiltonian cycle minimizing the sum of costs of its pairs of edges (not just ...
David Eppstein's user avatar
9 votes
Accepted

What are bounded-treewidth circuits good for?

We now understand that for any fixed bound $k \in \mathbb{N}$ on the treewidth, we can convert any Boolean circuit of treewidth less than $k$ to a so-called d-SDNNF circuit, in linear time and with ...
a3nm's user avatar
  • 9,269
9 votes
Accepted

Naive definition of treewidth

Your parameter "naive treewidth" is known as tree-partition-width in the literature. It is known that if a graph has constant treewidth and constant maximum degree, then it has constant tree-partition-...
Yota Otachi's user avatar
  • 1,731
8 votes
Accepted

Is counting simple cycles in $P$ for graphs of bounded tree width?

A simple cycle is a connected set where every vertex has degree 2. Then you have a formula SC(X) stating X (a set of edges) is a simple cycle. You can see many versions of Courcelle's theorem for ...
M. kanté's user avatar
  • 1,046
7 votes

Maximum Treewidth of a Graph with $m$ Edges

The best known upper bound of the treewidth in terms of the number of edges of a graph is as follows: the pathwidth (and therefore also the treewidth) of any graph on $n$ vertices and $m$ edges is at ...
Serge Gaspers's user avatar
6 votes
Accepted

Complexity of SAT parameterized by treewidth

FPT results The complexity of SAT, #SAT and MaxSAT parametrized by primal and incidence treewidth is FPT for all cases and of the form $2^{ck}\|F\|^d$ where $\|F\|=\sum_{C \in F} |var(C)|$ is the ...
holf's user avatar
  • 2,174
6 votes
Accepted

Something-Treewidth Property

For question $1$: any bidimensional parameter has this property on general graphs. A parameter $s(G)$ is bidimensional if the value of $s(G) \geq s(H)$ for every minor $H$ of $G$, and if $s$ is ``...
daniello's user avatar
  • 3,266
6 votes

Relation between tree-width and clique number

Theorem (6.4 in [1]): If $G$ has no pan and no even hole as an induced subgraph, then $tw(G)\leq 3\omega(G)/2-2$. Theorem (5.4 in [2]): If $G$ is odd-signable, has no clique cutset and has no cap nor ...
Florent Foucaud's user avatar
6 votes
Accepted

Tree decompositions of optimal width where every vertex is in a bounded number of bags?

Answering my own question: the answer is "no". For each $k \ge 3$, Ding and Oporowski construct a graph $G_k$ on $2k$ vertices with treewidth $3$, such that in every optimal tree decomposition of $G_k$...
hdur's user avatar
  • 261
5 votes

Program for computing Tree decomposition of a graph

LibTW can still be found. It's at http://www.treewidth.com/treewidth/ .
Mathijs's user avatar
  • 161
5 votes

Program for computing Tree decomposition of a graph

For $n\le150$ you can use the webservice over at http://treedecompositions.com/ to directly obtain and visualize a quick and reasonable decomposition, without having to compile or install anything.
Fasermaler's user avatar
5 votes

Exact Algorithms for r-Dominating Set on Bounded Treewidth Graphs

There is a recent paper by Glencora Borradaile, Hung Le: Optimal Dynamic Program for r-Domination Problems over Tree Decompositions (IPEC 2016). Here they show that there is an algorithm that given as ...
daniello's user avatar
  • 3,266
5 votes

Complexity of testing if a hypergraph has generalized hypertreewidth $2$

We do not know (to best of my knowledge).
Zoltan Miklos's user avatar
5 votes

Treewidth of two complete binary trees joined at their leaves

Indeed, this graph has treewidth 2. It's a well-known result in phylogenetics where the leaves are labelled. See Bryant, David, and Jens Lagergren. "Compatibility of unrooted phylogenetic trees is FPT....
steven kelk's user avatar
5 votes
Accepted

Treewidth relations between Boolean formulas and Tseitin encodings

There is a relation between the treewidth of a circuit and the primal treewidth of its Tseitin transformation but you will have to take the fan-in of the circuit into account, which is large when ...
holf's user avatar
  • 2,174
4 votes
Accepted

When is hypertree width more useful than generalized hypertree width?

Every XP/FPT algorithm parametrized by htw also gives an XP/FPT algorithm parametrized by ghtw (provided that the decomposition is given in the input) since there is a linear relation between ghw and ...
holf's user avatar
  • 2,174
4 votes

Does distance-2 coloring fit in Telle and Proskurowski 's algorithm for partial-k trees?

distance-2 coloring is coloring in the square (d(x,y) <= 2 implies xy an edge in the square). If a graph has tw k, its square has bounded clique-width (see Gurski-Wanke and Suchan-Todinca). See Oum ...
M. kanté's user avatar
  • 1,046
4 votes
Accepted

Does replacing each vertex of $G$ by $H$ increase treewidth of $G$ by at most $\Delta(G)$?

Let $G$ be a complete graph with $n$ vertices and $H$ be a complete graph with $n-1$ vertices, all marked. We replace each vertex of $G$ with $H$ to produce a graph $G^*$ with $n(n-1)$ vertices that ...
Laakeri's user avatar
  • 1,766
4 votes
Accepted

Parameterized complexity of tree/branch decomposition

This paper https://arxiv.org/abs/2104.07463 gives an overview of treewidth algorithms in Table 1. Similar table also exists in Wikipedia. The situation for parameterized computing of an optimal tree ...
Laakeri's user avatar
  • 1,766
4 votes

Is there a standard axiomatization of graph width parameters?

This isn't quite what you were asking for, but one of the first papers on treewidth found this parameter by axiomatizing a lattice of parameters for graphs, among which treewidth is the top element. ...
David Eppstein's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible