Color coding has recently become my favorite technique in graph theory! This blog post doesn’t really do it justice. But it’s at least some notes.

Theorem. Feedback vertex set (find a set of \(k\) vertices whose deletion renders your multigraph acyclic) is in FPT.

Proof. Reduction rules:

  1. Delete vertices involved in loops
  2. Reduce multi-edges to be at most 2-multiplicity
  3. Delete connected components which are trees
  4. If you have a degree-2 vertex you can “contract”: remove the vertex and join its neighbors. This is safe because it doesn’t affect the topology of your graph.

In particular these reduction rules should guarantee that our graph has min-degree \(3\) after applying the reductions.

Now I think we have the following property: Let \(X\) be a set of \(k\) vertices whose removal renders the graph acyclic. Then \(1/2\) of the edges in \(G\) have an endpoint in \(X\).

Proof: I didn’t fully follow the proof. I think the gist is that once you remove \(X\) you gotta have a forest which has very few edges. And the min-degree condition is somehow just really good.

FPT algo: So based on the key lemma we get the following FPT algo for this problem

for 4^k itterations:
  while graph not acyclic:
    while there is a reduction rule you can apply:
      apply that reduction rule
    Now randomly guess an edge and an endpoint of that edge to add to your feedback vertex set; succeed with probability 1/4

This should work with constant PR.

Theorem. Longest Path in FPT

Proof. The cannonical example of color coding! Color, hope its rainbow, and then DP.

There’s also a fancier divide and color algorithm. The idea is you try to partition the vertex set. But you try a bunch of different partitions. You have really high branching at low depth in the recursion tree and then really low branching at high depth. Somehow this improves the constant of the standard color coding algo a tiny bit.

Theorem. Subgraph isomorphism in graphs of bounded degree.

Proof. Color edges, hope that your stuff shows up as connected components. Bounded degree condition makes it relatively likely that you get separated out.

It’s slightly more complicated if your pattern graph isn’t connected. Then you do matching at the end.

Lemma. If you randomly color a \(k\)-edge graph with \(q=100\sqrt{k}\) colors then with probability at least \(2^{-\sqrt{k}}\) you get a proper coloring

Proof. Let \(v_1,v_2,v_3,\ldots,\) be vertices that arise from the following process:

repeatedly delete a min-degree vertex

They argue that \(v_i \le O(\sqrt{k})\). Seems pretty believable.

An inequality that comes up fairly often is \(1-x \le e^{-x}\). Here they use another interesting one though: if \(x\in(0,1/2)\) then \(1-x \ge 2^{-2x}\). Neat.

They think of the random coloring as happening one vertex at a time. Then, they probability of the \(i\)-th vertex getting a good color is at least \[1-d_i / q \ge 2^{-2d_i/q}\] using our bound on \(d_i\).

Now, the total probability of success is at least:

\[2^{-2(1/q) \sum d_i} = 2^{-\sqrt{k}}.\]

It was pointed out that this is basically just a fancy way of saying that cliques maximize chromatic number per a given number of edges. But its a lot more quantitative than just saying that.

Remark. This is cool. \(2^{o(k)}\) is rare for FPT algos.

Theorem. \(d\)-clustering chromatic coloring / color and conquer.

We say that a graph is a \(d\)-cluster graph if it consists of \(d\) connected components, each of which is a clique. Problem: is there a set of \(k\) edges you can modify (add or delete) to make input graph be a \(d\)-cluster graph.

Proof.

Assume yes instance. Let \(A\) be the set of edges we need to modify. So we apply the lemma in hopes that \(A\) is properly colored.

Assume that we have a coloring of \(G\) that is a proper coloring of a solution \(A\). The key observation is that \(A\) isn’t allowed to change any connections between vertices of the same color class. Hence, the induced subgraph on each color-class must already be \(\ell\)-cluster graphs.

So now we have at most \(qd\) parts. And we try all \(d^{qd}\) ways of combining these into \(d\) clusters.

After guessing the combo we just count how many edges are missing within each of the clusters and how many bad edges go between clusters. If deleting them is within budget we do it and win. Else we keep going.

Derandomization

Remark. We will define some objects:

  • splitters
  • universal sets
  • perfect hash families

