In today 6pm KST, I will stream solving problems related to Chordal Graphs and Tree decompositions. Stream link is here.
List of featured problems
Even if the problem has some special structure, I will ignore it and only assume that it is a Chordal Graph or a graph with bounded treewidth.
Stream will end if someone asks me to play League together. I think it will probably last about 4 hours.
Enjoy!
what if the entire chat asks if you could play league together
edit: apologies, I am not funny :(
1/10
Stream is now live!
Stream is finished. I solved the last three problems. Thanks to everyone for participating!
Stream notes
Apollonian Network, City Tour
Road
Sister Ports
Kid's Nightmare
Palindromic Equivalence (AC)
How to find "forest" given tree decomposition For each node $$$v$$$, just take bag as $$$B(v) = {v} \cup {w | w > v, (w, v) \in E}$$$ Trivial, that tree decomposition is exactly all set of edges How are the base tree..? I believe, it's the smallest $$$w$$$ such that $$$w > v, (w, v) \in E$$$ if such $$$w$$$ does not exists then it's the root of the forest. can the "subtree" prop be proved. If some node $$$w$$$ belongs to $$$B(v)$$$, then it will belong to $$$B(par(v))$$$ UNLESS $$$v = w$$$
I just checked your twitch channel and saw that the vod is not available. Have you recorded the lecture? I am super interested but I missed the stream :/
Sorry, I don't want it to be recorded :( But it's not a lecture, so probably won't be something you'd want
Got it! I have seen such concepts in college (from a theoretical point of view) but I always found the decompositions hard to code. Anyway, thanks for answering!