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 ...
- 3,256
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 ...
- 50.8k
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 ...
- 50.8k
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$. ...
- 6,979
13
votes
Accepted
Is it still open to determine the complexity of computing the treewidth of planar graphs?
As far as I know the NP-completeness of computing the treewidth of a planar graph is still open. The most recent reference I know is a survey by Bodlaender from 2012 called `Fixed-Parameter ...
- 5,255
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 ...
- 50.8k
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 ...
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 ...
- 9,596
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 ...
- 8,836
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-...
- 1,731
9
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 ...
- 50.8k
8
votes
Accepted
Maximum Treewidth of a Graphs 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, ...
- 810
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 ...
- 1,036
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 ...
- 2,089
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 ``...
- 3,256
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 ...
- 2,143
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$...
- 261
5
votes
Program for computing Tree decomposition of a graph
LibTW can still be found. It's at http://www.treewidth.com/treewidth/ .
- 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.
- 265
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 ...
- 3,256
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....
- 71
5
votes
Complexity of testing if a hypergraph has generalized hypertreewidth $2$
We do not know (to best of my knowledge).
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 ...
- 2,089
4
votes
Maximum Treewidth of a Graphs 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 ...
- 5,066
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 ...
- 1,036
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 ...
- 2,089
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 ...
- 1,716
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 ...
- 1,716
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. ...
- 50.8k
Only top scored, non community-wiki answers of a minimum length are eligible