# Color Coding

55 %
45 %
Education

Published on March 7, 2014

Author: ASPAK2014

Source: slideshare.net

Color Coding and Chromatic Coding Venkatesh Raman The Institute of Mathematical Sciences 3 March 2014 Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 1 / 17

Randomized Algorithms Let Π ⊆ Σ∗ be a problem. Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 2 / 17

Randomized Algorithms Let Π ⊆ Σ∗ be a problem. Algorithm Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 2 / 17

Randomized Algorithms Let Π ⊆ Σ∗ be a problem. x ∈ Σ∗ Algorithm Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 2 / 17

Randomized Algorithms Let Π ⊆ Σ∗ be a problem. x ∈ Σ∗ Algorithm Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 2 / 17

Randomized Algorithms Let Π ⊆ Σ∗ be a problem. x ∈ Σ∗ Algorithm x ∈ Π? (Output correct answer with good probability) Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 2 / 17

Randomized Algorithms Let Π ⊆ Σ∗ be a problem. x ∈ Σ∗ Algorithm x ∈ Π? (Output correct answer with good probability) Here we are interested in randomized algorithms for parameterized problems taking running time f (k)|x|O(1) with constant success probability. Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 2 / 17

Randomized Algorithm for UFVS Deﬁnition (Feedback Vertex Set) Let G = (V , E ) be an undirected graph. S ⊆ V is called feedback vertex set if G S is a forest. Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 3 / 17

Randomized Algorithm for UFVS Deﬁnition (Feedback Vertex Set) Let G = (V , E ) be an undirected graph. S ⊆ V is called feedback vertex set if G S is a forest. Undirected Feedback Vertex Set (UFVS) Input: Parameter: Question: An undirected graph G = (V , E ) and a positive integer k k Does there exists a feedback vertex set of size at most k Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 3 / 17

Randomized Algorithm for UFVS Do the following preprocessing rules Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 4 / 17

Randomized Algorithm for UFVS Do the following preprocessing rules Delete degree ≤ 1 vertices. Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 4 / 17

Randomized Algorithm for UFVS Do the following preprocessing rules Delete degree ≤ 1 vertices. Short circuit degree 2 vertices. Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 4 / 17

Randomized Algorithm for UFVS Do the following preprocessing rules Delete degree ≤ 1 vertices. Short circuit degree 2 vertices. Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 4 / 17

Randomized Algorithm for UFVS Do the following preprocessing rules Delete degree ≤ 1 vertices. Short circuit degree 2 vertices. Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 4 / 17

Randomized Algorithm for UFVS Do the following preprocessing rules Delete degree ≤ 1 vertices. Short circuit degree 2 vertices. Add vertex x to FVS, if x has self loop. Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 4 / 17

Randomized Algorithm for UFVS Do the following preprocessing rules Delete degree ≤ 1 vertices. Short circuit degree 2 vertices. Add vertex x to FVS, if x has self loop. Now we can assume every vertex in G has degree ≥ 3. Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 4 / 17

Randomized Algorithm for UFVS Claim : If G is graph with minimum degree ≥ 3, then number of edges incident to any FVS F is ≥ E (G ) . 2 Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 5 / 17

Randomized Algorithm for UFVS Claim : If G is graph with minimum degree ≥ 3, then number of edges incident to any FVS F is ≥ E (G ) . 2 Proof: F H=G - F ; Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 5 / 17

Randomized Algorithm for UFVS Claim : If G is graph with minimum degree ≥ 3, then number of edges incident to any FVS F is ≥ E (G ) . 2 Proof: Let V≤1 = set of degree ≤ 1 vertices in H, V2 = set of degree 2 vertices in H, and F V≥3 = set of degree ≥ 3 vertices in H. H=G - F ; Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 5 / 17

Randomized Algorithm for UFVS Claim : If G is graph with minimum degree ≥ 3, then number of edges incident to any FVS F is ≥ E (G ) . 2 Proof: Let V≤1 = set of degree ≤ 1 vertices in H, V2 = set of degree 2 vertices in H, and F V≥3 = set of degree ≥ 3 vertices in H. Number of edges between H and F , E (H, F ) ≥ 2V≤1 + V2 H=G - F ; Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 5 / 17

Randomized Algorithm for UFVS Claim : If G is graph with minimum degree ≥ 3, then number of edges incident to any FVS F is ≥ E (G ) . 2 Proof: Let V≤1 = set of degree ≤ 1 vertices in H, V2 = set of degree 2 vertices in H, and F V≥3 = set of degree ≥ 3 vertices in H. Number of edges between H and F , E (H, F ) ≥ 2V≤1 + V2 > V≤1 + V2 + V≥3 ( V≤1 > V≥3 ) H=G - F ; Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 5 / 17

