This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
en:group:seminars:20111005 [2011/09/15 13:28] maatouk |
en:group:seminars:20111005 [2016/06/23 11:26] (current) |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ---- dataentry seminar ---- | ---- dataentry seminar ---- | ||
| date_dt : 2011-10-05 | date_dt : 2011-10-05 | ||
| - | title : TBA | + | title : Coloring random graphs online without creating monochromatic subgraphs |
| speaker : Dr. Reto Spöhel | speaker : Dr. Reto Spöhel | ||
| affiliation : Max Planck Institute for Informatics | affiliation : Max Planck Institute for Informatics | ||
| Line 13: | Line 13: | ||
| ==== abstract ==== | ==== abstract ==== | ||
| - | TBA | + | |
| + | Consider the following generalized notion of graph coloring: a coloring of | ||
| + | the vertices of a graph G is \emph{valid} w.r.t. some given graph F if | ||
| + | there is no copy of F in G whose vertices all receive the same color. We | ||
| + | study the problem of computing valid colorings of the binomial random | ||
| + | graph G_{n,p} on n vertices with edge probability p=p(n) in the following | ||
| + | online setting: the vertices of an initially hidden instance of G_{n,p} | ||
| + | are revealed one by one (together with all edges leading to previously | ||
| + | revealed vertices) and have to be colored immediately and irrevocably with | ||
| + | one of r available colors. | ||
| + | It is known that for any fixed graph F and any fixed integer r\geq 2 this | ||
| + | problem has a threshold p_0(F,r,n) in the following sense: For any | ||
| + | function p(n) = o(p_0) there is a strategy that a.a.s. (asymptotically | ||
| + | almost surely, i.e., with probability tending to 1 as n tends to infinity) | ||
| + | finds an r-coloring of G_{n,p} that is valid w.r.t. F online, and for any | ||
| + | function p(n)=\omega(p_0) \emph{any} online strategy will a.a.s. fail to | ||
| + | do so. | ||
| + | |||
| + | We establish a general correspondence between this probabilistic problem | ||
| + | and a deterministic two-player game in which the random process is | ||
| + | replaced by an adversary that is subject to certain restrictions inherited | ||
| + | from the random setting. This characterization allows us to compute, for | ||
| + | any F and r, a value \gamma=\gamma(F,r) such that the threshold of the | ||
| + | probabilistic problem is given by p_0(F,r,n)=n^{-\gamma}. Our approach | ||
| + | yields polynomial-time coloring algorithms that a.a.s. find valid | ||
| + | colorings of G_{n,p} online in the entire regime below the respective | ||
| + | thresholds, i.e., for any p(n) = o(n^{-\gamma}). | ||
| + | |||
| + | Joint work with Torsten Mütze und Thomas Rast (both ETH Zurich); appeared | ||
| + | at SODA '11. | ||