Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HYPERGRAPH COLORING:
Reports tagged with hypergraph coloring:
TR13-159 | 20th November 2013
Per Austrin, Venkatesan Guruswami, Johan Håstad

#### $(2+\epsilon)$-SAT is NP-hard

Revisions: 2

We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: Given a CNF-formula where each clause has width $w$ and the guarantee that there exists an assignment satisfying at least $g = \lceil \frac{w}{2}\rceil -1$ literals in each clause, it is NP-hard to find ... more >>>

TR14-043 | 2nd April 2014
Venkatesan Guruswami, Euiwoong Lee

#### Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs

Consider a $K$-uniform hypergraph $H = (V,E)$. A coloring $c : V \rightarrow \{1, 2, \dots, k \}$ with $k$ colors is rainbow if every hyperedge $e$ contains at least one vertex from each color, and is called perfectly balanced when each color appears the same number of times. A ... more >>>

TR15-062 | 15th April 2015
Sangxia Huang

#### $2^{(\log N)^{1/4-o(1)}}$ Hardness for Hypergraph Coloring

Revisions: 2

We show that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with $2^{(\log N)^{1/4-o(1)}}$ colors, where $N$ is the number of vertices. There has been much focus on hardness of hypergraph coloring recently. Guruswami, H{\aa}stad, Harsha, Srinivasan and Varma showed that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with ... more >>>

TR17-080 | 1st May 2017
Joshua Brakensiek, Venkatesan Guruswami

#### The Quest for Strong Inapproximability Results with Perfect Completeness

The Unique Games Conjecture (UGC) has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect ... more >>>

TR17-147 | 3rd October 2017
Venkatesan Guruswami, Rishi Saket

#### Hardness of Rainbow Coloring Hypergraphs

A hypergraph is $k$-rainbow colorable if there exists a vertex coloring using $k$ colors such that each hyperedge has all the $k$ colors. Unlike usual hypergraph coloring, rainbow coloring becomes harder as the number of colors increases. This work studies the rainbow colorability of hypergraphs which are guaranteed to be ... more >>>

TR18-073 | 21st April 2018
Amey Bhangale

#### NP-hardness of coloring $2$-colorable hypergraph with poly-logarithmically many colors

We give very short and simple proofs of the following statements: Given a $2$-colorable $4$-uniform hypergraph on $n$ vertices,

(1) It is NP-hard to color it with $\log^\delta n$ colors for some $\delta>0$.
(2) It is $quasi$-NP-hard to color it with $O\left({\log^{1-o(1)} n}\right)$ colors.

In terms of ... more >>>

TR19-048 | 2nd April 2019
Per Austrin, Amey Bhangale, Aditya Potukuchi

#### Simplified inpproximability of hypergraph coloring via t-agreeing families

We reprove the results on the hardness of approximating hypergraph coloring using a different technique based on bounds on the size of extremal $t$-agreeing families of $[q]^n$. Specifically, using theorems of Frankl-Tokushige [FT99], Ahlswede-Khachatrian [AK98] and Frankl [F76] on the size of such families, we give simple and unified proofs ... more >>>

TR19-094 | 16th July 2019
Venkatesan Guruswami, Sai Sandeep

#### Rainbow coloring hardness via low sensitivity polymorphisms

A $k$-uniform hypergraph is said to be $r$-rainbow colorable if there is an $r$-coloring of its vertices such that every hyperedge intersects all $r$ color classes. Given as input such a hypergraph, finding a $r$-rainbow coloring of it is NP-hard for all $k \ge 3$ and $r \ge 2$. ... more >>>

TR21-007 | 14th January 2021
Sai Sandeep

#### Almost Optimal Inapproximability of Multidimensional Packing Problems

Multidimensional packing problems generalize the classical packing problems such as Bin Packing, Multiprocessor Scheduling by allowing the jobs to be $d$-dimensional vectors. While the approximability of the scalar problems is well understood, there has been a significant gap between the approximation algorithms and the hardness results for the multidimensional variants. ... more >>>

ISSN 1433-8092 | Imprint