Randomized Algorithm for UFVS Claim : If G is graph with minimum degree ≥ 3, then number of edges incident to any FVS F is ≥ E (G ) . 2 Proof: Let V≤1 = set of degree ≤ 1 vertices in H, V2 = set of degree 2 vertices in H, and F V≥3 = set of degree ≥ 3 vertices in H. Number of edges between H and F , E (H, F ) ≥ 2V≤1 + V2 > V≤1 + V2 + V≥3 ( V≤1 > V≥3 ) = V (H)> E (H). H=G - F ; Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 5 / 17

Randomized Algorithm for UFVS Algorithm Initially we set S ← ∅. Now run the following steps k times. 1: Apply preprocessing rules and create an equivalent instance (G , k ) 2: Pick an edge e, u.a.r (i.e with probability 1 E (G ) ) 3: Choose an end point of e, u.a.r (i.e with probability 1 ) into S and 2 delete it from the graph. Now if S is a FVS, output S, otherwise output No. Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 6 / 17

Analysis If the input instance is No instance Pr[Algorithm output No] = 1. Let the input instance is Yes instance and F is a FVS od size ≤ k. Pr[Choosing an edge incident to F in step 2] ≥ Pr[Chosen vertex is in F in step 3] ≥ Pr[S=F] ≥ 1 2 1 1 · 2 2 1 4k Now we repeat the algorithm 4k times. 1 Pr[Algorithm fails in all repetitions] ≤ 1 − 4k 1 Pr[Algorithm succeed at least once] ≥ 1 − e ≥ Venkatesh Raman (IMSc) Randomized Techniques in FPT 4k 1 2 1 ≤ e. 3 March 2014 7 / 17

Color Coding This technique is introduced by Alon et al. (1995) This technique is used to solve constant treewidth k-sized subgraph isomorphism problem. Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 8 / 17

Color Coding This technique is introduced by Alon et al. (1995) This technique is used to solve constant treewidth k-sized subgraph isomorphism problem. We illustrate this technique by applying to k-path Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 8 / 17

k-path k-path Input: Parameter: Question: An undirected graph G and a positive integer k k Does there exists a path on k vertices in G Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 9 / 17

Colorful path v1 v5 v7 v2 v6 v3 v4 Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 10 / 17

Colorful path v1 v5 v7 v2 v6 v3 v4 colorful path on 5 vertices in the graph G ? Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 10 / 17

Algorithm for k-path Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 11 / 17

Algorithm for k-path Color each vertex of the input graph G , u.a.r using from the set of k colors, [k] Check whether there exists a colorful k-path in the colored graph and output Yes/No accordingly Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 11 / 17

Algorithm for k-path Color each vertex of the input graph G , u.a.r using from the set of k colors, [k] Check whether there exists a colorful k-path in the colored graph and output Yes/No accordingly Running Time : Time to check colorful k-path × nO(1) Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 11 / 17

Algorithm for k-path Color each vertex of the input graph G , u.a.r using from the set of k colors, [k] Check whether there exists a colorful k-path in the colored graph and output Yes/No accordingly Running Time : Time to check colorful k-path × nO(1) Probability of success If (G , k) is a No instance, the probability of success is 1. If (G , k) is an Yes instance, the probability of success is at least Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 k! . kk 11 / 17

DP for Checking colorful k-path We introduce 2k · |V (G )| Boolean variables: x(v , C ) = TRUE for some v ∈ V (G ) and C ⊆ [k] There is path ends at v where each color in C appears exactly once and no other color appears. Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 12 / 17

DP for Checking colorful k-path Clearly, x(v , {color (v )}) = TRUE. Recurrence for vertex v with color r : x(u, C {r }) x(v , C ) = uv ∈E (G ) If we know every x(v , C ) with |C | = i, then we can determine every x(v , C ) with |C | = i + 1. All the values can be determined in time O(2k · |E (G )|). There is a colorful path ends at t ⇐⇒ x(t, [k]) = TRUE for some t. Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 13 / 17

Analysis for k-path The algorithm for k-path has Running time 2k nO(1) Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 14 / 17

Analysis for k-path The algorithm for k-path has Running time 2k nO(1) Success probability k! at least k k if (G , k) is an Yes instance 1 if (G , k) is an No instance Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 14 / 17

Analysis for k-path The algorithm for k-path has Running time 2k nO(1) Success probability k! at least k k if (G , k) is an Yes instance 1 if (G , k) is an No instance k Now run the algorithm k (≤ e k ) times and output Yes if at least once we k! get an Yes answer, otherwise output No. Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 14 / 17

