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

75 questions
Filter by
Sorted by
Tagged with
68 views

### Solving Feedback vertex set using dynamic programming on nice tree decomposition

I am interested in a specific solution to the Feedback Vertex Set In theorem 7.10 from this book, it is stated that Feedback Vertex Set can be solved in $k^{O(k)}$ using tree decomposition. I learned ...
55 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 ...
97 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 ...
86 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 ...
39 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 ...
210 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 ...
45 views

### Three Clique Sums of Bounded Treewidth and Bounded Genus graphs

This question asks about the forbidden minors of the class of graphs that can be formed by taking three clique sums of planar graphs and bounded treewidth graphs(The class is defined for some constant ...
67 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 ...
166 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 ...
127 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 ...
110 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 ...
141 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 ...
283 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 ...
202 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 ...
369 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 ...
322 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 ...
150 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 ...
185 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 ...
178 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$?
319 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}\}$. ...
288 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 ...
112 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 ...
178 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-...
296 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$ ...
116 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$ ...
685 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. ...
95 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 ...
246 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 ...
274 views

227 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 ...
329 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 ...
684 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 ...
821 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-...
342 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$ ...
213 views

### Number of k-expressions of graph (clique Width)

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 ...
404 views

### Algorithmic advantages of pathwidth over treewidth

Treewidth plays an important role in FPT algorithms, in part because many problems are FPT parameterized by treewidth. A related, more restricted, notion is that of pathwidth. If a graph has pathwidth ...
391 views

### Enumerating Planar Graphs of Bounded Treewidth

I am looking for references for the following problem: given integers $n$ and $k$, enumerate all non-isomorphic planar graphs on $n$ vertices and treewidth $\leq k$. I'm interested both in theoretical ...
441 views

### Minimum Tree-width of circuit for MAJORITY

What is the minimum tree-width of a circuit over $\{\wedge,\vee,\neg\}$ for computing MAJ? Here MAJ $:\{0,1\}^n \rightarrow \{0,1\}$ outputs 1 iff at least half of its inputs are $1$. I care only ...
594 views

### What separates easy global problems from hard global problems on graphs of bounded treewidth?

Plenty of hard graph problems are solvable in polynomial time on graphs of bounded treewidth. Indeed, textbooks typically use e.g. independet set as an example, which is a local problem. Roughly, a ...
296 views

### What are bounded-treewidth circuits good for?

One can talk of the treewidth of a Boolean circuit, defining it as the treewidth of the "moralized" graph on wires (vertices) obtained as follows: connect wires $a$ and $b$ whenever $b$ is the output ...
1k views

### Relation between tree-width and clique number

Are there any nice graph classes for which the tree-width $tw(G)$ is upper-bounded by a function of the clique number $\omega(G)$, i.e. $tw(G)\leq f(\omega(G))$? For example, it is a classic fact ...
274 views

### Clique-width expressions with logarithmic depth

When we are given a tree decomposition of a graph $G$ with width $w$, there are several ways in which we can make it "nice". In particular, it is known that it is possible to transform it into a tree ...
519 views

### Polynomial time solvable instances of Max-Sat

The problem Max-Sat ask you to find an assignment of a CNF formula which satisfy as many clauses as possible. For the simpler problem SAT there are many known special cases which can be solved in ...
441 views

### How to go from a DAG model to bounded treewidth?

I am cross posting this question from CS.SE since I believe it is research-related question. Given a Bayesian Network DAG $G$, we can transform it into a junction tree $T_G$ by performing two steps:...
1k views

### Exact Algorithms for r-Dominating Set on Bounded Treewidth Graphs

Given a graph, $G = (V, E)$, I want to find an optimal $r$-domination for $G$. That is, I want a subset $S$ of $V$ such that all vertices in $G$ are at a distance of at most $r$ from some vertex in $S$...
795 views

### What's the correlation between treewidth and instance hardness for random 3-SAT?

This recent paper from FOCS2013, Strong Backdoors to Bounded Treewidth SAT by Gaspers and Szeider talks about the link between the treewidth of the SAT clause graph and instance hardness. For ...
Is the following graph class known in the literature? The class of graphs is parameterized by positive integers $d$ and $t$ and contains each graph $G=(V,E)$ such that for each vertex $v\in V$, the ...