License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.80
URN: urn:nbn:de:0030-drops-62056
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6205/
Go to the corresponding LIPIcs Volume Portal

Bennett, Huck ; Reichman, Daniel ; Shinkar, Igor

On Percolation and NP-Hardness

pdf-format:
LIPIcs-ICALP-2016-80.pdf (0.6 MB)

Abstract

The edge-percolation and vertex-percolation random graph models start with an arbitrary graph G, and randomly delete edges or vertices of G with some fixed probability. We study the computational hardness of problems whose inputs are obtained by applying percolation to worst-case instances. Specifically, we show that a number of classical N P-hard graph problems remain essentially as hard on percolated instances as they are in the worst-case (assuming NP !subseteq BPP). We also prove hardness results for other NP-hard problems such as Constraint Satisfaction Problems, where random deletions are applied to clauses or variables.

We focus on proving the hardness of the Maximum Independent Set problem and the Graph Coloring problem on percolated instances. To show this we establish the robustness of the corresponding parameters alpha(.) and Chi(.) to percolation, which may be of independent interest. Given a graph G, let G' be the graph obtained by randomly deleting edges of G. We show that if alpha(G) is small, then alpha(G') remains small with probability at least 0.99. Similarly, we show that if Chi(G) is large, then Chi(G') remains large with probability at least 0.99.

BibTeX - Entry

@InProceedings{bennett_et_al:LIPIcs:2016:6205,
  author =	{Huck Bennett and Daniel Reichman and Igor Shinkar},
  title =	{{On Percolation and NP-Hardness}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{80:1--80:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6205},
  URN =		{urn:nbn:de:0030-drops-62056},
  doi =		{10.4230/LIPIcs.ICALP.2016.80},
  annote =	{Keywords: percolation, NP-hardness, random subgraphs, chromatic number}
}

Keywords: percolation, NP-hardness, random subgraphs, chromatic number
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI