I’m actually super hyped for this chapter, it looks so fancy, and has “fourier guys”. I also just realized that I really want to understand Fourier analysis. So I will probably take a class on fourier analysis instead of a complexity theory class. Hard choice.

Yeah, this chapter is low key my favorite!! I mean, color coding is still my favorite technique just because of how useful it is. But I really want to thoroughly understand this chapter because it is super cool.

PIE

PIE says

\[|\bigcap_i A_i| = \sum_{X\subseteq [n]} (-1)^{|X|} |\bigcap_{j\in X} U\setminus A_j|.\]

Now, the whole “sum over \(2^{n}\) subsets” approach might not seem good. But, let’s just do an application.

num ham cycles

Example. Fix some vertex \(v_0\). Let \(U\) be the set of length \(n\) closed walks starting at \(v_0\). Let \(A_v\) be the set of length \(n\) closed walks starting at \(v_0\) that visit vertex \(v\) at least once.

Then, the number of hamiltonian cycles in the graph is

\[\left|\bigcap_v A_v \right|\]

But we can actually compute the terms on the RHS: \[\bigcap_{v\in X} U\setminus A_v\] is the number of closed walks of length \(n\) starting from \(v_0\) in the graph \(G-X\). We can compute this with MM.

So we get a \(2^{n}n^{O(1)}\) time algo for computing number of HAM-cycles in a graph. Polynomial space, so that’s a plus.

Example. Ok now we are going to try to do Steiner Tree. In HAM cycle the key insight was that walks are easier to count than paths. Here we are going to do something similar: we are going to count “branching walks” instead of trees.

Branching walks are ordered homomorphic trees. Basically, you give me a tree with some numbers on it (subject to the stipulation that numbers on children have to be larger than numbers on their parents). And then I need to map it’s vertices to the graph. But I’m allowed to do homomorphic stuff.

So we run PIE again, and get the problem of counting the number of branching walks in certain graphs.

This can be computed with a clever DP:

Let \(b_j(a)\) denote the number of length \(j\) branching walks starting from \(a\). As the base case we have \(b_0(a) = 1\). For \(j>0\) we have \[b_j(a) = \sum_{t\in N_G(a)} \sum_{j_1+j_2 = j-1} b_{j_1}(a) b_{j_2}(t).\] The neat thing here is that we just peal off a bit of stuff from the branching walk and recurse-anate the rest.

Example. Chromatic Number

Let \(k\in O(1)\). Note that a proper \(k\)-coloring of \(V(G)\) can be thought of as a cover of \(G\) by \(k\) independent sets.

To start we compute the numbers of independent subsets of each vertex set via dynamic programming in \(2^{n}n^{O(1)}\) time. Let \(U\) be the set of \(k\)-tuples of independent sets.

Let \(A_v\) be the set of \(k\)-tuples of independent sets \(I_1,\ldots, I_k\) such that \(v\in \bigcup_i I_i\).

Then for any \(X\subseteq V\) the quantity \(\bigcap_{v\in X} A_v\) is the number of \(k\)-tuples of independent sets in \(G-X\). We can compute this easily: it’s the number of independent sets in \(G-X\) raised to the \(k\)-th power.

Then we PIE and win.

If you wanna do this in poly space the only solutions ppl know require \((2+\Omega(1))^{n}\) time. A \(3^{n}n^{O(1)}\) solution is to compute the number of independent subsets on the fly rather than storing all of them.

Fast Zeta and Mobius Transforms

Definition. \[(\zeta f)(X) = \sum_{Y\subseteq X} f(Y).\] \[(\mu f)(X) = \sum_{Y\subseteq X} (-1)^{|X\setminus Y|} f(Y).\] \[(\sigma f)(X) = (-1)^{|X|}f(X).\]

Proposition.

\[\zeta = \sigma \mu \sigma\] \[\mu = \sigma \zeta \sigma\]

Theorem. Inversion formula ( this is kinda like PIE) \(\mu\zeta = \zeta\mu = \text{id}.\)

We can view the PIE stuff as doing zeta and mobius transforms. Ok, I don’t yet get why this is a good idea. But you can do it.

Theorem. Fast Zeta / Mobius Transform

Can compute all the values of \(\zeta f, \mu f\) in \(O(2^{n}\cdot n)\) time.

subset convolution and cover product

subset convolution: \[(f*g)(Y) = \sum_{X\subseteq Y}f(X)g(Y\setminus X).\]

cover product: \[(f\star g)(Y) = \sum_{A\cup B = Y} f(A)g(B)\]

pointwise product: \[(f\cdot g)(Y) = f(Y)\cdot g(Y)\]

Observe:

\[\zeta(f\star g) = (\zeta f) \cdot (\zeta g).\]

This, combined with the inversion formula let’s us compute cover product fast.

Then, we can decompose \(f*g\) into a small number of cover products.

let’s see an application first, because it’s hard to see where we’re going.

