Notes - ADS HT24, Colour coding


Flashcards

What sort of decision problems is the technique of colour coding useful for?


Searching for a subgraph $H$ in a graph $G$ (e.g. a long path, a cycle, a set of disjoint triangles).

Can you summarise the technique of colour coding for tackling $\mathbf{NP}$ problems where we are searching for a subgraph $H$ of size $k$ in a graph $G$ (e.g. a long path, a cycle, a set of disjoint triangles)? Briefly explain why this is useful.


  • Colour the vertices of $G$ randomly using $k$ colours
  • Search for a colourful copy of $H$ in $G$
    • For lots of types of subgraphs (including long paths, cycles, disjoint triangles) this can be done in FPT time.
  • Repeat multiple times to get a high probability such a subgraph is found

The technique of color coding for $\mathbf{NP}$ problems where we are searching for a subgraph $H$ of size $k$ in a graph $G$ (e.g. a long path, a cycle, a set of disjoint triangles) works roughly as follows:

  • Colour the vertices of $G$ randomly using $k$ colours
  • Search for a colourful copy of $H$ in $G$ (one that includes all $k$ colours)
    • For lots of types of subgraphs (including long paths, cycles, disjoint triangles) this can be done in FPT time.
  • Repeat multiple times to get a high probability such a subgraph is found

Suppose we are looking for a subgraph with $k$ vertices. What is the probability that the coloured graph $G$ contains a colourful copy of $H$?


\[\frac{1}{k^k}\]

The $\mathbf{DisjointTriangles}$ decision problem is:

  • Input: Graph $G = (V, E)$, integer $k$
  • Output: Does $G$ contain $k$ disjoint triangles?

This problem is part of a general class of problems where we are searching for a subgraph $H$ in a larger graph $G$, and here the technique of colour coding is applicable. Can you describe a randomised FPT algorithm that solves this problem?


  • Randomly colour vertices of $G$ using $3k$ colours, $j \in \{1, \cdots, 3k\}$ with probability $1/(3k)$
  • For $j = 0, \cdots, k-1$, search for a triangle using colours $3j + 1, 3j + 2, 3j + 3$.
  • If $G$ does not contain $k$ disjoint triangles, the probability of finding $k$ triangles as required is $0$.
  • If $G$ does contain $k$ disjoint triangles, the probability of finding $k$ triangles is $1/(3k)^{3k}$ (since the probability a given triangle has the correct colour configuration is $1/(3k)^3$, and we repeat this $k$ times).
  • Repeat as many times as neccessary to get good guarantees on an answer.

The $\mathbf{LongestPath}$ decision problem is:

Input: Graph $G = (V, E)$, integer $k$ Output: Does $G$ contain a path with $k$ vertices?

This problem is part of a general class of problems where we are searching for a subgraph $H$ in a larger graph $G$, and here the technique of colour coding is applicable. Can you describe a randomised FPT algorithm that solves this problem?


  • Randomly colour vertices of $G$ using $k$ colours, $j \in \{1, \cdots, k\}$ with probability $1/k$.
  • Íearch for a path whose 1st vertex takes colour $1$, 2nd vertex takes colour $2$, etc.
  • If $G$ does not contain a path with $k$ vertices, the probability of finding such a path is $0$.
  • If $G$ does contain such a path, the probability of success is $1/(k^k)$.

Proofs




Related posts