With all of them it basically turns out that they have pretty minimal overhead compared to their randomized version, usually a log factor.

Definition. SPLITTER

Let \(k\le \ell\). You can define splitters for \(k>\ell\) as well but I don’t think it’ll be necessary for us. An \((n,k,\ell)\)-splitter is a collection \(\mathcal{F}\) of colorings \(f: [n]\to [\ell]\), with the property that for any \(k\)-element subset \(S\) of \([n]\) there is some coloring \(f\in\mathcal{F}\) that is injective onto \(S\), i.e., colors each element of \(S\) a different color.

Theorem. For any \(n,k \ge 1\) one can construct an \((n,k,k^2)\)-splitter of size \(k^{O(1)}\log n\) in time \(k^{O(1)}n\log n\).

Remark. This is the main object we need. Unfortunately the dependancy chain for constructing it seems rather long.

Perfect Hash Families were introduced by Alon Yuster Zwick in their seminal Color-Coding paper. But they use some result about “bounded probability spaces”.

In any case, its obvious by a probabilistic argument that these objects exist, and while its impressive that they can be computed efficiently, its probably believable.

Definition. An \((n,k,k)\)-splitter is called an \((n,k)\)-perfect hash family.

Theorem. For any \(n,k \ge 1\) one can construct an \((n,k)\)-perfect hash family of size \(e^{k+O(\log^2 k)}\log n\) in time \(e^{k+O(\log^2 k)} n\log n\).

Remark. The construction of this object is by composing a \((k^2,k,k)\)-splitter (which is apparently easier to construct than an \((n,k)\)-perfect hash family) and an \((n,k,k^2)\)-splitter.

My attempt to construct a \((k^2,k)\)-perfect hash family: there are only \(\binom{k^2}{k}\le k^{k}\) \(k\)-element subsets of \([k^{2}]\). So, we could itterate over these sets \(S\) and for each of these define a coloring for the sole purpose of having the coloring be rainbow on \(S\). It seems they maybe have slightly better quantitative bounds, but this seems like the right vibe.

Definition. An \((n,k)\)-universal set is a family \(U\) of subsets of \([n]\) such that for any \(S\in \binom{[n]}{k}\) the family \(\{A\cap S: A\in U\}\) contains all subsets of \(S\).

Theorem. One can construct an \((n,k)\)-universal set of size \(2^{k+O(\log^2 k)}\log n\) in time \(2^{k+O(\log^2 k)}n\log n\).

Remark. How to do this: explicit construction of a \((k^2,k)\)-universal set and compose it with an \((n,k,k^2)\)-splitter.

Definition. A family of functions \(f: [n]\to [q]\) is called a \(k\)-wise independent sample space if, for every \(x\in [n]^{k}\) with distinct components and every \(y\in [q]^{k}\) we have

\[\Pr_f [f(x_1)=y_1 \land f(x_2)=y_2 \land \cdots]\]

Theorem. There exists a \(k\)-wise independent sample space of size \(O(n^{k})\) and it can be constructed in linear time in its output size.

examples of derandomization

In many cases given the above objects the derandomization is trivial.

Proposition. Deterministic Longest Path FPT algo.

Proof. For de-randomizing the vanilla version: Instead of random coloring use a perfect hash family.

For de-randomizing the fancy tree version: instead of randomly partitioning the vertex set use a universal set.

Theorem. Now we de-randomize the chromatic coding algorithm for \(d\)-clustering.

Proof. Here we need to define another one of these pseudo-random objects a “coloring family”.

The idea is we just construct a small one and then we boost it with the \((n,k,k^2)\)-splitter that we always use to boost small things.

Here’s the lemma spelled out in a bit more detail:

Take a 2-wise independent sample space of functions \(f:[k^2]\to [\sqrt{k}]\). If you randomly sample a function \(f\) from the 2-wise independent sample space and use \(f\) to color the at-most \(k^2\) vertices of a \(k\)-edge graph, then in expectation \(\sqrt{k}\) of the edges will be monochromatic. Then we use alterations to fix those edges. Alterations basically means that we itterate over all possible things that these vertices could be and give them unique colors.