Example. Counting colorings via fast subset convolution:

Define \(s(X): \mathcal{P}(V)\to \left\{ 0,1\right\}\) to be \(1\) iff \(X\) is an independent set. Then

\[(s*s*\cdots * s)(X)\] i.e., \(s\) convolved with itself \(k\) times is the number of \(k\)-colorings of \(G[X]\).

Remark.

Sometimes you might care about something like \[\min_{A\cup B = Y, A\perp B} f(A)+g(B)\] or \[\min_{A\cup B = Y} f(A)+g(B).\]

You can interpret these as subset convolutions / cover products over min-sum semiring.

Then you could well ask, can we compute this stuff fast? Of course the mobius transform is not at all defined over these wacky semirings becuase they have no notion of \(-1\). But if the numbers are small you can embed them and then do fast stuff. Like you literally write them as bit vectors or whatever.

Example. why you might care:

Suppose you wanted to compute the min-cost coloring of a graph. So, there is a function \(c(v,i)\) which says “coloring \(v\) color \(i\) costs \(c(v,i)\)”. You can express this as a convolution over a min-sum semiring.

longest path

looks like they spend most of the tools that they develop working on longest path problem, to give an alternative to the color coding stuff.

anyways, I’ll read that tomorrow.

ok this is super off-topic but, I was trying to come up with an algorithm for longest path in graphs of bounded tree-width. One reason you might care about such a thing is that it’d imply a \(2^{\widetilde{O}(\sqrt{n})}\) time algorithm for longest path in planar graphs.

I have a sketch of an idea, not totally sure if it works, writing it down here and hopefully can more carefully check at some point.

the idea is:

  • state = store a partition of \(X_t\) into connected components of paths and also store how the stuff within each part is connected up.
  • specifically, for the partition and ordering etc you are storing the optimal length path-forest
  • forget vertex bag: take the stuff that used to be valid and push that vertex out of the bag, and then that is still valid.
  • add edge bag: try to splice the new edge in. Note that because \(X_t\) is a separator it can’t connect down to stuff.
  • join bag: idk, maybe take a look at the steiner tree one in the book.

Remark chapter 11 has a fancy “cut and count” technique that is supposed to be better for connectivity sensitive bounded treewidth DPs. Worth checking out at some point.

hmm, not very confident in this. Anyways, back to algebraic techniques.

algebraic longest path

Let \(S_k\) denote the set of permutations of \([k]\).

We define monomials corresponding to labelled walks. We will have variables \(x_{uv}\) for whether edges are included in the walk, and variables \(y_{v,i}\) for whether vertex \(v\) got a label of \(i\) in the walk (note \(y_{v,i}, y_{v,j}\) can both be true even if \(i\neq j\)). Now for a fixed labelled walk \(W,\ell\) we can test it’s existence with the following polynomial: \[\text{mon}_{W,\ell}(x,y) = \prod x_{v_i, v_{i+1}} \prod y_{v_i, \ell(i)}.\] Then, write the polynomial: \[P(x,y) = \sum_{\text{walks } W=v_1,v_2,\ldots, v_k} \sum_{\ell \in S_k} \text{mon}_{W,\ell}(x,y).\]

Let’s say we are working over a field of characteristic \(2\), namely \(\mathbb{F}_{2^{\left\lceil 8\log k \right\rceil}}\). Then we claim that the non-path walks in the above sum cancel out. So, \(P\) is distinct from the zero polynomial (in this field) iff \(P\) has a \(k\)-path. Then we run polynomial identity testing. It’s kind of tricky to evaluate the polynomial, but turns out you can do it with weighted PIE and some DP stuff.

faster longest path

Next they describe some modifications to get better run time. But I think that’s enough for now.

update faster longest path

bipartite (undirected only)

Call the bipartition \(A\sqcup B = V\). Here it’s pretty easy. You only label vertices on one side. We have to ban paths with a \(C_2\) in them though: these are impossible to reverse. Now our reversing procedure is: If walk repeats a vertex in \(A\) then we swap the labels. If the walk repeats a vertex in \(B\) we reverse that part of the path. This is find because its undirected and gives a new path because the path has length at least \(2\).

and in our DP we can keep track of previous two vertices.

Theorem. There is a \(\sqrt{2}^{n} n^{O(1)}\) time algo for ham in undirected bipartite graphs (generalizes to \(k\)-path as well).

interlude: hardness

ink_img014

You can prove some kind of exponential lower bound if you make some assumptions about \(3SAT\) hardness. I think each vertex only gets an edge in from \(1\) clause. So number of these middle vertices is like \(\sim m\).

full undirected better

You decrease the number of labels by randomly partitioning, labelling vertices on one side and internal edges on the other side. You just Markov and have a tiny chance of the partitioning working as desired but it’s like inverse polynomial so you don’t care.

Theorem. \[ 2^{.75k} \]