<p>This answer doesn't answer the question about previous work, but it does show the problem is NP-complete.</p>

<p><strong>Lemma 1.</strong> <em>Finding a shortest <span class="math-container">$s$</span>-<span class="math-container">$t$</span> hyperpath (as defined in the post) in a given hypergraph is NP-complete, even in hypergraphs of hyperedge degree 3.</em></p>

<p><em>Proof.</em> Clearly the problem is in NP.  It is NP-hard by the following reduction from 3D-matching.</p>

<p>Fix an instance of 3D matching -- a set of triples <span class="math-container">$X$</span> from universe <span class="math-container">$U=\{1,2,\ldots,3n\}$</span>.  Given the instance, the reduction outputs the instance of Shortest <span class="math-container">$s$</span>-<span class="math-container">$t$</span> Hyperpath in the hypergraph <span class="math-container">$G=(V,E)$</span> defined as follows.</p>

<p>First create the vertex set <span class="math-container">$V=\{b_0, a_1, b_1, a_2, b_2, a_3, b_3, \ldots, a_{3n}, b_{3n}\}$</span>.  Define the hyperpath source and destination to be <span class="math-container">$s=b_0$</span> and <span class="math-container">$t=b_{3n}$</span>.  Next, add <span class="math-container">$3n$</span> "path" hyperedges <span class="math-container">$$(b_0,a_1,b_1), (b_1,a_2,b_2), (b_2, a_3, b_3), \ldots, (b_{3n-1}, a_{3n}, b_{3n}).$$</span>  Finally, for each triple <span class="math-container">$(i, j, k)$</span> in <span class="math-container">$X$</span>, add hyperedge <span class="math-container">$(a_i, a_j, a_k)$</span>.  This completes the reduction.</p>

<p>We'll show that there is an <span class="math-container">$s$</span>-<span class="math-container">$t$</span> hyperpath of length at most <span class="math-container">$4n$</span> if and only if there is a 3D matching.  </p>

<p>First suppose that there is a 3D matching <span class="math-container">$M$</span> (that is, an <span class="math-container">$n$</span>-subset of <span class="math-container">$X$</span> such that each element in <span class="math-container">$\{1,\ldots,3n\}$</span> occurs in exactly one triple in <span class="math-container">$M$</span>).  Then the <span class="math-container">$3n$</span> "path" hyperedges, together with the <span class="math-container">$n$</span> hyperedges <span class="math-container">$\{(a_i, a_j, a_k) : (i, j, k) \in M\}$</span> form the desired hyperpath.</p>

<p>Conversely, suppose there is such a hyperpath (from <span class="math-container">$b_0$</span> to <span class="math-container">$b_{3n}$</span>).  By induction on the <span class="math-container">$b_i$</span> vertices, each of the <span class="math-container">$3n$</span> path hyperedges <span class="math-container">$(b_i, a_{i+1}, b_{i+1})$</span> must be in the hyperpath.  Then, since each vertex <span class="math-container">$a_1,\ldots,a_{3n}$</span> is in one such path hyperedge, each such vertex must also be in an odd number of other hyperedges in the hyperpath.  Those hyperedges must correspond to triples in <span class="math-container">$X$</span>.  Each such hyperedge contains <span class="math-container">$3$</span> of the <span class="math-container">$a_i$</span> vertices, and the hyperpath has length <span class="math-container">$4n$</span> (or less), so there must be <span class="math-container">$n$</span> such hyperedges, and their corresponding triples must form a 3D matching. <span class="math-container">$~~\Box$</span></p>

<p><s>I suspect that even determining whether there exists any <span class="math-container">$s$</span>-<span class="math-container">$t$</span> hyperpath is also NP-complete.</s></p>

<p>EDIT: I think the <em>existence</em> of an <span class="math-container">$s$</span>-<span class="math-container">$t$</span> hyperpath can be determined in polynomial time by checking feasibility of this set of linear equations over <span class="math-container">$\mathbb{Z}_2$</span>: introduce an indicator variable <span class="math-container">$x_e$</span> for each hyperedge <span class="math-container">$e$</span>, then, for every vertex <span class="math-container">$v$</span> constrain <span class="math-container">$$\sum_{e \ni v} x_e = \begin{cases} 1 &amp; \text{if } v\in\{s,t\} \\ 0 &amp; \text{otherwise}.\end{cases}$$</span></p>

