2
$\begingroup$

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!

$\endgroup$

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.