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.

Filter by
Sorted by
Tagged with
4
votes
0answers
91 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
0answers
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 ...
1
vote
0answers
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 ...
4
votes
2answers
205 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 [1] for an example). For simplicity, here I am assuming that ...
1
vote
0answers
44 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 ...
1
vote
0answers
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 ...
9
votes
1answer
161 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 ...
3
votes
1answer
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 ...
2
votes
2answers
109 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 ...
5
votes
0answers
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 ...
4
votes
1answer
279 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 ...
14
votes
0answers
201 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 ...
4
votes
3answers
363 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 ...
6
votes
1answer
319 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 ...
6
votes
0answers
149 views

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

Graph-Minor Theorem of Robertson and Seymour [1] 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
0answers
176 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 ...
3
votes
1answer
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$?
2
votes
2answers
313 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}\}$. ...
9
votes
1answer
250 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 ...
7
votes
0answers
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 ...
2
votes
0answers
176 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-...
10
votes
1answer
294 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$ ...
2
votes
1answer
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$ ...
13
votes
1answer
675 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. ...
7
votes
0answers
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 ...
6
votes
1answer
243 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 ...
9
votes
2answers
271 views

Something-Treewidth Property

Let $s$ be a graph parameter (ex. diameter, domination number, etc) A family $\mathcal{F}$ of graphs has the $s$-treewidth property if there is a function $f$ such that for any graph $G\in \mathcal{...
7
votes
2answers
272 views

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

A hypergraph $H = (V, E)$ consists of a set of vertices $V$ and a set $E$ of hyperedges, i.e., subsets of $V$. The generalized hypertreewidth (GHW) parameter is a measure of the cyclicity of a ...
16
votes
0answers
330 views

Complexity of the homomorphism problem parameterized by treewidth

The homomorphism problem $\text{Hom}(\mathcal{G}, \mathcal{H})$ for two classes $\mathcal{G}$ and $\mathcal{H}$ of graphs is defined as follows: Input: a graph $G$ in $\mathcal{G}$, a graph $H$ in $...
7
votes
1answer
223 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 ...
10
votes
1answer
327 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 ...
5
votes
0answers
666 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 ...
24
votes
1answer
815 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-...
12
votes
1answer
341 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$ ...
0
votes
2answers
208 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 ...
19
votes
1answer
400 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 ...
9
votes
2answers
381 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 ...
13
votes
2answers
439 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 ...
19
votes
3answers
593 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 ...
15
votes
1answer
289 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 ...
13
votes
3answers
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 ...
15
votes
1answer
266 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 ...
18
votes
2answers
513 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 ...
4
votes
0answers
433 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:...
14
votes
5answers
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$...
11
votes
2answers
789 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 ...
18
votes
5answers
1k views

Fast treewidth algorithms

I would like to compute the treewidth of a graph. There are really good heuristics for other NP-hard graph problems such as VF2 for subgraph isomorphism, with code available in igraph for example. I ...
17
votes
2answers
388 views

Generalization of locally bounded treewidth graphs

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 ...
5
votes
1answer
472 views

Long Cycle in Bounded Tree-Width Graphs using DFS and Dynamic Programming

For fixed parameter $k$, I would like to find a long cycle of length $\geq k$ in an undirected graph $G(V,E)$. This can be done in $O(k!2^k|V|)$-time [2] using 1) depth-first search (DFS) and 2) ...
11
votes
1answer
388 views

MSO properties, planar graphs and minor-free graphs

Courcelle's theorem states that every graph property definable in monadic second-order logic can be decided in linear time on graphs of bounded treewidth. This is one of the most well-known ...