# Tag Info

13

$2$-coloring $s$-uniform hypergraphs is also called Set Splitting, problem [SP4] in Garey-Johnson book. The hardness proof is due to Lovasz in this paper.

10

As David pointed out, Khot's paper, "Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring", Theorem 1.6, says it is NP-hard to color $K$-colorable graph with $2^{\Omega((\log K)^2)}$ colors for graphs with degree at most $2^{2^{(\log K)^2}}$, for sufficiently large constant $K$. In other words, for graphs of ...

9

There is an inapproximability result for coloring bounded degree graphs in Khot's FOCS'01 paper, "Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring" — it's probably weaker than you want, but at least it's in the right direction. He proves that, for a parameter $k$ (assumed to be constant), and for $k$-...

8

As a first remark, your focus seems to be on hypergraphs but I think that most of the literature about embedding hypergraphs prefers to work with simplicial complexes. A good reference on these questions is this paper by Matousek, Tancer and Wagner. Does Fáry's Theorem hold in higher dimension? The answer is no. There are actually 3 different notions ...

8

Oh oh. You want to be very very careful. Contact graphs of convex polytopes in 3d can realize any graph. Surprisingly, the clique can be realized by n polytopes that are n rotated and translated copies of the same polytope (the mind boggles). See this paper: http://www.cs.uiuc.edu/~jeffe/pubs/crum.html This already implies that you can encode pretty nasty ...

8

The best known hardness of approximating the chromatic number of $3$-colorable graphs with bounded maximum degree is due to Venkatesan Guruswami and Sanjeev Khanna, On the Hardness of 4-Coloring a 3-Colorable Graph: There is a constant $\Delta$ such that given a $3$-colorable graph with maximum degree at most $\Delta$, it is NP-hard to color it using ...

6

As the other answer points out, the reduction in the original paper seems to have a bug: $H$ will not be two-colorable unless $G$ is bipartite. I couldn't quite see how to prove the reduction in the other answer works, but here is one that I think does. The vertices of $H$ will be $\{x_{i, v}: i \in [k], v \in V(G)\} \cup \{z\}$. $H$ has an edge $f_v = \{x_{... 5 This result might be helpful: Emden-Weinert, Hougardy, and Kreuter proved that determining whether a graph with maximum degree$\Delta$has a coloring using$ k=\Delta - \sqrt\Delta +1 $colors is NP-complete ($k\ge 3$) T. Emden-Weinert, S. Hougardy, B. Kreuter, Uniquely colourable graphs and the hardness of colouring graphs of large girth, Combin. ... 5 We do not know (to best of my knowledge). 4 (Comment$\rightarrow$Answer) Consider the following algorithms for a hypergraph$(U,\mathcal S)$, with$n=|U|$: For a set$X\subseteq \mathcal S$of sets and a set$A \in X$, define$d_X(A)$as the number of elements in$A$that are double covered by$X$, i.e.$|A \cap \left(\bigcup(X \setminus \{A\})\right|$. Additionally, let$c(X)$denote the number ... 4 Schnyder Theorem states that a graph is planar iff its incidence poset has dimension at most 3. This has been extended by Mendez to arbitrary simplicial complexes (see "Geometric Realization of Simplicial Complexes", Graph Drawing 1999: 323-332). Strangely enough there is a much older paper with a very similar title "The geometric realization of a semi-... 4 Every XP/FPT algorithm parametrized by htw also gives an XP/FPT algorithm parametrized by ghtw (provided that the decomposition is given in the input) since there is a linear relation between ghw and hw [1]:$\mathsf{hw} \leq 3\mathsf{ghw}+1$. So basically, you can see hw as a easier to compute constant approximation of ghw. I am not aware however of ... 3 These subsets of grids, and your graph-theoretic interpretation of them, are studied in my paper The complexity of bendless three-dimensional orthogonal graph drawing. D. Eppstein. J. Graph Algorithms and Applications 17 (1): 35–55, 2013. http://dx.doi.org/10.7155/jgaa.00283 I don't think I included the quadratic example suggested in daniello's answer in ... 3 I don't think this is true as stated, since if$(u,v)$,$(u,w)$,$(v,w)$is a triangle in$G$then clearly there is no way to "two color" the corresponding hyper edges in$H$no matter how many isomorphic copies of$G$you make, yet,$G$may still be$k$-colorable for$k>2$. Here is a different way that may work. Following your same set up, Let$e^{H}_{u,v}...

3

This answer doesn't answer the question about previous work, but it does show the problem is NP-complete. Lemma 1. Finding a shortest $s$-$t$ hyperpath (as defined in the post) in a given hypergraph is NP-complete, even in hypergraphs of hyperedge degree 3. Proof. Clearly the problem is in NP. It is NP-hard by the following reduction from 3D-matching. ...

3

