# Questions tagged [treewidth]

Questions regarding the treewidth of graphs. Graphs of low treewidth admit fast divide-and-conquer algorithms for many graph problems that are NP-hard on general graphs.

87 questions
Filter by
Sorted by
Tagged with
1 vote
79 views

### Tractability of computing generalized hypertreewidth on bounded arity hypergraphs

Generalized hypertreewidth is a generalization of treewidth to hypergraphs. Unlike treewidth, it is not tractable, for a fixed width $k \in \mathbb{N}$, given a hypergraph $H$, to determine if $H$ has ...
184 views

### What is the treewidth of the 3D-grid (mesh or lattice) with sidelength n?

Here, by 3D-grid of sidelength $n$ I mean the graph $G=(V,E)$ with $V= \{1,\ldots,n\}^3$ and $E=\{( (a,b,c) ,(x,y,z) ) \mid |a-x|+|b-y|+|c-z|=1 \}$. I known how to get the treewidth of $n*n$ grid is ...
1 vote
49 views

1 vote
64 views

### Treewidth of monotone graph classes with bounded cliquewidth

Assume a graph class excludes a certain bicique $K_{n,n}$ and has bounded cliquewidth. Then by a result of Gurski and Wanke, this class also has bounded treewidth. Is there a similar result that ...
163 views

### Trading treewidth for depth in Boolean circuits

We know that languages defined by (poly-sized) Boolean formulae equals $\mathbf{NC}^1$: that Boolean formulae can be simulated in $\mathbf{NC}^1$ was shown by Brent/Spira [B,S], and the converse is ...
1 vote
93 views

### Can someone recommend a reference on graph minors structure theorem and sublinear treewidth?

Can someone recommend a reference on graph minors structure theorem and sublinear treewidth? Doesn't have to be the newest/strongest results as long as it's easier than tracking down all the papers ...
1 vote
64 views

### Directed tree decompositions on subtrees of DAGs

Given a DAG, is the arboreal decomposition of the DAG with the guarantee that given a node $x$, $v$ such that $x$ is reachable from $v$ are in the subtree of $x$? If not, is there a similar ...
261 views

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

I am asking this question from the context of parameter preserving reductions which has implications for kernelization (See Theorem 18 of  for an example). For simplicity, here I am assuming that ...
1 vote
73 views

### Can the theory of Bidimensionality be applied to weighted instances of a problem?

So my understanding of bidimensionality is you are assured the problem solution is about O(k^2) so you can pay O(k) purely to reduce the instance to one of bounded treewidth. As far as I know, this ...
236 views

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

Let $G$ be a graph on $n$ vertices whose maximum degree is at most $\Delta$ and whose treewidth is at most $k$. Does there exist a function $f(k, \Delta)$, independent of $n$, such that it is possible ...
181 views

### When is hypertree width more useful than generalized hypertree width?

In analysis of CSPs, there are three width notions that are analogous to treewidth: hypertree width (hw), generalized hypertree width (ghw) and fractional hypertree width (fhw). Moreover the ...
115 views

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

This question is on "Vertex Partitioning Problems" framework of Telle and Proskurowski. For solving problems in parital $k$-trees (i.e., graphs of bounded treewidth), the "Vertex ...
147 views

### How much does treewidth changes after removal of a path?

Let $G$ be a graph such that $\mathrm{tw}(G)=t$. Let $t' = \min\limits_{u,v \in V(G)} \max\limits_{P \text{ is a path from } u \text{ to } v} \mathrm{tw}(G - P)$. Then how small $t'$ can be? My ...
516 views

### Complexity of SAT parameterized by treewidth

Many papers state that Boolean satisfiability is in FPT when parameterized by primal, dual, or incidence treewidth. What are the best known time complexities of these parameterized algorithms? In ...
228 views

### Counting solutions to extended MSO formulas, and sampling -- do these appear in the literature?

I am trying to determine if the literature contains various extensions of Courcelle's theorem. Since I haven't been able to find these in the literature, I guess that these are folklore results, or ...
473 views

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

Motivation: Determining if a graph has a Hamiltonian cycle is $NP$-hard in general. However, determining if there is a Hamiltonian cycle is in polynomial time on graphs of bounded tree width, either ...
374 views

### Naive definition of treewidth

Treewidth has arguably pretty involved definition. Recently I was thinking about a problem and turns out it easy to solve it for graphs with small naive treewidth''. Naive treewidth is defined as ...
312 views

### Grid-Minor Theorem of Robertson and Seymour and its Algorithmic Applications

