English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Coloring Random Graphs Online Without Creating Monochromatic Subgraphs

Mütze, T., Rast, T., & Spöhel, R. (2011). Coloring Random Graphs Online Without Creating Monochromatic Subgraphs. In D. Randall (Ed.), Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 145-158). Philadelphia, PA: SIAM. doi:10.1137/1.9781611973082.13.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0010-1203-0 Version Permalink: http://hdl.handle.net/11858/00-001M-0000-0024-0526-D
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Mütze, Torsten1, Author
Rast, Thomas1, Author
Spöhel, Reto2, Author              
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: Consider the following generalized notion of graph coloring: a coloring of the vertices of a graph~$G$ is \emph{valid} \wrt 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~$\Gnp$ on~$n$ vertices with edge probability~$p=p(n)$ in the following online setting: the vertices of an initially hidden instance of $\Gnp$ 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 \aas (asymptotically almost surely, i.e., with probability tending to 1 as $n$ tends to infinity) finds an $r$-coloring of $\Gnp$ that is valid \wrt $F$ online, and for any function~$p(n)=\omega(p_0)$ \emph{any} online strategy will \aas fail to do so. In this work 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 \aas find valid colorings of $\Gnp$ online in the entire regime below the respective thresholds, i.e., for any $p(n) = o(n^{-\gamma})$.

Details

show
hide
Language(s): eng - English
 Dates: 20112011
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 618654
DOI: 10.1137/1.9781611973082.13
Other: Local-ID: C1256428004B93B8-756C48B4DC6ED7CDC12578180067169E-Spoehel2011
 Degree: -

Event

show
hide
Title: Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms
Place of Event: San Francisco, CA
Start-/End Date: 2011-01-23 - 2011-01-25

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms
  Abbreviation : SODA 2011
Source Genre: Proceedings
 Creator(s):
Randall, Dana1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Philadelphia, PA : SIAM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 145 - 158 Identifier: -