Questions tagged [hypergraphs]
The hypergraphs tag has no usage guidance.
37
questions
1
vote
0
answers
75
views
Tractability of computing generalized hypertreewidth on bounded arity hypergraphs
Generalized hypertreewidth is a generalization of treewidth to hypergraphs. Unlike treewidth, it is not tractable, for a fixed width $k \in \mathbb{N}$, given a hypergraph $H$, to determine if $H$ has ...
- 8,866
2
votes
0
answers
90
views
What kind of solver should I use for this hypergraph problem?
I have to list the solutions to the following hypergraph problem:
There is a set of nodes, linked by edges that are 2-to-1 and bidirectional. The possible directions are either direct: 2 sources and 1 ...
- 8,588
4
votes
0
answers
82
views
Are there classes for that FO-model checking is FPT on hypergraphs?
For graphs, there are many classes that admit FPT-algorithms for model checking of first order logic, e.g. the class of nowhere dense graphs by Grohe et. al.
Are there similar results for ($k$-uniform)...
- 41
2
votes
1
answer
228
views
Which hypergraphs can be simplified by alternatively removing a hyperedge and an isolated vertex?
Let $H = (V, E)$ be a hypergraph, with $V$ the set of vertices and $E \subseteq 2^V$ the set of hyperedges. An elimination sequence on $H$ consists of alternatively removing hyperedges. Specifically, ...
- 8,866
1
vote
0
answers
72
views
Hardness of vertex colouring on hypergraphs with $O(\log n)$ edges
I'm interested to know whether there has been any work done on the problem in the title. For the problem to be meaningful, we would naturally need that the hyperedges must have large ($\omega(1)$) ...
- 331
3
votes
1
answer
162
views
3-dimensional matching variant
In the normal version of the matching problem, we are given a set of vertices $X$, $Y$, and $Z$, each of size $n$, and a set of edges $E\subseteq X\times Y\times Z$. We need to find a matching $M\...
- 33
1
vote
0
answers
49
views
K-Uniform Hypergraph Strong Coloring [closed]
I want to ask if strong coloring of a k-uniform hypergraph using only k colors is NP-Hard or NP-Complete? If you can add a reference this will be helpful.
- 11
4
votes
1
answer
312
views
Shortest path on a hypergraph with no leftovers
In quantum computing, determining the code distance of a stabilizer code is similar to the shortest path problem on a hypergraph. Each node in the graph would be some sort of parity check performed by ...
- 1,498
3
votes
1
answer
172
views
When is hypertree width more useful than generalized hypertree width?
In analysis of CSPs, there are three width notions that are analogous to treewidth: hypertree width (hw), generalized hypertree width (ghw) and fractional hypertree width (fhw). Moreover the ...
- 1,716
5
votes
1
answer
202
views
Expander Graph from Hypergraph
I came up with this problem while thinking about an optimizing compiler.
Let $H$ be a hypergraph. From this we construct a graph $G_H$ as follows the vertices are the hyperedges of the hypergraph. ...
- 153
5
votes
2
answers
200
views
Minimising the root-set of a spanning hyperforest of a hypergraph
I am interested in the complexity of a problem involving spanning hyperforests (a union of hypertrees, which covers all of the vertices) of a $k$-hypergraph. I describe the relevant definitions for ...
- 8,821
3
votes
2
answers
193
views
Reduction of graph chromatic number to hypergraph 2-colorability
I'm following this paper titled "Coverings and colorings of hypergraphs" by Lovasz 1973, which is referenced in Garey and Johnson's Computers and Intractability, for the Set Splitting Problem. In this ...
- 141
3
votes
1
answer
107
views
Almost regular subhypergraph of hypergraph with large minimal degree
I am interested in knowing whether the following conjecture is true or not:
For every $d \geq 1$ there exist constants $\delta,M_0 > 0$ such that the following holds for all $M \geq M_0$.
Let $\...
- 14.2k
2
votes
1
answer
99
views
Counting xyz-graphs in $\mathbb{Z}_n^3$
This is a followup question to: Lower bound on the largest restrained cubic subset
How many distinct xyz-graphs exist in $\mathbb{Z}_n^3$? We denote this number as $C(n)$
This question may be seen ...
- 225
3
votes
2
answers
132
views
Lower bound on the largest restrained cubic subset
Consider an $n \times n \times n$ cube. I would like to consider subsets of points in the cube with the two following constraints:
Each row in the cube (in any of the three directions) has exactly 2 ...
- 225
1
vote
0
answers
148
views
Detecting bridges in Hypergraph S-t Reachability
Is there a fast algorithm to detect possible bridge arcs in hyperpaths from set $S$ of nodes to node $t$ in a hypergraph $G$. That is, given a hypergraph $G$, source nodes $S$, and target node $t$, ...
- 338
1
vote
2
answers
257
views
Reduction from independent set in hypergraphs to independent set in graphs
Let me introduce my notations.
IS-H :
Input : an hypergraph $G=(V,H)$, an integer $k$
Question : is there a (weak) independent set of size $k$, i.e. a set $S \subseteq V$ such that $|S| \ge k$ and ...
- 137
3
votes
1
answer
140
views
What is the recognition complexity of k-uniform k-partite hypergraphs? [duplicate]
We can easily recognize bipartite graphs, but I surprisingly couldn't find anything on the recognition complexity of 3-uniform tripartite hypergraphs, though I'm sure this has been studied.
It's also ...
- 14k
8
votes
2
answers
297
views
Complexity of testing if a hypergraph has generalized hypertreewidth $2$
A hypergraph $H = (V, E)$ consists of a set of vertices $V$ and a set $E$ of hyperedges, i.e., subsets of $V$.
The generalized hypertreewidth (GHW) parameter is a measure of the cyclicity of a ...
- 8,866
6
votes
1
answer
298
views
Complexity of #SAT for monotone DNF formulae whose hypergraph is a hypertree
A monotone DNF on variables $x_1, \ldots, x_n$ is a disjunction of clauses, each clause being a conjunction of some of the $x_1, \ldots, x_n$. The #SAT problem asks, given a monotone DNF $\Phi$, how ...
- 8,866
5
votes
1
answer
1k
views
Is there an approximation algorithm for MAX k DOUBLE SET COVER?
Given a set system $(X,\mathcal S)$, let us say that a subset $\mathcal C\subseteq \mathcal S$ doubly covers a vertex $x$ in $X$ if $x$ is contained in at least two sets of $\mathcal C$. Let us define ...
- 2,143
6
votes
1
answer
303
views
NP-hardness of coloring uniform hypergraphs
Since a $2$-uniform hypergraphs are just graphs. The problem of deciding if $2$-uniform is $k$-colorable for $k=1,2$ is easy, and NP-hard for $k \geq 3$ colors. This is well know and I have seen ...
- 407
4
votes
1
answer
1k
views
Hardness of 3-dimensional matching variant
I am thinking about a variant of 3-dimensional matching. In normal 3d matching, we have three sets of vertices $X$, $Y$ and $Z$, and a set of edges $E \subseteq X \times Y \times Z$. We want to choose ...
- 43
6
votes
1
answer
220
views
Intersection models for weakly chordal graphs?
Due to the apparent unpopularity of my previous posts, I'd like to post a question about graph theory which seems to be a popular topic here :)
Among the many known classes of perfect graphs, there ...
- 1,292
14
votes
4
answers
1k
views
Which properties of planar graphs generalize to higher dimension / hypergraphs?
A planar graph is a graph which can be embedded in the plane, without having crossing edges.
Let $G=(X,E)$ be a $k$-uniform-hypergraph, i.e. an hypergraph such that all its hyperedges have size k.
...
- 9,428
5
votes
1
answer
319
views
Best approximation for a HYPERGRAPH-MAXDICUT problem
Consider a $(c^a,(c+d)^a,1)$-regular directed hypergraph $\mathcal{H}(a)$ on $n^a$ vertices with fixed $n\geq c+d+1$, fixed $c\geq 2$, fixed $d\geq 0$ and variable parameter $a\geq 1$ (meaning every ...
13
votes
4
answers
2k
views
hardness of approximating the chromatic number in graphs with bounded degree
I am looking for hardness results on vertex coloring of graphs with bounded degree.
Given a graph $G(V,E)$, we know that for any $\epsilon>0$, it's hard to approximate $\chi(G)$ within a factor ...
- 271
21
votes
2
answers
3k
views
Recognizing line graphs of hypergraphs
The line graph of a hypergraph $H$ is the (simple) graph $G$ having edges of $H$ as vertices with two edges of $H$ are adjacent in $G$ if they have nonempty intersection.
A hypergraph is an $r$-...
- 2,477
6
votes
0
answers
293
views
k-uniform k-partite hypergraph matching in polynomial time
I have what seems like an elementary question, but google didn't throw up any answers for it. I would appreciate any pointers users here may provide. Please note that I have also asked this question ...
- 779
10
votes
4
answers
767
views
What are the root difficulties in going from graphs to hypergraphs?
There are many examples in combinatorics and computer science where we can analyze a graph-theoretic problem but for the problem's hypergraph analog, our tools are lacking. Why do you think problems ...
- 6,970
23
votes
2
answers
836
views
Are shift-chains two-colorable?
For $A\subset [n]$ denote by $a_i$ the $i^{th}$ smallest element of $A$.
For two $k$-element sets, $A,B\subset [n]$, we say that $A\le B$ if $a_i\le b_i$ for every $i$.
A $k$-uniform hypergraph ${\...
- 14k
10
votes
1
answer
326
views
CSPs with unbounded fractional hypertree width
At SODA 2006, Martin Grohe and D$\acute{\rm a}$niel Marx's paper "Constraint solving via fractional edge covers" (ACM citation) showed that for the class of hypergraphs $H$ with bounded fractional ...
- 5,961
8
votes
1
answer
777
views
Max-clique in line graph of hypergraph
Suppose we have a multigraph (later, a multihypergraph). An edge-clique is a set of edges which all pairwise intersect (have at least one common vertex). Then any edge-clique $C$ in a multigraph ...
- 1,100
4
votes
0
answers
231
views
Follow-up on Nair/Tetali's Correlation Decay Tree for hypergraphs?
I'm wondering if anybody has followed up on Nair/Tetali's correlation decay tree construction for hypergraphs. I didn't find anything relevant in back-citation on google scholar. Interesting question ...
- 4,671
10
votes
2
answers
491
views
Consequences of lower bounds for $\epsilon$-nets on approximation
Many here are probably aware of Alon's recent super-linear lower bounds for $\epsilon$-nets in a natural geometric setting [PDF]. I would like to know what, if anything, such a lower bound implies ...
- 2,583
13
votes
1
answer
435
views
Efficient algorithm for near-optimal edge-colourings of hypergraphs
Graph colouring problems are, already, hard enough for most people. Even so, I'm going to have to be difficult and ask a problem about hypergraph colouring.
Question.
What efficient algorithms are ...
- 8,821
19
votes
4
answers
1k
views
"All-different hypergraph coloring" - known problem?
I am interested in the following problem: Given a set X and subsets X_1, ..., X_n of X, find a coloring of the elements of X with k colors such that the elements in each X_i are all differently ...
- 1,023