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$?
- For lots of types of subgraphs (including long paths, cycles, disjoint triangles) this can be done in FPT time.
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?
- Input: Graph $G = (V, E)$, integer $k$
- Output: Does $G$ contain $k$ disjoint triangles?
- 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?
Input: Graph $G = (V, E)$, integer $k$ Output: Does $G$ contain a path with $k$ vertices?
- 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)$.