CC BY-SA 4.0
2020-02-18T22:22:45.860Z
2020-02-20T18:24:47.863Z
2020-02-20T18:24:47.863Z
Neal Young
<p>In quantum computing, determining the code distance of a stabilizer code is similar to the shortest path problem on a hypergraph. Each node in the graph would be some sort of parity check performed by the code, and each hyperedge would be a set of parity checks a particular physical error flips. If you construct the graph correctly, paths between certain nodes will correspond to logical errors and the code distance will correspond to a shortest path because the shortest path corresponds to the minimum number of errors.
So that's the motivation for being interested in the shortest path problem on a hypergraph.</p>

<p>I did some preliminary searching for existing algorithms that solve this problem. Unfortunately, it seems that existing research is actually referring to a slightly different problem than what I had in mind. In particular, existing work seems to be happy to pass through edges that touch unrelated nodes an odd number of times. In the context of a code distance calculation this would be a bad idea, because it would cause parity check violations elsewhere in the graph. The "minimum length path" wouldn't successfully get back into the desired codespace.</p>

<p>The variant of the shortest hyperpath problem that I care about is as follows.
Let <span class="math-container">$n$</span> and <span class="math-container">$m$</span> be the start and end nodes.
Let <span class="math-container">$E$</span> be a set of hyperedges.
<span class="math-container">$E$</span> is a hyperpath between <span class="math-container">$n$</span> and <span class="math-container">$m$</span> if <span class="math-container">$n$</span> appears in an <em>odd</em> number of the hyperedges of <span class="math-container">$E$</span>, <span class="math-container">$m$</span> also appears in an odd number of the hyperedges of <span class="math-container">$E$</span>, and all other nodes appear an <em>even</em> number of times in the hyperedges of <span class="math-container">$E$</span>.
I want <span class="math-container">$n$</span> and <span class="math-container">$m$</span> to be the only nodes whose corresponding parity check triggers when the corresponding errors from <span class="math-container">$E$</span> are applied.
The goal is to find the hyperpath with the minimum number of hyperedges.</p>

<p>Has there been previous work on this problem? Note that I'm mostly interested in the case where the hyperedge degree is bounded (e.g. the error graph of the surface code typically has no hyperedges with degree larger than 4, even with circuit level noise and two qubit gate errors).</p>

CC BY-SA 4.0
2020-02-18T20:23:12.217Z
So if the hypergraph contains degree-1 edges $(n)$ and $(m)$, then those two edges by themselves form a hyperpath $E=\{(n), (m)\}$ from $n$ to $m$?
Neal Young
CC BY-SA 4.0
2020-02-18T20:52:49.410Z
@NealYoung Yes. Although in practice the graph would have been prepared to avoid solutions of that type, since they represent returning to the original codeword instead of a logical error.
Craig Gidney
<shortest-path><hypergraphs>
Shortest path on a hypergraph with no leftovers
Craig Gidney
# Shortest path on a hypergraph with no leftovers

(Asked by: username_0 on 2020-02-18)

In quantum computing, determining the code distance of a stabilizer code is similar to the shortest path problem on a hypergraph. Each node in the graph would be some sort of parity check performed by the code, and each hyperedge would be a set of parity checks a particular physical error flips. If you construct the graph correctly, paths between certain nodes will correspond to logical errors and the code distance will correspond to a shortest path because the shortest path corresponds to the minimum number of errors.
So that's the motivation for being interested in the shortest path problem on a hypergraph.

I did some preliminary searching for existing algorithms that solve this problem. Unfortunately, it seems that existing research is actually referring to a slightly different problem than what I had in mind. In particular, existing work seems to be happy to pass through edges that touch unrelated nodes an odd number of times. In the context of a code distance calculation this would be a bad idea, because it would cause parity check violations elsewhere in the graph. The "minimum length path" wouldn't successfully get back into the desired codespace.

