Search type Search syntax
Tags [tag]
Exact "words here"
Author user:1234
user:me (yours)
Score score:3 (3+)
score:0 (none)
Answers answers:3 (3+)
answers:0 (none)
isaccepted:yes
hasaccepted:no
inquestion:1234
Views views:250
Code code:"if (foo != bar)"
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Bookmarks inbookmarks:mine
inbookmarks:1234
Status closed:yes
duplicate:no
migrated:no
wiki:no
Types is:question
is:answer
Exclude -[tag]
-apples
For more details on advanced search visit our help page
Results tagged with
Search options user 51040

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.

4
votes
We claim that the treewidth of $G^*$ is at least $n (n-1)/12$, which falsifies the conjecture. Proof: Suppose that the treewidth of $G^*$ is less than $n(n-1)/12$. …
answered Dec 17 '20 by Laakeri
4
votes
This paper https://arxiv.org/abs/2104.07463 gives an overview of treewidth algorithms in Table 1. Similar table also exists in Wikipedia. … It uses very similar techniques as the Bodlaender's algorithm for treewidth. Similarly as for treewidth, no FPT algorithms with better depency on $k$ are known. [1] Bodlaender, Hans L. …
answered Nov 25 '21 by Laakeri
4
votes
1answer
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 particular, I would expect something like $O(2^{tw} nm)$ time complexity for at least primal treewidth, but I cannot find a reference for it. Also, how about (weighted) Max-SAT and #SAT? …
asked Oct 6 '19 by Laakeri
3
votes
1answer
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). …
asked Jan 28 '20 by Laakeri