DROPS

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.274

Universal Factor Graphs for Every NP-Hard Boolean CSP

Authors: Shlomo Jozeph

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract

An instance of a Boolean constraint satisfaction problem can be divided into two parts. One part, that we refer to as the factor graph of the instance, specifies for each clause the set of variables that are associated with the clause. The other part, specifies for each of the given clauses what is the constraint that is evaluated on the respective variables. Depending on the allowed choices of constraints, it is known that Boolean constraint satisfaction problems fall into one of two classes, being either NP-hard or in P. This paper shows that every NP-hard Boolean constraint satisfaction problem (except for an easy to characterize set of natural exceptions) has a universal factor graph. That is, for every NP-hard Boolean constraint satisfaction problem, there is a family of at most one factor graph of each size, such that the problem, restricted to instances that have a factor graph from this family, cannot be solved in polynomial time unless NP is contained in P/poly. Moreover, we extend this classification to one that establishes hardness of approximation.

Cite as

Shlomo Jozeph. Universal Factor Graphs for Every NP-Hard Boolean CSP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 274-283, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{jozeph:LIPIcs.APPROX-RANDOM.2014.274,
  author =	{Jozeph, Shlomo},
  title =	{{Universal Factor Graphs for Every NP-Hard Boolean CSP}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{274--283},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.274},
  URN =		{urn:nbn:de:0030-drops-47021},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.274},
  annote =	{Keywords: Hardness of Approximation, Hardness with Preprocessing}
}

Search Results

Documents authored by Jozeph, Shlomo

Universal Factor Graphs for Every NP-Hard Boolean CSP

Abstract

Cite as

Thanks for your feedback!

Could not send message