Stream notes

Apollonian Network, City Tour

• simple path = subset of edges which is connected, two degree-1 vertices, others with degree 2
• $$$DP[v][S][degreeCount][unionStatus]$$$ = Maximum edge cost sum, rooted at vertex $$$v$$$, path includes vertices in $$$S$$$, $$$degreeCount$$$ contains vector of degrees (for vertices in $$$S$$$), $$$unionStatus$$$ denotes the UF for vertices in $$$S$$$
• Each edges are considered in the topmost node in tree-decomposition *

Road

Sister Ports

• consider each edge in topmost bags (how?)
• $$$DP[v][S]$$$ = consider bag $$$v$$$, node $$$S$$$ remains unmatched
• recurse to subproblems, halt if a subproblem ends up ignoring some nodes

Kid's Nightmare

• $$$DP[v][S]$$$ = consider bag $$$v$$$, pick $$$S \subseteq B(v)$$$ as a set, maximum attainable
• first defined as a collection from subtrees
• then, for $$$DP[v][S]$$$ with $$$|S| \le 1, v \notin S$$$, update value to $$$DP[v][S \cup {v}]$$$

Palindromic Equivalence (AC)

• Hmm, somebody told me there is a chordal structure
• Rules enforces some pair of nodes to have same color.
• Rules enforces some pair of nodes to have different colors.
• There is such kind of graph and I believe it's chordal (ONTAK 2010) Probably that's why I wrote "chordal graph" in my note lol
• So, task asks to find # of independent sets in chordal graph
• $$$DP[v][w]$$$ = Bag $$$v$$$ in tree decomp, choose $$$w$$$ ($$$w$$$ can possibly denote nil vertex)
• You can only choose some node in the topmost bag
• If you carry some node, then the child shall carry that node if it exists
• Ok, I can write it
• hope this is not quadratic~ (per limits it doesn't matter i guess:) )

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$$$

// given simple, nonempty graph
// in O(m log n), returns permutation of vertices (positive) or empty vector (negative) such that
// for p[i], all j > i such that p[j] is adjacent to p[i], constitutes cliques.
// for each undir edge (s, e), both s \in gph[e], e \in gph[s] should hold