\section{Recognition through graph isomorphism}\label{sec:recognition}
We first prove Theorem~\ref{thm:recognition} using the classification
and vertex orbits. We then give an independent recognition proof
using pairs of edges. The input is a connected simple bigraph with at least one edge
and its bipartition supplied. Put $n=|V(H)|$ and $m=|E(H)|$.
For an unpartitioned connected bipartite input, a bipartition is
found in linear time; its two possible orders give the same
cut-percolation decision.

\paragraph{Decision model and running time.}\label{sec:recognition-model}
The \emph{graph-isomorphism problem} asks whether two finite graphs
are isomorphic. A polynomial-time Turing reduction to it is an
algorithm allowed polynomially many such queries on polynomial-sized
graphs, with polynomial computation between queries. Running times
are measured in the binary input length; this is the \emph{bit
complexity} model. Quasipolynomial time is
$n^{(\log n)^{O(1)}}$. A decision problem is in $\mathsf{NP}$ if
every positive instance has a polynomial-length certificate checkable
in polynomial time.

\begin{definition}\label{def:colored-isomorphism}
A \emph{vertex-colored graph} has a specified label at each vertex.
A \emph{colored isomorphism} must preserve these labels as well as
adjacency. Label names are shared between the two input graphs.
\end{definition}

Although there can be many atomic folds, their moved components
belong to a polynomial list determined by the Laplacian.
Colored graph-isomorphism queries test which vertex images are
possible for each component pair. These possible moves determine
the vertex orbits of the fold group. By the classification,
transitivity on each part decides cut-percolation; see
Section~\ref{sec:vertex-recognition}. The edge-pair alternative
in Section~\ref{sec:pair-automaton} uses the same support list.

\subsection{A polynomial list of atomic supports}
We enumerate possible moved component pairs before testing their
isomorphisms.

Let $\mathsf L$ be the combinatorial Laplacian from
\eqref{eq:laplacian} and $P_\theta$ its
orthogonal projector onto the $\theta$-eigenspace. Here $\theta$
ranges over all distinct eigenvalues, not just the Fiedler eigenvalue.
For a vector $z$, its \emph{positive support} is $\{v:z_v>0\}$,
and its \emph{negative support} is $\{v:z_v<0\}$.

\begin{lemma}\label{lem:support-list}
The two moved components of every atomic fold occur as the positive
and negative supports of a vector in the list
\begin{equation}\label{eq:support-list}
 \bigl\{P_\theta(\mathbf e_u-\mathbf e_v):
       \theta\in\spec(\mathsf L),\ u,v\in V(H)\bigr\}.
\end{equation}
The list, including the exact signs of all its coordinates, can be
computed in polynomial bit complexity.
\end{lemma}
\begin{proof}
Let $f$ be atomic, with moved components $C,D$ and fixed set $Z$.
As in Lemma~\ref{lem:atomic}, the Laplacian on the $f$-odd subspace
is the principal Dirichlet matrix $\mathsf L_{C,C}$. Its least
eigenvalue $\mu$ is simple and has a strictly positive eigenvector.
Its odd extension $u$ is an eigenvector of the full Laplacian,
strictly positive on $C$, strictly negative on $D$, and zero on $Z$.
On the entire $\mu$-eigenspace, the $f$-odd subspace is exactly
the line $\RR u$.

Choose $a\in C$ and $b=f(a)$. The vector $\mathbf e_a-\mathbf e_b$
is $f$-odd, and $P_\mu$ commutes with $f$. Therefore
\[
 P_\mu(\mathbf e_a-\mathbf e_b)=c u.
\]
Its scalar product with $u$ is $2u(a)>0$, so $c>0$. This gives
exactly the supports $C,D$ in \eqref{eq:support-list}.

