# Tag Info

## Hot answers tagged treewidth

### 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,266
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 ...
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 ...

### 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 ...
• 3,698
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,999
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, ...
• 840
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 ...
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,626
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 ...
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 ...
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 ...
• 9,269
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
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,046

### 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 ...
• 5,116
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,174
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,266

### 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,153
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

### Program for computing Tree decomposition of a graph

LibTW can still be found. It's at http://www.treewidth.com/treewidth/ .
• 161

### 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

### 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,266

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

We do not know (to best of my knowledge).

### 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....
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,174
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,174

### 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,046
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,766