The variant of the shortest hyperpath problem that I care about is as follows.
Let $n$ and $m$ be the start and end nodes.
Let $E$ be a set of hyperedges.
$E$ is a hyperpath between $n$ and $m$ if $n$ appears in an *odd* number of the hyperedges of $E$, $m$ also appears in an odd number of the hyperedges of $E$, and all other nodes appear an *even* number of times in the hyperedges of $E$.
I want $n$ and $m$ to be the only nodes whose corresponding parity check triggers when the corresponding errors from $E$ are applied.
The goal is to find the hyperpath with the minimum number of hyperedges.

Has there been previous work on this problem? Note that I'm mostly interested in the case where the hyperedge degree is bounded (e.g. the error graph of the surface code typically has no hyperedges with degree larger than 4, even with circuit level noise and two qubit gate errors).

**Tags:** shortest-path, hypergraphs
> **Comments:**
> **username_1**: So if the hypergraph contains degree-1 edges $(n)$ and $(m)$, then those two edges by themselves form a hyperpath $E=\{(n), (m)\}$ from $n$ to $m$?  
> **username_0**: @NealYoung Yes. Although in practice the graph would have been prepared to avoid solutions of that type, since they represent returning to the original codeword instead of a logical error.  

---

## 1 answers

### Answer by username_1 on 2020-02-18. Score: 4 | Accepted answer

This answer doesn't answer the question about previous work, but it does show the problem is NP-complete.

**Lemma 1.** *Finding a shortest $s$-$t$ hyperpath (as defined in the post) in a given hypergraph is NP-complete, even in hypergraphs of hyperedge degree 3.*

*Proof.* Clearly the problem is in NP. It is NP-hard by the following reduction from 3D-matching.

Fix an instance of 3D matching -- a set of triples $X$ from universe $U=\{1,2,\ldots,3n\}$. Given the instance, the reduction outputs the instance of Shortest $s$-$t$ Hyperpath in the hypergraph $G=(V,E)$ defined as follows.

First create the vertex set $V=\{b\_0, a\_1, b\_1, a\_2, b\_2, a\_3, b\_3, \ldots, a\_{3n}, b\_{3n}\}$. Define the hyperpath source and destination to be $s=b\_0$ and $t=b\_{3n}$. Next, add $3n$ "path" hyperedges $$(b\_0,a\_1,b\_1), (b\_1,a\_2,b\_2), (b\_2, a\_3, b\_3), \ldots, (b\_{3n-1}, a\_{3n}, b\_{3n}).$$ Finally, for each triple $(i, j, k)$ in $X$, add hyperedge $(a\_i, a\_j, a\_k)$. This completes the reduction.

We'll show that there is an $s$-$t$ hyperpath of length at most $4n$ if and only if there is a 3D matching.

First suppose that there is a 3D matching $M$ (that is, an $n$-subset of $X$ such that each element in $\{1,\ldots,3n\}$ occurs in exactly one triple in $M$). Then the $3n$ "path" hyperedges, together with the $n$ hyperedges $\{(a\_i, a\_j, a\_k) : (i, j, k) \in M\}$ form the desired hyperpath.

Conversely, suppose there is such a hyperpath (from $b\_0$ to $b\_{3n}$). By induction on the $b\_i$ vertices, each of the $3n$ path hyperedges $(b\_i, a\_{i+1}, b\_{i+1})$ must be in the hyperpath. Then, since each vertex $a\_1,\ldots,a\_{3n}$ is in one such path hyperedge, each such vertex must also be in an odd number of other hyperedges in the hyperpath. Those hyperedges must correspond to triples in $X$. Each such hyperedge contains $3$ of the $a\_i$ vertices, and the hyperpath has length $4n$ (or less), so there must be $n$ such hyperedges, and their corresponding triples must form a 3D matching. $~~\Box$

~~I suspect that even determining whether there exists any $s$-$t$ hyperpath is also NP-complete.~~

EDIT: I think the *existence* of an $s$-$t$ hyperpath can be determined in polynomial time by checking feasibility of this set of linear equations over $\mathbb{Z}\_2$: introduce an indicator variable $x\_e$ for each hyperedge $e$, then, for every vertex $v$ constrain $$\sum\_{e \ni v} x\_e = \begin{cases} 1 & \text{if } v\in\{s,t\} \\ 0 & \text{otherwise}.\end{cases}$$


---

