Location
Toggle navigation
HOME
INSTITUTE
Mission
Address
Executive Board
Directorate
Scientific Advisory Board
Board of Trustees
NEWS
Press Releases
Awards
Spotlights
Campus Event Calendar
25th Anniversary
Employment
DEPARTMENTS
Algorithms & Complexity
Computer Vision and Machine Learning
Internet Architecture
Computer Grapics
Databases and Information Systems
Research Group Computational Biology
Automation of Logic
PUBLICATIONS
Algorithms & Complexity
Computer Vision and Multimodal Computing
Computer Grapics
Databases and Information Systems
Research Group Computational Biology
Automation of Logic
Research Reports
IMPRS-CS
PEOPLE
SOFTWARE
SERVICES
Joint Administration
- Information Services & Technology
- Building and Technical Support
- Library
- Public Relations
Research Coordination
Equal Opportunities
Care Appointees
Ombudsperson for
Good Scientific Practice
and Doctoral Research
International Office
CS@MPG
CS@SAAR
Computer Science Department,
Saarland University
Max Planck Institute for
Software Systems (MPI-SWS)
German Center for
Artificial Intelligence (DFKI)
Center for Security, Privacy
and Accountability (CISPA)
Graduate School for
Computer Science
Cluster of Excellence (MMCI)
Max Planck Center for Visual
Computing and Communication
Kaiserslautern-Saarbrücken
Computer Science Cluster
IT Incubator
Publications
Home
Intranet
Server
domino.mpi-inf.mpg.de
Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop
Author, Editor
Author(s):
Mütze, Torsten
Rast, Thomas
Spöhel, Reto
dblp
dblp
dblp
Not MPG Author(s):
Mütze, Torsten
Rast, Thomas
Editor(s):
Randall, Dana
dblp
Not MPII Editor(s):
Randall, Dana
BibTeX cite key*:
Spoehel2011
Title, Booktitle
Title*:
Coloring random graphs online without creating monochromatic subgraphs
Booktitle*:
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)
Event, URLs
Conference URL::
http://www.siam.org/meetings/da11/
Downloading URL:
http://www.siam.org/proceedings/soda/2011/SODA11_013_muetzet.pdf
Event Address*:
San Francisco, CA
Language:
English
Event Date*
(no longer used):
Organization:
Association for Computing Machinery (ACM), Society for Industrial and Applied Mathematics (SIAM)
Event Start Date:
23 January 2011
Event End Date:
25 January 2011
Publisher
Name*:
SIAM
URL:
http://www.siam.org/
Address*:
Philadelphia, Pa.
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
January
Pages:
145-158
Year*:
2011
VG Wort Pages:
40
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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})$.
Keywords:
random graph, graph coloring, online algorithm, average-case analysis
Download
Access Level:
Public
Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort
BibTeX Entry:
@INPROCEEDINGS
{
Spoehel2011
,
AUTHOR = {M{\"u}tze, Torsten and Rast, Thomas and Sp{\"o}hel, Reto},
EDITOR = {Randall, Dana},
TITLE = {Coloring random graphs online without creating monochromatic subgraphs},
BOOKTITLE = {Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)},
PUBLISHER = {SIAM},
YEAR = {2011},
ORGANIZATION = {Association for Computing Machinery (ACM), Society for Industrial and Applied Mathematics (SIAM)},
PAGES = {145--158},
ADDRESS = {San Francisco, CA},
MONTH = {January},
}
Entry last modified by Anja Becker, 02/13/2012
Edit History (please click the blue arrow to see the details)
Edit History (please click the blue arrow to see the details)
Editor(s)
[Library]
Created
01/14/2011 07:45:59 PM
Revisions
2.
1.
0.
Editor(s)
Anja Becker
Reto Spöhel
Reto Spöhel
Edit Dates
13.02.2012 14:29:31
14.01.2011 20:17:53
14.01.2011 19:46:00
Attachment Section
Attachment Section