# 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.

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

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 ...

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 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 :$\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 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 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

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 ...

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

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

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 ...

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

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

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

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

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

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