All Questions
Tagged with parameterized-complexity treewidth
8 questions
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
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
5
votes
2
answers
674
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
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
19
votes
1
answer
594
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 ...
- 3,722
17
votes
1
answer
617
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 ...
- 3,722
14
votes
5
answers
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$...
- 1,364