Chromatic Coding

Speaker(s)

Saket Saurabh

Affiliation

Institute of Mathematical Sciences, Chennai, India

Date

June 2, 2011, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

Alon, Yuster and Zwick developed the method of color-coding to give a 2^O(k)n^O(t)  time algorithm for subgraph isomorphism problem when the subgraph we are looking for has treewidth t and size k. We develop a variation of this method, called Chromatic Coding, where one is interested in just properly coloring the subgraph one is seeking for, as opposed to color coding, where every vertex gets a distinct color. Using this method we develop the first subexponential time algorithms for feedback arc set in tournaments, dense instances of betweenness and minimum quartet inconsistency. In this talk we will introduce the method of Chromatic Coding through the example of feedback arc set in tournaments.

(This is a joint work with Noga Alon and Daniel Lokshtanov.)

---