Very important property : tree-width duality. e.g look at : Tree-width of hyper-graphs and surface duality by Frederic Mazoit, The abstract is as follow: In Graph Minors III, Robertson and Seymour write: "It seems that the tree- width of a planar graph and the tree-width of its geometric dual are approximately equal, indeed, we have convinced ...

3

A new paper from Wolfgang Fischl, Georg Gottlob, Reinhard Pichler states that it remains hard even for $k = 2$. I still haven't read it however, I am just providing the link: https://arxiv.org/abs/1611.01090

3

From the standard machinery, we can quickly deduce that there is a quasilinear-time reduction from $\textrm{IS-H}$ to $\textrm{IS}$. (But see below if quasilinear isn't good enough for you.) Recall that $\textrm{3-SAT}$ is hard for $\mathsf{NTIME}[t(n)]$ under reductions that run in time $\tilde{O}(t(n))$, and in particular the resulting 3-CNF formula has ...

2

EDIT (Aug 1): I posted a small report with a more detailed proof on my blog; the reduction idea is the same, but the "gadget" used are better explained (you can also directly download the pdf from here) The problem seems NP-complete and this is a possible reduction from SET COVER. Suppose you have an universe $A$ of $n$ elements: $A = \{a_1,...,a_n\}$, a ...

2

No, the variant is in P: for each element $x_i \in X$ find the set $A_{x_i}$ of triples "reachable" from $x_i$: start with all triples containing $x_i$ $A_{x_i} = \{ (x, y, z) \mid x = x_i \}$ iteratively add to $A_{x_i}$ all triples that share at least one element with all triples already in $A$ check if $E \setminus A_{x_i}$ is a solution and also for ...

2

The problem is NP-hard for $k=3$ already. Indeed, testing if a graph is tripartite (i.e., there exists a partition $V_1 \sqcup V_2 \sqcup V_3$ of its vertex set $V$ such that each edge is between two different subsets) is cleary NP-hard, as it is exactly equivalent to $3$-coloring. Now, I reduce the problem of the question to that problem. Given a graph $G$...

2

Unfortunately the conjecture is wrong (for $d \geq 2$). Here is a counterexample for $d=2$. Suppose that the conjecture (in its graphical formulation) held for some $c,M_0 > 0$. Consider a complete bipartite graph in which the left side has $M^2$ vertices and the right side has $M$ vertices. Thus the left degrees are $M$ and the right degrees are $M^2$. ...

2

Consider the points in the cube as indexed by $(x,y,z) \in \mathbb{Z}_n^3$ and consider the point set $\{(x,y,z) : z = x + y\} \cup \{(x,y,z) : z = x + y + 1\}$. Here addition is done modulo $n$. This point set has $2n^2$ points - for each of the $n^2$ choices of $x$ and $y$ there are exactly two choices of $z$. By the same argument every row (in either ...

2

This is not an answer but is too long for a comment: The graph you care about is called the line graph of the hypergraph. For usual graphs, it is well known that the line graph of an expander graph is also an expander graph (because vertex and edge expansion are equivalent). Whether this holds for hypergraphs probably depends on which of the many notions ...

1

This answer addresses the NP-hardness of the SPANNING SYMMETRIC HYPERFOREST ROOT SET (SSHRS) problem (given an undirected hypergraph $G$ and a number $k$, is there a spanning hyperforest with root set of size at most $k$ in the symmetric directed hypergraph $D_G$). We prove that this problem is hard by reduction from the MAXIMUM UNIQUELY RESTRICTED ...

1

Consider that hamiltonian cycles of the bipartite graph are isomorphic (that is we can always permute the rows amongst themselves and the columns similarly to reach any other hamiltonian cycle). Consider the planes given by $(x,-,-)$ and $(-,y,-)$. Permuting these planes is exactly the same as permuting the rows and columns of the $(-,-,z)$ planes. Thus we ...

1

I am not as convinced as @Andrew Morgan is that this is "fair standard fare", and would also welcome pointers to a citable reduction. In particular, I do not see how to maintain a linear blowup if $k$ depends on $n$, because encoding that the independent set is large enough with linear blowup seems to require a simulation of any threshold gate by a linear-...

1

Observe that the negation of a (monotone) CNF-formula F is a (monotone) DNF G which has the same hypergraph. Moreover #G = 2^n-#F where n is the number of variables of F. Thus, every known (structural) easyness and hardness result for the exact counting on CNF generalizes to DNF. In other words, counting the number of model of beta-acyclic DNF is easy (from ...

1

If I would like to know something about intersection models, the first reference I would check is the "Topics in Intersection Graph Theory" by McKee and McMorris. Theorem 1.5 answers your (combinatorial) question.

1

This is perhaps not entirely satisfactory since you asked for an approximation rather than a hardness result but there is no constant independent of $a$ for which the problem can be approximated to within via an FGLSS-like reduction. Unless P=NP, for every $\epsilon > 0$, there exists $c_0$ such that there is no poly-time $\epsilon$-approximation for ...

Only top voted, non community-wiki answers of a minimum length are eligible