Questions tagged [hypergraphs]
The hypergraphs tag has no usage guidance.
7
questions with no upvoted or accepted answers
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
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
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,681
2
votes
0
answers
91
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,598
1
vote
0
answers
79
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,896
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)$) ...
- 341
1
vote
0
answers
149
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