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.
90 questions
12
votes
2
answers
733
views
Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees
Do we know any problem that satisfies the following criteria?
It is polynomial-time solvable on trees.
It is NP-complete when restricted to graphs of treewidth 2.
The problem can be encoded only ...
6
votes
1
answer
179
views
Tree decompositions with unique witness for each edge
In this question I am concerned with tree decompositions of undirected graphs. Recall that a tree decomposition of a graph $G = (V, E)$ is a tree $T$ whose nodes are subsets of $V$ (called bags) ...
- 9,838
9
votes
1
answer
243
views
What is the smallest graph of treewidth $k$ having less edges than the $(k+1)$-clique?
Treewidth is a graph parameter measuring how close a graph is to being a tree. I am interested in what is the minimal number of edges required for a graph to have treewidth $k$.
A natural family of ...
- 9,838
1
vote
1
answer
130
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 ...
- 9,838
3
votes
1
answer
247
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 ...
- 388
1
vote
0
answers
54
views
Bound on the treewidth of a graph from modular contraction
I cannot find a reference for this easy to prove result concerning the treewidth of a graph with respect to the treewidth of a modular contraction of it.
Let $G=(V,E)$ be a graph. A module $M \...
- 2,344
0
votes
0
answers
173
views
What's the connection between branchwidth and treewidth
I understand that treewidth and branchwidth are essentially equivalent for a fixed graph, given that $branchwidth(G) = Θ(treewidth(G))$.
However, my question pertains to a specific case involving ...
- 388
3
votes
1
answer
173
views
Treewidth for hypergraphs that specify connectedness requirements
This question is about an alternative definition of treewidth, called weak treewidth. It is defined on hypergraphs where hyperedges intuitively require that the connected subtrees of occurrences of ...
- 9,838
3
votes
1
answer
119
views
Polynomial time solvable in series parallel graph but NP-hard in graph with bounded treewidth
Whether there is a problem to meet the conditions: it is polynomial time solvable in series parallel graphs but NP-hard in graph with bounded treewidth?
- 139
5
votes
2
answers
265
views
Treewidth relations between Boolean formulas and Tseitin encodings
Suppose you have a propositional formula $\varphi$ in CNF. You want to efficiently obtain an equisatisfiable CNF formula encoding $\neg \varphi$. You use the usual Tseitin encoding with auxiliary ...
- 1,049
1
vote
1
answer
192
views
Nontrivial Algorithms for Coloring (Parameterized by Pathwidth)
Let $k$ be a positive integer. In the $k$-coloring problem, we are given a graph $G$ on $n$ nodes, and want to determine if there is a way to assign a color to each vertex of $G$ such that no two ...
- 696
1
vote
1
answer
122
views
On motivation towards study of width parameters beyond treewidth
Many width parameters are invented to capture the tractability of CSP (and its equivalent problem, conjunctive queries (CQ) evaluation): treewidth, hypertree width, generalized hypertree width, ...
- 125
5
votes
1
answer
182
views
Is there a standard axiomatization of graph width parameters?
There are many useful graph properties described as "width parameters" that show up in algorithm analysis (especially for FPT-type algorithms). The most famous example is probably treewidth,...
- 2,531
3
votes
2
answers
177
views
Parameterized complexity of tree/branch decomposition
I'm looking for an up to date reference for parameterized complexity of tree and branch decompositions. IE, complexity of finding tree/branch decomposition of optimal width in terms of relevant graph ...
- 4,731
2
votes
0
answers
88
views
What is the expected treewidth of a large-treewidth graph intersected with Erdos-Renyi graph?
Suppose we have a graph $G$ with treewidth $t$. Let $p \in (0,1)$ be a constant. Then let's independently remove each edge from $G$ with probability $p$. What is the expected treewidth of the ...
- 309
0
votes
0
answers
78
views
Low-Treewidth Sorting Networks
It was previously asked if there exist Boolean circuits of treewidth $O(\log n)$ that compute the majority function $\text{MAJ}_n$ on $n$ inputs. While a construction using online algorithms and the ...
- 101
2
votes
0
answers
97
views
How typical are odd-H-minor free graphs?
Can anything be said about how typical are odd-H-minor free graphs? (definition of odd-minor-free is in Section 2.2 of notes, page 20 of slides). For instance, for a random graph with $n$ vertices, $...
- 4,731
1
vote
1
answer
70
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 ...
- 61
5
votes
0
answers
198
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 ...
- 223
1
vote
0
answers
98
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 ...
- 228
1
vote
0
answers
75
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 ...
- 23
4
votes
2
answers
282
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,869
2
votes
0
answers
84
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 ...
- 228
10
votes
1
answer
256
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 ...
- 261
3
votes
1
answer
213
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 ...
- 1,901
2
votes
2
answers
119
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 ...
- 1,869
5
votes
0
answers
154
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 ...
- 309
6
votes
1
answer
637
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 ...
- 1,901
14
votes
0
answers
240
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 ...
- 1,479
5
votes
3
answers
510
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 ...
- 1,479
6
votes
1
answer
382
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 ...
- 309
6
votes
0
answers
422
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 ...
user17918
1
vote
0
answers
287
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 ...
- 23
3
votes
1
answer
199
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$?
- 848
5
votes
2
answers
676
views
Maximum Treewidth of a Graph 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}\}$.
...
- 696
10
votes
2
answers
381
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 ...
- 9,838
7
votes
0
answers
122
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 ...
- 3,276
2
votes
0
answers
279
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-...
- 103
10
votes
1
answer
353
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$ ...
- 19.2k
2
votes
1
answer
152
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$ ...
- 79
14
votes
1
answer
851
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.
...
- 894
7
votes
0
answers
102
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 ...
- 1,481
6
votes
1
answer
301
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 ...
- 63
9
votes
2
answers
315
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{...
- 696
8
votes
2
answers
309
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 ...
- 9,838
18
votes
0
answers
442
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 $...
- 9,838
7
votes
1
answer
276
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 ...
- 1,481
11
votes
1
answer
407
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
0
answers
1k
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 ...
- 9,838
26
votes
1
answer
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-...
- 9,838