Questions tagged [hypergraphs]
The hypergraphs tag has no usage guidance.
7
questions with no upvoted or accepted answers
6
votes
0
answers
298
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
84
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,701
2
votes
0
answers
99
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,843
1
vote
0
answers
155
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
0
votes
0
answers
132
views
Error in TAOCP 4a on the bipartite graph constructed from a hypergraph
The first sentence on page 33 of Donald Knuth's The Art of Computer Programming (TAOCP) Vol. 4a reads:
Furthermore, a hypergraph is equivalent to a bipartite graph with vertex set $V \cup E$ and ...
0
votes
0
answers
47
views
Is hypergraph reachability definable in MSO?
Let $(A,E)$ be a directed 2-uniform hypergraph and $E$ the corresponding binary relation such that $(X,Y) \in E$ iff there is a hyperedge from $X$ to $Y$.
We say that there is a path from $X_1$ to $...
