So, I'll break this post into two questions. Both concern 3-uniform hypergraphs. A 3-uniform hypergraph $H=(V,E)$ consists of a set of vertices $V$ and a set of edges $E$, where each edge $e\in E$ is a set of exactly three vertices from $V$.

1) Here is a well-defined notion of a circuit in a 3-uniform hypergraph. Construct the incidence matrix $B\in\{0,1\}^{|V|\times|E|}$ where entry $B_{ve}=1$ if and only if $v\in e$. So every column of $B$ has exactly three 1s. Then $\text{ker}(B)=\{x\in\{0,1\}^{|E|}:Bx=0\}$ describes the circuit space. In words, a circuit is a subset of edges such that every vertex is included in an even number of edges from the subset.

This seems like a natural generalization of the circuit space for normal graphs, which is also the kernel of the incidence matrix. However, I can't find any work using this definition of circuit space for hypergraphs! Is there a name for this type of hypergraph circuit or some literature I should check out?

2) It is efficient (polynomial time in $|V|$ and $|E|$) to find a basis $\{x_i\}_i$ for the circuit space of a 3-uniform hypergraph since it's just the null space of B. However, can we find a "minimal" circuit basis efficiently? A minimal circuit basis is a circuit basis that uses the minimal number of hyperedges, i.e. minimize, over all bases, $\sum_i|x_i|$ where $|x_i|$ is the Hamming weight of vector $x_i$.

The corresponding problem of finding a minimum circuit basis (often called minimum "cycle" basis because the basis consists of cycles) for normal graphs is efficient -- Horton's algorithm being the first polynomial-time algorithm. Is there any way to find a minimal circuit basis for 3-uniform hypergraphs efficiently? What if we put additional conditions on the 3-uniform graph (such as how there are efficient algorithms for counting spanning trees of certain classes of 3-uniform hypergraphs even if it's hard in general, e.g. arxiv.org/abs/1002.3331)?

Thanks for your help!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.