# Finding a minimal circuit basis for 3-uniform hypergraphs

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)?