Analysis for k-path The algorithm for k-path has Running time 2k nO(1) Success probability k! at least k k if (G , k) is an Yes instance 1 if (G , k) is an No instance k Now run the algorithm k (≤ e k ) times and output Yes if at least once we k! get an Yes answer, otherwise output No. Probability of failure ≤ 1 − Venkatesh Raman (IMSc) k k! k /k! kk ≤ e −1 Randomized Techniques in FPT 3 March 2014 14 / 17

Analysis for k-path The algorithm for k-path has Running time 2k nO(1) Success probability k! at least k k if (G , k) is an Yes instance 1 if (G , k) is an No instance k Now run the algorithm k (≤ e k ) times and output Yes if at least once we k! get an Yes answer, otherwise output No. Probability of failure ≤ 1 − k k! k /k! kk ≤ e −1 k-path can be solved in randomized (2e)k nO(1) time, with constant success probability. Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 14 / 17

Derandomization Suppose we have a list of colorings col1 , col2 , . . . , colm such that for any S ⊆ V with |S| = k there exists i, coli is one-to-one on S, then instead of random coloring we can use these list of colorings to get a deterministic algorithm. Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 15 / 17

Derandomization Suppose we have a list of colorings col1 , col2 , . . . , colm such that for any S ⊆ V with |S| = k there exists i, coli is one-to-one on S, then instead of random coloring we can use these list of colorings to get a deterministic algorithm. Such a list of colorings is called an (n, k)-family of perfect hash functions Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 15 / 17

Derandomization Suppose we have a list of colorings col1 , col2 , . . . , colm such that for any S ⊆ V with |S| = k there exists i, coli is one-to-one on S, then instead of random coloring we can use these list of colorings to get a deterministic algorithm. Such a list of colorings is called an (n, k)-family of perfect hash functions There exists an (n, k)-family of perfect hash functions of size e k k O(log k) log2 n and can be constructed in time linear in the output size Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 15 / 17

Derandomization Suppose we have a list of colorings col1 , col2 , . . . , colm such that for any S ⊆ V with |S| = k there exists i, coli is one-to-one on S, then instead of random coloring we can use these list of colorings to get a deterministic algorithm. Such a list of colorings is called an (n, k)-family of perfect hash functions There exists an (n, k)-family of perfect hash functions of size e k k O(log k) log2 n and can be constructed in time linear in the output size k-path can be solved deterministically in (2e)k k O(log k) nO(1) time. Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 15 / 17

Chromatic Coding Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 16 / 17

Thank You Venkatesh Raman (IMSc) Randomized Techniques in FPT 3 March 2014 17 / 17

 User name: Comment:

## Related presentations

#### Identification of critically ill children

November 18, 2018

#### Good Maths Tutor a rare find

November 18, 2018

#### Informaciona tehnologija-lekcija 14 - Blockchain

November 18, 2018

#### When you want to take the right step for your care...

November 18, 2018

#### Contemporary O Level Maths Tuition

November 18, 2018

#### Manual de Comercio Exterior

November 18, 2018

## Related pages

### Html Color Codes

Get HTML color codes for your website. Color chart, color picker and color palettes.

### Color code - Wikipedia

A color code or colour code is a system for displaying information by using different colors. ... Systems incorporating color-coding include: In electronics:

### Color-coding - Wikipedia

In computer science and graph theory, the method of color-coding efficiently finds k-vertex simple paths, k-vertex cycles, and other small subgraphs within ...

### HTML color codes and names - Computer Hope

HTML color codes, color names, and color chart with all hexadecimal, RGB, HSL, color ranges, and swatches.

### color coding - Englisch ⇔ Deutsch Wörterbuch - leo.org

Das Sprachangebot für Englisch-Deutsch: Wörterbuch mit Übersetzungen, Flexionstabellen und Audio, interaktivem Forum und Trainer für flexibles Lernen.

### RGB Color Codes Chart - RapidTables.com

RGB color space or RGB color system, constructs all the colors from the combination of the Red, Green and Blue colors. The red, green and blue use 8 bits ...

### HTML Color Picker - W3Schools

Colors HOME Color Names Color Values Color Groups Color Shades Color Picker Color Mixer Color Converter Color RGB Color HEX Color HSL Color HWB Color CMYK ...

### dict.cc | colour coding | Wörterbuch Englisch-Deutsch

Übersetzung für colour coding im Englisch-Deutsch-Wörterbuch dict.cc.