Graph-Minor Theorem of Robertson and Seymour  states that if graph G has large treewidth, then it contains a large grid as minor. Most approximation results on general classes of graphs with ... 1 vote
271 views

### Directed NP Hard Problem on DAG

There are problems that are NP-Hard on undirected graphs(maximum weight independent set and graph coloring) but are polynomial time solvable on trees. Tree decomposition is a good tool to talk about ...
196 views

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

Which natural (well studied) classes of graphs have treewidth that scales as $\Theta(n^\alpha)$ in the number $n$ of vertices, with $1/2 < \alpha < 1$?
465 views

### Maximum Treewidth of a Graphs with $m$ Edges

What is the maximum treewidth of a graph with $m$ edges? In other words, what is the correct growth for the following function? $\alpha(m) = max\{\mathrm{treewidth}(G): G \mbox{ has$m$edges}\}$. ...
365 views

### Finding subgraphs with high treewidth and constant degree

I am given a graph $G$ with treewidth $k$ and arbitrary degree, and I would like to find a subgraph $H$ of $G$ (not necessarily an induced subgraph) such that $H$ has constant degree and its treewidth ...
119 views

### Deterministic approximation algorithms for treewidth

As far as I understand, the factor $O(\sqrt{\log OPT})$ approximation algorithm for treewidth of Feige, Hajiaghayi, and Lee is randomized, and no deterministic approximation algorithm with this factor ...
243 views

### Paper regarding the complexity of the longest path problem on weighted directed graphs of bounded treewidth

I would like to cite a paper/report/etc that solves the following problem polynomially in $n$: Given a weighted directed graph $G=(V,E)$, $|V|=n$, of bounded treewidth $k \in \mathbb{N}$ and a source-...
333 views

### Is bounded-width SAT decidable in logspace?

Elberfeld, Jakoby, and Tantau 2010 (ECCC TR10-062) proved a space-efficient version of Bodlaender's theorem. They showed that for graphs with treewidth at most $k$, a tree decomposition of width $k$ ...
141 views

### Treewidth of two complete binary trees joined at their leaves

Let $T$ be a complete binary trees on $n$ nodes. Let $G'$ be the graph that consists of two disjoint copies of $T$. For a leaf $x \in T$, let $x_1, x_2$ be the two copies of it in $G'$. Then, let $G$ ...
820 views

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

Treewith is an important graph parameter that indicates how close a graph is from being a tree (although not in a strict topological sense). It is well known that computing the treewidth is NP-hard. ...
99 views

### Complexity of computing the simplicial width of a graph

Let $G=(V,E)$ be a finite undirected graph. A tree decomposition $(T,\lambda)$ of $G$ is a tree $T$ with labeling function $\lambda : T \to 2^{V}$ such that: For every edge $\{v_1,v_2\} \in E$, there ...
289 views

### Treewidth of deep Sierpiński Sieve Graph

Note $S_n$ the Sierpiński sieve graph of order $n$, which is obtained from the connectivity of the Sierpiński sieve. For $n$ high enough, what is the treewidth of $S_n$? I think that I can show that ...
295 views

265 views

### Tree-decomposition with clique interfaces

Let $G=(V,E)$ be a finite undirected graph. A tree decomposition $(T,\lambda)$ of $G$ is a tree $T$ with labeling function $\lambda : T \to 2^{V}$ such that: For every edge $\{v_1,v_2\} \in E$, there ...
391 views

### Classes of graphs with superconstant treewidth

There are several interesting classes of graphs with bounded treewidth. For instance, trees (treewidth 1), series parallel graphs (treewidth 2), outerplanar graphs (treewidth 2), $k$-outerplanar ...
968 views

### Tree decomposition for DAGs

Tree decompositions and treewidth are a standard way to measure how close an undirected graph is to a tree. I am studying decompositions of directed acyclic graphs (DAGs), and have come to define them ...
1k views

### Is it still open to determine the complexity of computing the treewidth of planar graphs?

For a constant $k \in \mathbb{N}$, one can determine in linear time, given an input graph $G$, whether its treewidth is $\leq k$. However, when both $k$ and $G$ are given as input, the problem is NP-...
361 views

### Does treewidth $k$ imply the existence of a $K_{1,k}$ minor?

Let $k$ be fixed, and let $G$ be a (connected) graph. If I'm not mistaken, it follows from the work of Bodlaender [1, Theorem 3.11] that if the treewidth of $G$ is roughly at least $2k^3$, then $G$ ...
The clique-width of a graph $G$ is the minimum number of labels needed to construct G by means of the following 4 operations. The Construction of a graph $G$ using the four operations is represented ...