For completeness, the projector computation uses only one real
algebraic number at a time. A real algebraic number is specified by
an integer polynomial and a rational interval isolating one of its
real roots. Let
\[
 \chi(t)=\det(tI-\mathsf L),\qquad
 Q(t)=\chi(t)/\gcd(\chi(t),\chi'(t)).
\]
Here $\chi$ is the characteristic polynomial, $\gcd$ is the greatest
common polynomial divisor, and the prime denotes differentiation.
The polynomial $Q$ is squarefree, meaning that it has no repeated
roots, and has the distinct Laplacian
eigenvalues as its roots. For a root $\theta$, polynomial division
gives $R_\theta(t)=Q(t)/(t-\theta)$, and diagonalizability gives
\begin{equation}\label{eq:projector}
 P_\theta=\frac{R_\theta(\mathsf L)}{Q'(\theta)}.
\end{equation}
Indeed, the right side is one on the $\theta$-eigenspace and zero
on every other eigenspace. Each coordinate in the list is thus a
rational function of one real algebraic number of degree at most
$n$. The binary lengths of characteristic-polynomial coefficients, polynomial
division, and the matrix powers needed in \eqref{eq:projector}
have polynomial bit size. Isolating the real roots and determining the signs of these rational
functions compute all signs in polynomial time
\cite{BPR}. There are at most $n^3$ vectors to inspect.
\end{proof}

For each sign pair $(C,D)$ from the list, put
$Z=V(H)\setminus(C\cup D)$. Retain it only if $C,D$ are nonempty,
both induced subgraphs are connected, and there is no edge between
them. Then $C,D$ are precisely the two components of $H-Z$.
Duplicates can be discarded.

\begin{lemma}\label{lem:boundary-gi}
For a retained support pair, its atomic fold involutions correspond
exactly to isomorphisms $\phi:H[C]\to H[D]$ that preserve the
bipartition and the neighborhood of each vertex in the named set $Z$.
Named means that each boundary vertex retains its identity, rather
than being freely relabeled.
Existence, including at most four prescribed vertex images, is a
vertex-colored graph-isomorphism query of polynomial size.
\end{lemma}
\begin{proof}
Give each vertex $x\in C\cup D$ the color
\[
 \bigl(\text{part of }x,\ N_H(x)\cap Z\bigr).
\]
The second coordinate is the exact subset of named boundary
vertices, encoded as a bit vector. A color-preserving isomorphism
$\phi$ extends to an involution that is $\phi$ on $C$,
$\phi^{-1}$ on $D$, and the identity on $Z$. All internal and
boundary edges are preserved. Its nonfixed components are exactly
$C,D$, so it is atomic. Conversely, an atomic fold with these
supports restricts to such an isomorphism.

To prescribe $\phi(x_i)=y_i$, reject inconsistent or noninjective
prescriptions and assign a fresh matched individual color to each
prescribed pair, retaining its original color. This imposes the
prescribed images without changing the underlying induced graphs.
\end{proof}

\subsection{Recognition from vertex orbits}\label{sec:vertex-recognition}
The classification lets us work with single vertices rather than
pairs of edges. We only need to know which vertices an atom can exchange.

\begin{proposition}\label{prop:vertex-recognition}
Cut-percolation can be recognized using $O(n^5)$ colored
graph-isomorphism queries of polynomial size and polynomial
computation between queries. Each query prescribes just one vertex image.
\end{proposition}
\begin{proof}
Form an undirected graph $Q$ on $V(H)$. For each retained candidate
$(C,D)$ and each $u\in C$, $v\in D$, add the edge $uv$ when
Lemma~\ref{lem:boundary-gi} admits an isomorphism with $\phi(u)=v$.
Every such edge is an actual move of an atomic fold. Conversely,
Lemma~\ref{lem:support-list} includes the support of every atom,
so all its nonfixed vertex moves occur in $Q$.

The components of $Q$ are exactly the orbits of the group generated
by atoms: a path is a sequence of atom moves, and every atom
preserves each component. This group is $\Fold(H)$ by
Lemma~\ref{lem:decomposition}. No edge of $Q$ joins the two parts.
Theorem~\ref{thm:classification} therefore says that $H$ cut-percolates
if and only if $Q[A]$ and $Q[B]$ are both connected.
There are at most $n^3$ candidates and at most $n^2$ prescribed
images for each. All other operations take polynomial time.
\end{proof}

Colored graph isomorphism is polynomial-time reducible to ordinary
graph isomorphism by attaching auxiliary graphs encoding the vertex
labels. This standard reduction preserves isomorphism answers and
has polynomial size. Proposition~\ref{prop:vertex-recognition}
therefore proves the Turing reduction in Theorem~\ref{thm:recognition}.
The quasipolynomial bound follows from the corrected
graph-isomorphism algorithm of Babai \cite{Babai}. At any fixed
maximum degree, the colored queries in Lemma~\ref{lem:boundary-gi}
retain that degree bound, so the colored bounded-degree method of
Luks \cite{Luks} gives polynomial recognition. We use that colored
method directly, without attaching degree-increasing color gadgets.

\paragraph{A short certificate.}
The same classification gives a certificate consisting only of a
few atomic involutions. No folding word needs to be supplied.

\begin{proposition}\label{prop:short-certificate}
A connected $n$-vertex bigraph with at least one edge is
cut-percolating if and only if a list of atomic fold involutions
generates a group transitive on each part. A positive instance
of degrees $d_A,d_B$ has such a list of length at most
$\min\{n-2,d_A+d_B-2\}$ and hence a certificate with
$O(n\min\{n,d_A+d_B\}\log n)$ bits, verifiable in polynomial time.
\end{proposition}
\begin{proof}
For a cut-percolating graph, the group generated by all atoms is
transitive on each part. Start with no selected atoms and hence
$n$ singleton vertex orbits. Suppose the selected atoms generate
more than the two part orbits. Some atom must send a vertex between
two current orbits: otherwise every atom would preserve every
current orbit, contradicting transitivity of the full fold group.
Add this atom. The number of orbits decreases by at least one.
After at most $n-2$ additions, the selected atoms are transitive
on each part. Corollary~\ref{cor:degree-generators} gives the
degree bound by describing the full fold group and its atomic
generators. Conversely, such atoms imply part-transitivity of
$\Fold(H)$ and hence cut-percolation by
Theorem~\ref{thm:classification}.

Record each involution as its vertex permutation. Check that it
is a nonidentity involution preserving parts and adjacency, and
that deleting its fixed vertices leaves exactly two connected
components which it exchanges. These are precisely the atomic
fold conditions. To compute the generated group's vertex orbits,
form the graph with edges $vf(v)$ for every recorded atom $f$ and
vertex $v$. Its components must be exactly $A$ and $B$.
All checks take polynomial time, and the list uses
$O(n\min\{n,d_A+d_B\}\log n)$ bits.
For $n=2$, the empty list certifies $K_{1,1}$.
\end{proof}

The bound $n-2$ is sharp for the star $K_{1,n-1}$: its atoms
are leaf transpositions, and at least $n-2$ of them are needed
to connect the $n-1$ leaves. The certificate test above also shows
that recognizing cut-percolation is in $\mathsf{NP}$.

\subsection{An independent alternative: the pair automaton}\label{sec:pair-automaton}
View each oriented atomic fold as a transformation of the $m$-element
edge set. The set of available transformations may be large; we test its
action on edge pairs without enumerating it. States are unordered
edge pairs $\{e_1,e_2\}$, with diagonal states $\{e,e\}$ allowed.
There are $\binom m2+m$ states.
A transition sends $\{e_1,e_2\}$ to $\{t(e_1),t(e_2)\}$ for one
oriented atomic fold $t$. This directed state graph is the
\emph{pair automaton}. A word gives a path in it, and reaching a
diagonal state means merging the original pair.

\paragraph{A three-edge example.}
On the star $K_{1,3}$, let $t_{12}$ send leaf $u_2$ to $u_1$
and let $t_{13}$ send leaf $u_3$ to $u_1$, fixing all other
vertices. Each map is an oriented atomic fold.
Figure~\ref{fig:pair-automaton} shows their actions on edge pairs:
every pair can be merged into $\{e_1,e_1\}$.
The same two folds also collapse all three edges at once:
$t_{13}\circ t_{12}$ has image $\{e_1\}$.
The pair criterion below makes this conclusion available
without searching for a word on the whole edge set.

\begin{figure}[htbp]
\centering
\input{figures/pair-automaton-drawing}
\caption{Pairwise merging on a three-edge star.
The fold $t_{12}$ sends $u_2$ to $u_1$, and $t_{13}$ sends $u_3$ to $u_1$;
all other vertices are fixed. Every off-diagonal edge-pair state reaches
the diagonal state, where both edges have the same image
(Section~\ref{sec:pair-automaton}). The diagram follows edge images; marked-edge
percolation uses inverse images in the reverse order.}
\label{fig:pair-automaton}
\end{figure}

\paragraph{Testing a transition.}
For a retained pair $(C,D)$, consider the orientation that maps $C$
to $D$ by $\phi$ and fixes $D\cup Z$. To test a transition from
$\{e_1,e_2\}$ to $\{e'_1,e'_2\}$, try both matchings of source
and target edges. Order the endpoints of each edge by their specified
parts. A source endpoint outside $C$ must equal its matched target
endpoint. A source endpoint $x\in C$ must have matched target
$y\in D$, and imposes $\phi(x)=y$. There are at most four such
prescriptions. By Lemma~\ref{lem:boundary-gi}, the transition exists
exactly when one of these colored-isomorphism queries succeeds.
Test the other orientation in the same way.

There are $O(n^3)$ retained candidates and $O(m^4)$ pairs of
automaton states, and a constant number of queries for each choice.
Thus the full directed pair graph is obtained with polynomially
many queries of polynomial size. An identity transition can be
included without a query; it has no effect on reachability.

\paragraph{From pairs to a single word.}
The following elementary automata criterion is standard;
see, for example, \cite{Eppstein}.
\begin{lemma}[Pairwise merging]\label{lem:pairwise}
A finite family of transformations of a nonempty finite set admits a word
whose image is a singleton if and only if every pair can be merged
by some word.
\end{lemma}
\begin{proof}
A collapsing word merges every pair. For the converse, start with
the whole set as the current image. If its size exceeds one,
choose two distinct elements of that image and apply a word merging
them. The image cardinality drops by at least one; applying a
function cannot increase it. Repeat until only one element remains.
\end{proof}

Graph search from all diagonal states along reversed transitions
decides whether every edge pair can be merged. By
Lemma~\ref{lem:decomposition}, oriented atomic folds suffice for
every collapsing word. By Lemma~\ref{lem:pairwise} and
Definition~\ref{def:percolation}, the test is exactly cut-percolation
recognition.

This gives an independent polynomial-time Turing reduction using
$O(n^3m^4)$ colored-isomorphism queries. The preceding vertex-orbit
procedure uses only $O(n^5)$ queries. Both use the same exact
spectral computation and the same boundary-colored induced graphs.

\subsection{A single automorphism-group computation}
Instead of making a separate isomorphism query for each constrained
move, we can compute $\Aut(H)$ once and answer all queries with
permutation-group algorithms.
\begin{proposition}\label{prop:aut-gens}
Given generators of the part-preserving automorphism group of $H$,
cut-percolation can be decided in polynomial time without further
graph-isomorphism queries.
\end{proposition}
\begin{proof}
Let $G=\Aut(H)$ be supplied by generators. For a retained candidate,
compute the pointwise stabilizer
$G_{(Z)}=\{g\in G:gz=z\text{ for every }z\in Z\}$ by permutation-group
algorithms. An element of this stabilizer sending one vertex of $C$
to $D$ interchanges the two components of $H-Z$. Its restriction
$\phi:C\to D$ is the boundary-preserving isomorphism required in
Lemma~\ref{lem:boundary-gi}, even if that element is not an
involution: extend $\phi$ and its inverse separately to obtain the
atomic involution.

Consequently each nontrivial transition test asks whether there is
$g\in G_{(Z)}$ satisfying $g(x_i)=y_i$ for a tuple of at most four
vertices. The set of such $g$ is called the \emph{tuple transporter}. The prescribed
images lie in the opposite component, so a nonempty tuple enforces
the component interchange. If the tuple is empty, the fold fixes
both source edges and the transition is an irrelevant self-loop.
For constant tuple length, tuple transporters and successive point
stabilizers are computed in polynomial time from generators
\cite{Seress}. Equivalently, the \emph{tuple orbit}, the set of all ordered tuples
$(gx_1,\ldots,gx_\ell)$ with $g\in G_{(Z)}$, has at most $n^4$
elements and can be traversed directly.
The spectral list and
the pair-graph search are already polynomial-time operations.
\end{proof}

Generators of $\Aut(H)$ are found with polynomially many colored
graph-isomorphism queries. Successively fix named vertices,
compute the orbit of the next vertex under the pointwise stabilizer,
and find witnesses by further \emph{individualization}, assigning
selected vertices distinct new colors to prescribe their images.
Orbit representatives over these levels generate the group \cite{Seress}.

\subsection{Certificates consisting of folding words}
The reachability argument gives a different certificate, independently
of the classification and Proposition~\ref{prop:short-certificate}.
It bounds the length of a successful folding word, which can also
be checked without graph-isomorphism queries.

\begin{proposition}\label{prop:np}
If $H$ is cut-percolating, it has a collapsing fold word of length
at most $(m-1)\binom m2$. Hence cut-percolation recognition is in
$\mathsf{NP}$.
\end{proposition}
\begin{proof}
A shortest word merging a given pair has length at most
$\binom m2$, since no nondiagonal pair repeats before the first
diagonal is reached. The greedy proof of
Lemma~\ref{lem:pairwise} uses at most $m-1$ such merges. This
gives the claimed word, with the empty word allowed at $m=1$.

A certificate records every fold's involutory vertex permutation
and retained side. In polynomial time one checks nonidentity, part preservation,
adjacency preservation, the fixed set, the exchanged side partition,
and absence of edges between open sides. Applying the recorded
oriented folds to every edge verifies that the final image is a
singleton. The total certificate length is polynomial in the input
size.
\end{proof}