Proof. Let \(V\) be the vertex set of \(G_1\), \(G_2\) and \(G_3\). By definition, both \(G_1\) and \(G_2\) are vertex-minors of some graph \(\widehat{G}_{1,2}\) whose vertex set consists of \(V\) and \(d(G_1,G_2)\) additional vertices. By locally complementing, we may assume that \(G_2\) is an induced subgraph of \(\widehat{G}_{1,2}\). Similarly, both \(G_2\) and \(G_3\) are vertex-minors of some graph \(\widehat{G}_{2,3}\) whose vertex set consists of \(V\) and \(d(G_2,G_3)\) additional vertices. Again we may assume that \(G_2\) is an induced subgraph of \(\widehat{G}_{2,3}\). Now let \(\widehat{G}_{1,3}\) be the union of \(\widehat{G}_{1,2}\) and \(\widehat{G}_{2,3}\). That is, on \(V\), the graph \(\widehat{G}_{1,2}\) equals \(G_2\), plus it has \(d(G_1,G_2)+d(G_2,G_3)\) additional vertices whose adjacencies are given by \(\widehat{G}_{1,2}\) and \(\widehat{G}_{2,3}\), respectively. Then \(\widehat{G}_{1,3}\) contains both \(G_1\) and \(G_3\) as vertex-minors. ◻

Proof. First let \(G'\) be a rank-\(k\) perturbation of \(G\). Then by [10], \(G'\) is also a \(k\)-perturbation of \(G\). So the \(k\)-ancilla-integrity of \(G\) (or equivalently of \(\ket{G}\)) is at most the \(k\)-rank-integrity of \(G\). Now let \(G'\) be a \(k\)-perturbation of \(G\). By [10], \(G'\) is locally equivalent to a graph which is a rank-\(2t\) perturbation of \(G\). Since the maximum component size is invariant under local complementation (or, in the quantum picture, by one-qubit gates), it follows that the \(2k\)-rank-integrity is at most the \(k\)-ancilla integrity. ◻

Proof. Let \(m = \max(k+2,t)\). Let \(G\) be a complete \(m\)-partite graph, where each vertex set in the partition contains exactly \(k+1\) vertices; so \(G\) is of order \(m (k+1)\). An analysis of the orbit of \(G\) by local complementations is given in [10]. One can check that deleting \(k\) vertices from any locally equivalent graph leads to a graph with a connected component containing at least \(m\) vertices.

Conversely, adding a vertex \(a\) to \(G\) connected to every vertex, then locally complementing on \(a\), then deleting \(a\), maps \(G\) to a disjoint union of \(m\) complete graphs with \(k+1\) vertices. ◻

Proof. Let \(X \subseteq V(G)\) be a set of size at most \(k\). Let \(G'\) be the subgraph of \(G\) which is obtained by removing all edges incident to a vertex in \(X\). Then, all the nonzero entries of the adjacency matrix of \(G+G'\) are contained in at most \(k\) rows and \(k\) columns. Thus, this matrix has rank at most \(2k\). Moreover, the components of the graph \(G'\) are exactly the components of \(G-X\) and the vertices of \(X\) (each of which is an isolated vertex). Thus, all components of \(G'\) have size at most the \(k\)-order-integrity of \(G\), as desired. ◻

Proof. For this proof we use some definitions that are introduced in 2.3. Let \(G^*\) be a (looped) graph of rank at most \(k\) which minimizes the maximum component size of \(G+G^*\). Let \({\mathcal{P}}^*\) be the type partition of \(G^*\), and note that \(|{\mathcal{P}}^*| \leq 2^k\) (since a rank-\(k\) binary matrix has at most \(2^k\) columns; see [obs:rank-quotient]).

For \(P, P' \in {\mathcal{P}}^*\) (not necessarily distinct), let \(H(P, P')\) be the graph on vertex set \(P \cup P'\) with an edge between \(v \in P\) and \(v' \in P'\) if and only if \(v\) and \(v'\) are adjacent in \({G}^*\) and in different components of \(G+{G}^*\). (So first we restrict our attention to what happens between the components of \(G+{G}^*\), and then we include an edge if that adjacency is “flipped”.) If \(vv'\) is an edge of \(H(P, P')\), then \(v\) and \(v'\) are adjacent in \({G}^*\) but not in \(G + {G}^*\) since they belong to different components, so they are also adjacent in \(G\). Thus, \(H(P, P')\) is a subgraph of \(G\) so contains no \(K_{t, t}\)-subgraph. Next we show how to find a small vertex cover of each graph \(H(P, P')\); then we put all of these covers together to obtain a set \(X\) so that every component of \(G-X\) is small.

Proof of [cl:vertex-cover].  If \(|P| \leq 3t\) or \(|P'| \leq 3t\) then we are done, so assume that \(|P|, |P'| > 3t\). Let \(V_1, \ldots, V_r\) denote the vertex sets of the components of \(G + {G}^*\), and write \(H=H(P, P')\). Since every pair of vertices in \(P\) and every pair of vertices in \(P'\) are twins in \(G^*\), the sets \(P\) and \(P'\) are either complete or anticomplete in \({G}^*\). (See 4.) If they are anticomplete then \(H\) is edgeless and we are done, so suppose that \(P\) and \(P'\) are complete in \({G}^*\).

Then, for all \(i \neq j \in [r]\), \(P \cap V_i\) and \(P' \cap V_j\) form a complete bipartite graph in \(H\). Let \(I \subseteq [r]\) be inclusion-wise minimal such that \(|P \cap \bigcup_{i \in I}V_i| \geq t\). Then, \(|P' \cap \bigcup_{j \notin I}V_j| < t\) since \(H\) is \(K_{t, t}\)-free. Since \(|P'| \geq 3t\), this implies \(|P' \cap \bigcup_{i \in I}V_i| \geq 2t\). In turn, this implies that \(|P \cap \bigcup_{j \notin I}V_j| < t\) since \(H\) is \(K_{t, t}\)-free.

Suppose first that \(I = \{i\}\) for some \(i \in [r]\). Then, \((P \cup P') \cap \bigcup_{j \notin I}V_j\) is a vertex cover of \(H\) of size at most \(2t\). So, suppose now that \(|I| \geq 2\). By the minimality of \(I\), we have \(|P \cap \bigcup_{i \in I}V_i| \leq 2t\). Then, \(|P| \leq 3t\) and we are done.

For all \(P, P' \in {\mathcal{P}}^*\), let \(X(P, P')\) be a vertex cover of \(H(P, P')\) of size at most \(3t\). Let \(X\) be the union of all such sets and note that \(|X| \leq 2^{2k} \cdot 3t\). To complete the proof, we now argue that every component of \(G-X\) is contained in a component of \(G + {G}^*\). For this, it suffices to show that any two adjacent vertices in \(G-X\) lie in the same component of \(G+{G}^*\). So, let \(v, v' \in V(G) \setminus X\) be adjacent in \(G\). Let \(P\) (resp. \(P'\)) be the part of \({\mathcal{P}}^*\) that contains \(v\) (resp. \(v'\)). Since \(v\) and \(v'\) are not in the chosen cover \(X(P, P')\) of \(H(P,P')\), either they are not adjacent in \({G}^*\) or they are in the same component of \(G+{G}^*\). Since they are adjacent in \(G\), if they are not adjacent in \({G}^*\) then they are in the same component of \(G+{G}^*\). Thus, in any case they lie in the same component of \(G+{G}^*\), which concludes the proof. ◻

Proof. Let \(P_1, P_2 \in \mathcal{P}\) and let \(u_1, u'_1 \in P_1\) and \(u_2, u'_2 \in P_2\). Since \(u_1 \sim u'_1\) and \(u_2 \sim u'_2\), we have \[u_1u_2 \in E(G) \iff u'_1u_2 \in E(G) \iff u'_1u'_2 \in E(G).\] This shows that \(P_1\) and \(P_2\) are either complete or anticomplete in \(G\). ◻

Proof. By contradiction, suppose that every \(v \in V(G)\) that is adjacent to exactly one of \(u, u'\) in \(\widehat{G}\) belongs to \(V(K)\). Consider the graph \(\widetilde{G}\) on vertex set \(V\) obtained from \(\widehat{G}\) by setting the neighborhood of all vertices in \(P' \cap V(K)\) to the neighborhood of \(u\) in \(\widehat{G}\) (equivalently, this amounts to moving them from \(P'\) to \(P\)). Then, the only differences between \(G+\widehat{G}\) and \(G+\widetilde{G}\) are edges inside \(V(K)\), so every component of \(G+\widehat{G}\) is the union of components of \(G+\widetilde{G}\). Note that the quotient graph \(\widetilde{G}/\widetilde{\mathcal{P}}\) is an induced subgraph of the quotient graph of \(\widehat{G}/\widehat{\mathcal{P}}\) (with the obvious notations), so \(\widetilde{G}\) has rank at most \(k\) by [obs:rank-quotient]. Since the partition into components of \(G+\widehat{G}\) minimizes the maximum component size, it follows that \(G+\widehat{G}\) and \(G+\widetilde{G}\) have the same maximum component size. Since among all such graphs, \(G+\widehat{G}\) has the maximum number of components, it follows that \(G+\widehat{G}\) and \(G+\widetilde{G}\) have the same components. Then, \(\widetilde{G}\) has smaller score than \(\widehat{G}\) with respect to \(G\), a contradiction to \(\widehat{G}\) being \(k\)-optimal. ◻

Proof. Suppose that we are given an instance \((G, k)\) of rank integrity. For the rest of this proof, we fix a looped graph \(G^*\) that is \(k\)-optimal for \(G\) and a typical system of representatives \((t^*, p^*, \mathcal{R}^*, R^*, G^*/\mathcal{P}^*)\) for \((G, G^*)\). We denote by \(\mathcal{K}^* = \{K_1, \ldots, K_{t^*}\}\) the typical set of components of \(G+G^*\) that corresponds to this typical system of representatives and by \(K_1, \ldots, K_{c^*}\) the components of \(G+G^*\). Note that \(t^*\) is the number of components in the typical set of components \(\mathcal{K}^*\), while \(c^*\) is the number of components of \(G+G^*\). We also write \(\mathcal{P}^* = \{P_1, \ldots, P_{p^*}\}\), where \(p^*\) is the number of parts of \(\mathcal{P}^*\). Our goal is to reconstruct the partition into components of \(G+G^*\) along with the graph \(G^*\). For this, we want to start from the typical system of representatives \((t^*, p^*, \mathcal{R}^*, R^*, G^*/\mathcal{P}^*)\). Thus, the first step of the algorithm is to guess:

• an integer \(t \leq 3 \cdot 2^{2^k}\),

• an integer \(p \leq 2^k\),

• a set \(\mathcal{R} \subseteq [t] \times [p]\) such that for every \(j \in [p]\), there exists \(i \in [t]\) such that \((i, j) \in \mathcal{R}\),

• a family \(R = (v_{i, j})_{(i, j) \in \mathcal{R}}\) of vertices of \(G\), and

• a looped graph \(H\) on vertex set \([p]\) of rank at most \(k\) that does not contain twins.

Note that \((t^*, p^*, \mathcal{R}^*, R^*, G^*/\mathcal{P}^*)\) indeed satisfies all these conditions.

Throughout the proof, we will establish properties regarding \((t^*, p^*, \mathcal{R}^*, R^*, G^*/\mathcal{P}^*)\) for \((G, G^*)\). The algorithm will verify that the guess \((t, p, \mathcal{R}, R, H)\) satisfies these properties, and abort if it is not the case.

Consistency.

We start with a first property. We say that \(R\) is consistent with \(H\) if for all \(v_{i, j}, v_{i', j'} \in R\) with \(i \neq i'\), we have \(v_{i, j}v_{i', j'} \in E(G) \iff jj' \in E(H)\).

Proof of [cl:consistent].  Let \(v_{i, j}, v_{i', j'} \in R^*\) with \(i \neq i'\). Since \(v_{i, j}\) and \(v_{i', j'}\) belong to different components of \(G+G^*\), they are not adjacent in \(G+G^*\). Therefore, \(v_{i, j}v_{i', j'} \in E(G) \iff v_{i, j}v_{i', j'} \in E(G^*) \iff jj' \in E(G^*/\mathcal{P}^*)\).

The algorithm verifies that \(R\) is consistent with \(H\), and aborts if it is not the case. We then start trying to construct the type partition \(\mathcal{P}^*\) of \(G^*\) and the partition into components of \(G+G^*\). We begin with an observation.

Let \(v \in V(G)\) and \(v_{i, j} \in R^*\) and suppose that \(v\) and \(v_{i, j}\) belong to the same component \(K_i\) of \(G+G^*\) and to the same part \(P_j\) of the type partition \(\mathcal{P}^*\) of \(G^*\). Then, \(v\) and \(v_{i, j}\) have the same neighborhood in \(G^*\), and they are not adjacent in \(G+G^*\) to any vertex \(v_{i', j'}\) for \(i' \neq i\). Thus, \(v\) and \(v_{i, j}\) have the same neighborhood in \(G\) on all the vertices \(v_{i', j'} \in R^*\) with \(i' \neq i\).

Compatibility.

With this idea in mind, we say that a vertex \(v \in V(G)\) is compatible with a vertex \(v_{i, j} \in R\) if \(v\) and \(v_{i, j}\) have the same neighborhood in \(G\) on all the vertices \(v_{i', j'} \in R\) with \(i' \neq i\). We then define the compatibility function \(f : V(G) \to 2^R\) as follows:

• If \(v \in R\) then \(f(v) = \{v\}\),

• If \(v \notin R\) then \(f(v) = \{v_{i, j} \in R : \text{v is compatible with v_{i, j}}\}\).

We denote by \(f^*\) the compatibility function corresponding to \((t^*, p^*, \mathcal{R}^*, R^*, G^*/\mathcal{P}^*)\). Intuitively, for every vertex \(u \in V(G)\), we should think of \(f(u)\) as describing the parts of \(\mathcal{P}^*\) and the components of \(G+G^*\) (more precisely, those among \(K_1, \ldots, K_{t^*}\)) to which \(u\) can belong.

Faithfulness.

We say that \(f\) is faithful if \(|f(u)| \geq 1\) for every \(u \in V(G)\). This means that for every \(u \in V(G)\), there is some component \(K_i \in \mathcal{K}^*\) with and some part \(P_j\) of \(\mathcal{P}^*\) where \(u\) can go.

Proof of [cl:f42-faithful].  Suppose first that \(i_u \in [t^*]\), so there is a vertex \(v_{i_u, j_u} \in R^*\). In this case, we already argued that \(v\) and \(v_{i_u, j_u}\) are compatible.

Suppose now that \(i_u \notin [t^*]\) and let \(i \in [t^*]\) such that \((i, j_u) \in \mathcal{R}^*\). We show that \(v\) is compatible with \(v_{i, j_u}\). Let \(i' \neq i \in [t^*]\) and \(j' \in [p^*]\) such that \(v_{i', j'} \in R^*\). Observe that \(K_{i_u} \neq K_{i'}\) since \(i_u \notin [t^*]\). Thus, both \(v\) and \(v_{i, j_u}\) are not adjacent to \(v_{i', j'}\) in \(G+G^*\). Since \(v, v_{i, j_u} \in P_{j_u}\), \(v\) and \(v_{i, j_u}\) have the same neighborhood in \(G^*\). Thus, \(v\) and \(v_{i, j_u}\) have the same adjacency in \(G\) to \(v_{i', j'}\). This proves that \(v\) and \(v_{i, j_u}\) are compatible.

The fact that \(f^*\) is faithful follows immediately, since there exists \(i \in [t^*]\) such that \((i, j_u) \in \mathcal{R}^*\).

Functionality.

We say that \(f\) is functional if for every \(u \in V(G)\), for every \(i \in [t]\), there is at most one \(j \in [p]\) such that \(v_{i, j} \in f(u)\). Informally, this means that \(v\) cannot be compatible with two representatives that live in the same component of \(G^*\).

Proof of [f42-functional].  Let \(u \in V(G)\), \(i \in [t^*]\) and \(j \neq j' \in [p^*]\) such that \(v_{i, j}, v_{i, j'} \in R^*\). By 6, there exists \(w \in V(G)\) that does not belong to \(K_i\) and that is adjacent to exactly one of \(v_{i, j}, v_{i, j'}\) in \(G^*\). Let \(j_0 \in [p^*]\) such that \(w \in P_{j_0}\). Since \(\mathcal{K}^*\) is a typical set of components of \(G+G^*\), there exists \(i_0 \neq i \in [t^*]\) such that \((i_0, j_0) \in \mathcal{R}^*\), so there is a vertex \(v_{i_0, j_0} \in R^*\). By 4, it follows that \(v_{i_0, j_0}\) is adjacent to exactly one of \(v_{i, j}, v_{i, j'}\) in \(G^*\). Since \(i_0 \neq i\), \(v_{i_0, j_0}\) is adjacent to neither \(v_{i, j}\) nor \(v_{i, j'}\) in \(G+G^*\). Thus, \(v_{i_0, j_0}\) is adjacent to exactly one of \(v_{i, j}, v_{i, j'}\) in \(G\). Therefore, \(u\) cannot be compatible with both \(v_{i, j}\) and \(v_{i, j'}\).

The algorithm verifies that \(f\) is faithful and functional, and aborts if it is not the case. From there, we would like to be able to decide which part of \(\mathcal{P}^*\) each \(u \in V(G)\) belongs to. If \(u\) is compatible with several vertices that belong to the same part \(P_j\) of \(\mathcal{P}^*\), this is a good indication that maybe we should try to put \(u\) in the part \(P_j\). Formally, a vertex \(u \in V(G)\) is flagged if there exists \(j \in [p]\) such that \(|\{i \in [t] : v_{i, j} \in f(u)\}| \geq 2\). This terminology is justified by the following observation – which holds even if the guess is not \((t^*, p^*, \mathcal{R}^*, R^*, G^*/\mathcal{P}^*)\).

Proof of [cl:flagged-unique].  The existence of \(j\) follows from the definition of flagged. We now prove the uniqueness. By contradiction, suppose that there exist \(j \neq j' \in [p]\), \(i_1 \neq i_2 \in [t]\), and \(i'_1 \neq i'_2 \in [t]\) such that \(v_{i_1, j}, v_{i_2, j}, v_{i'_1, j'}, v_{i'_2, j'} \in f(u)\). Since \(H\) is twin-free, there exists \(j_0 \in [p]\) such that exactly one of \(jj_0, j'j_0\) is an edge of \(H\). By construction, there exists \(i_0 \in [t]\) such that \((i_0, j_0) \in \mathcal{R}\), so there is a vertex \(v_{i_0, j_0} \in R\). Without loss of generality, we may assume that \(i_1 \neq i_0 \neq i'_1\). Then, since \(R\) is consistent with \(H\) (otherwise the algorithm would have aborted in Line [line:consistent]) and \(u\) is compatible with both \(v_{i_1, j}\) and \(v_{i'_1, j'}\), we have \[\begin{align} jj_0 \in E(H) &\iff v_{i_1, j}v_{i_0, j_0} \in E(G) \\ &\iff uv_{i_0, j_0} \in E(G) \\ &\iff v_{i'_1, j'}v_{i_0, j_0} \in E(G) \\ &\iff j'j_0 \in E(H), \end{align}\] a contradiction.

Strong conficts.

The information stored by \(f\) is only based on the family \(R\) that we guessed, and it can be inconsistent between different vertices of \(G\). Say that two vertices \(u, u' \in V(G)\) are strongly conflicting if for every \(v_{i, j} \in f(u)\) and every \(v_{i', j'} \in f(u')\) such that \(i \neq i'\), the adjacency in \(G\) between \(v_{i, j}\) and \(v_{i', j'}\) is different from that between \(u\) and \(u'\). This means that if we want to put \(u\) and \(u'\) in the components and parts described by \(f\), they must be placed in the same component.

The reflexive transitive closure of the “strongly conflicting” relation is an equivalence relation. Let \(\mathcal{U}\) be the partition of \(V(G)\) into equivalence classes under this relation. We denote by \(\mathcal{U}^*\) the partition corresponding to the function \(f^*\). As we argued above, the only way to reconcile two strongly conflicting vertices should be to put them in the same component of the perturbation. This is indeed the case in \(G^*\).

Proof of [cl:conflicting-same-cc].  It suffices to prove that if \(u, w \in V(G)\) are strongly conflicting for \(f^*\), they belong to the same component of \(G+G^*\). Let \(u, w \in V(G)\) be strongly conflicting for \(f^*\). Let \(K_{i_u}\) (resp. \(K_{i_{w}}\)) be the component of \(G+G^*\) that contains \(u\) (resp. \(w\)) and let \(P_{j_u}\) (resp. \(P_{j_{w}}\)) be the part of \(\mathcal{P}^*\) that contains \(u\) (resp. \(w\)). By contradiction, suppose that \(i_u \neq i_{w}\).

We first show that there exist vertices \(u', w' \in V(G)\) such that:

• all vertices among \(u, u', w, w'\) belong to different components of \(G+G^*\), except maybe \(\{u, u'\}\), and \(\{w, w'\}\),

• \(u' \in P_{j_u}\) and \(w' \in P_{j_w}\), and

• the number of edges between \(\{u, u'\}\) and \(\{w, w'\}\) in \(G\) is nonzero modulo \(4\).

Consider first the case where \(i_u, i_{w} \in [t^*]\). Then, there are vertices \(v_{i_u, j_u}, v_{i_{w}, j_{w}} \in R^*\), and \(u\) is compatible with \(v_{i_u, j_u}\) and \(w\) with \(v_{i_{w}, j_{w}}\) by [cl:f42-faithful]. Since \(u, w\) are strongly conflicting, exactly one of \(uw\) and \(v_{i_u, j_u}v_{i_{w}, j_{w}}\) is an edge in \(G\), so the number of edges between \(\{u, v_{i_u, j_u}\}\) and \(\{w, v_{i_{w}, j_{w}}\}\) in \(G\) is nonzero modulo 4. In this case, set \(u' = v_{i_u, j_u}\) and \(w' = v_{i_w, j_w}\).

Suppose now that \(i_u \notin [t^*]\) and \(i_w \in [t^*]\). By definition of \(\mathcal{K}^*\), there exists \(i'_u \neq i_w \in [t^*]\) such that \(v_{i'_u, j_u} \in R^*\). Then, \(u\) is compatible with \(v_{i'_u, j_u}\) and \(w\) with \(v_{i_w, j_w}\) by [cl:f42-faithful]. Since \(u, w\) are strongly conflicting, exactly one of \(uw\) and \(v_{i'_u, j_u}v_{i_w, j_w}\) is an edge in \(G\), so the number of edges between \(\{u, v_{i'_u, j_u}\}\) and \(\{w, v_{i_w, j_w}\}\) in \(G\) is nonzero modulo 4. In this case, set \(u' = v_{i'_u, j_u}\) and \(w' = v_{i_w, j_w}\). The case where \(i_u \in [t^*]\) and \(i_w \notin [t^*]\) is symmetric.

Suppose finally that \(i_u, i_w \notin [t^*]\). By definition of \(\mathcal{K}^*\), there exist \(i'_u \in [t^*]\) such that \(v_{i'_u, j_u} \in R^*\), and \(i'_w \neq i'_u \in [t^*]\) such that \(v_{i'_w, j_w} \in R^*\). Then, \(u\) is compatible with \(v_{i'_u, j_u}\) and \(w\) with \(v_{i'_w, j_w}\) by [cl:f42-faithful]. Since \(u, w\) are strongly conflicting, exactly one of \(uw\) and \(v_{i'_u, j_u}v_{i'_w, j_w}\) is an edge in \(G\), so the number of edges between \(\{u, v_{i'_u, j_u}\}\) and \(\{w, v_{i'_w, j_w}\}\) in \(G\) is nonzero modulo 4. In this case, set \(u' = v_{i'_u, j_u}\) and \(w' = v_{i'_w, j_w}\).

This proves the existence of \(u', w'\) with the desired properties. Since \(u, u' \in P_{j_u}\) and \(w, w' \in P_{j_{w}}\), the number of edges between \(\{u, u'\}\) and \(\{w, w'\}\) in \(G^*\) is zero modulo 4. Thus, the number of edges between \(\{u, u'\}\) and \(\{w, w'\}\) in \(G+G^*\) is nonzero modulo 4. This contradicts that all these vertices belong to different components of \(G+G^*\), except maybe \(u\) and \(u'\), and \(w\) and \(w'\). This concludes the proof that \(i_u = i_w\), so \(u, w\) belong to the same component of \(G+G^*\).

Weak conflicts.

There can also be inconsistencies between vertices that are not strongly conflicting. Say that two vertices \(u, u' \in V(G)\) are conflicting if there exist \(v_{i, j} \in f(u)\) and \(v_{i', j'} \in f(u')\) with \(i \neq i'\) such that the adjacency in \(G\) between \(v_{i, j}\) and \(v_{i', j'}\) is different from that between \(u\) and \(u'\). They are weakly conflicting if they are conflicting but not strongly conflicting. We show that weakly conflicting vertices have a very specific behavior, even if the guess is not \((t^*, p^*, \mathcal{R}^*, R^*, G^*/\mathcal{P}^*)\).

Proof of [cl:setup-weakly-conflicting].  Since \(f\) is faithful (otherwise the algorithm would have aborted in Line [line:faithful-functional]), we have \(|f(u)|, |f(u')| \geq 1\). By contradiction, suppose that \(|f(u)| = 1\) and let \(f(u) \mathrel{\vcenter{:}}= \{v_{i, j}\}\). By definition, every \(v_{i', j'} \in f(u')\) with \(i' \neq i\) has the same adjacency as \(u'\) on \(v_{i, j}\) in \(G\). Thus, either \(u\) and \(u'\) are strongly conflicting or they are not conflicting, which is impossible by assumption. Thus, \(|f(u)| \geq 2\), and by symmetry \(|f(u')| \geq 2\).

By contradiction, suppose that \(|f(u)| \geq 3\) and let \(v_{i_1, j_1}, v_{i_2, j_2}, v_{i_3, j_3} \in f(u)\). Since \(f\) is functional (otherwise the algorithm would have aborted in Line [line:faithful-functional]), \(i_1, i_2\) and \(i_3\) are distinct. Let \(v_{i'_1, j'_1}, v_{i'_2, j'_2} \in f(u')\). Again, \(i'_1\) and \(i'_2\) are distinct. Without loss of generality, we can assume that \(i_1, i_2, i_3, i'_1, i'_2\) are pairwise distinct, except maybe \(i_1, i'_1\), and \(i_2, i'_2\). By symmetry, suppose that \(u'\) is adjacent to \(v_{i_3, j_3}\) in \(G\). Since \(u'\) is compatible with \(v_{i'_1, j'_1}\) and \(v_{i'_2, j'_2}\), they are both adjacent to \(v_{i_3, j_3}\) in \(G\). Since \(u\) is compatible with \(v_{i_3, j_3}\), \(u\) is adjacent to both \(v_{i'_1, j'_1}\) and \(v_{i'_2, j'_2}\) in \(G\). Since \(u\) is compatible with \(v_{i_1, j_1}\) and \(v_{i_2, j_2}\), they are both adjacent to \(v_{i'_1, j'_1}\) and \(v_{i'_2, j'_2}\) in \(G\), except maybe \(v_{i_1, j_1}\) and \(v_{i'_1, j'_1}\) if \(i_1 = i'_1\), and \(v_{i_2, j_2}\) and \(v_{i'_2, j'_2}\) if \(i_2 = i'_2\). Since \(v_{i_1, j_1}, v_{i_2, j_2}, v_{i_3, j_3} \in f(u)\) and \(v_{i'_1, j'_1}, v_{i'_2, j'_2} \in f(u')\) were arbitrary, it follows that either \(u, u'\) are strongly conflicting or they are not conflicting. Both these outcomes are impossible, so \(|f(u)| = 2\) and symmetrically \(|f(u')| = 2\).

Write \(f(u) = \{v_{i_1, j_1}, v_{i_2, j_2}\}\) and \(f(u') = \{v_{i'_1, j'_1}, v_{i'_2, j'_2}\}\). Since \(f\) is functional, \(i_1\) and \(i_2\) are distinct and so are \(i'_1\) and \(i'_2\). By contradiction, suppose that \(\{i_1, i_2\} \neq \{i'_1, i'_2\}\). Without loss of generality, we can assume that \(i_1, i_2, i'_1, i'_2\) are pairwise distinct, except maybe \(i_2, i'_2\). By symmetry, suppose that \(u'\) is adjacent to \(v_{i_1, j_1}\) in \(G\). Since \(u'\) is compatible with \(v_{i'_1, j'_1}\) and \(v_{i'_2, j'_2}\), they are both adjacent to \(v_{i_1, j_1}\) in \(G\). Since \(u\) is compatible with \(v_{i_1, j_1}\), \(u\) is adjacent to both \(v_{i'_1, j'_1}\) and \(v_{i'_2, j'_2}\) in \(G\). Since \(u\) is compatible with \(v_{i_2, j_2}\), \(v_{i_2, j_2}\) is adjacent to \(v_{i'_1, j'_1}\) in \(G\), and to \(v_{i'_2, j'_2}\) in \(G\) unless maybe if \(i_2 = i'_2\). Then, it follows that either \(u, u'\) are strongly conflicting or they are not conflicting. Both these outcomes are impossible, so \(\{i_1, i_2\} = \{i'_1, i'_2\}\). This proves the first part of the statement. Since \(u\) and \(u'\) are weakly conflicting, it follows immediately that exactly one of \(v_{i_1, j_1}v_{i_2, j'_2}\) and \(v_{i_1, j'_1}v_{i_2, j_2}\) is an edge in \(G\).

Crossings.

[cl:setup-weakly-conflicting] motivates the following definition. Let \(i_1 \neq i_2 \in [t]\) and \(j_1, j_2, j'_1, j'_2 \in [p]\) such that \((i_1, j_1), (i_1, j'_1), (i_2, j_2), (i_2, j'_2) \in \mathcal{R}\). We say that \((i_1, i_2, j_1, j'_1, j_2, j'_2)\) is crossing if \(v_{i_1, j_1}v_{i_2, j'_2} \in E(G)\) and \(v_{i_1, j'_1}v_{i_2, j_2} \notin E(G)\). Let \(X \subseteq [t]^2 \times [p]^4\) denote the set of all such tuples that are crossing. Let \(X^* \subseteq [t^*]^2 \times [p^*]^4\) be the corresponding set for \((t^*, p^*, \mathcal{R}^*, R^*, G^*/\mathcal{P}^*)\).

Thus, [cl:setup-weakly-conflicting] asserts that if \(u, u' \in V(G)\) are weakly conflicting, there exists \(x = (i_1, i_2, j_1, j_2, j'_1, j'_2) \in X\) such that \(f(u) = \{v_{i_1, j_1}, v_{i_2, j_2}\}\) and \(f(u') = \{v_{i_1, j'_1}, v_{i_2, j'_2}\}\), say. Suppose that we know that \(u, u' \in V(K_{i_1} \cup K_{i_2})\) and that if \(u \in V(K_{i_1})\) then \(u \in P_{j_1}\) and so on. In that case, if \(uu' \in E(G)\), we have \(u' \in K_{i_1} \Rightarrow u \in K_{i_1}\), and if \(uu' \notin E(G)\), we have \(u \in K_{i_1} \Rightarrow u' \in K_{i_1}\). We represent these constraints as follows.

Let \(x = (i_1, i_2, j_1, j_2, j'_1, j'_2) \in X\). Let \(W_x = \{u \in V(G) : f(u) = \{v_{i_1, j_1}, v_{i_2, j_2}\}\}\) and \(W'_x = \{u \in V(G) : f(u) = \{v_{i_1, j'_1}, v_{i_2, j'_2}\}\}\). The crossing digraph for \(x\) is the directed graph \(D_x\) on vertex set \(W_x \cup W'_x\) with an arc from \(u \in W_x\) to \(u' \in W'_x\) if and only if \(uu' \notin E(G)\) and an arc from \(u' \in W'_x\) to \(u \in W_x\) if and only if \(uu' \in E(G)\). We show how this digraph can be used to solve the weak conflicts between \(W_x\) and \(W'_x\) for \((G, G^*)\).

Proof of [cl:exists-crossing-solver].  Let \(\mathcal{S} = \{S_1, \ldots, S_s\}\) be the set of strongly connected components of \(D_x\). Let \(D'_x\) be the directed acyclic graph on vertex set \(\mathcal{S}\) obtained by contracting each \(S_i\) to a single vertex. It follows from [cl:f42-faithful] that \(W_x \cup W'_x \subseteq V(K_{i_1}) \cup V(K_{i_2})\). [cl:f42-faithful] also implies that for every \(u \in W_x\), if \(u \in V(K_{i_1})\) then \(u \in P_{j_1}\), and so on. Thus, as we argued before, an arc from \(u\) to \(v\) in \(D_x\) means that \(u \in V(K_{i_1})\) implies \(v \in V(K_{i_1})\). Thus, for every \(a \in [s]\), either \(S_a \subseteq V(K_{i_1})\) or \(S_a \subseteq V(K_{i_2})\). Without loss of generality, we can assume that \(S_1 \prec S_2 \prec \ldots \prec S_s\) is a topological ordering of \(D'_x\).

If \(W_x \cup W'_x \subseteq V(K_{i_2})\), we are done, so suppose that \(W_x \cup W'_x \not\subseteq V(K_{i_2})\). Let \(a \in [s]\) be minimum such that \(S_a \subseteq V(K_{i_1})\), which is well-defined since \(W_x \cup W'_x \not\subseteq V(K_{i_2})\). Let \(u_0\) be an arbitrary vertex of \(S_a\). Let \(u \in V(D_x)\) be reachable from \(u_0\) in \(D_x\). Since \(u_0 \in V(K_{i_1})\) and since there exists a directed path from \(u_0\) to \(u\) in \(D_x\), it follows that \(u \in V(K_{i_1})\). Let \(u \in V(D)\) that cannot be reached from \(u_0\) but can reach \(u_0\) in \(D_x\). Let \(b \in [s]\) such that \(u \in S_b\). Since \(u\) can reach \(u_0 \in S_a\), we have \(b \leq a\). Since \(S_a\) is strongly connected in \(D_x\) and \(u_0\) cannot reach \(u\) in \(D_x\), we have \(b \neq a\), so \(b < a\). Thus, by minimality of \(a\), we have \(S_b \not \subseteq V(K_{i_1})\), so \(S_b \subseteq V(K_{i_2})\) so \(u \in V(K_{i_2})\).

Crossing solvers.

A function \(\phi : X^* \to V(G) \cup \{\bot\}\) is a crossing solver for \((t^*, p^*, \mathcal{R}^*, R^*, G^*/\mathcal{P}^*)\) if the following holds for every \(x = (i_1, i_2, j_1, j_2, j'_1, j'_2) \in X^*\):

• If \(\phi(x) = \bot\) then \(W_x \cup W'_x \subseteq V(K_{i_2})\).

• Otherwise, \(\phi(x) \in W_x \cup W'_x\), every \(u \in W_x \cup W'_x\) that can be reached from \(\phi(x)\) in \(D_x\) satisfies \(u \in V(K_{i_1})\), and every \(u \in W_x \cup W'_x\) that cannot be reached from \(\phi(x)\) in \(D_x\) but that can reach \(\phi(x)\) in \(D_x\) satisfies \(u \in V(K_{i_2})\).

[cl:exists-crossing-solver] exactly says that there exists a crossing solver for \((t^*, p^*, \mathcal{R}^*, R^*, G^*/\mathcal{P}^*)\). Let \(\phi^*\) be such a crossing solver.

In the algorithm, we now guess a function \(\phi : X \to V(G) \cup \bot\) such that for every \(x \in X\), we have \(\phi(x) \in W_x \cup W'_x \cup \{\bot\}\).

Updated compatibility.

Given [cl:exists-crossing-solver], it is natural to update the compatibility function \(f\) to an updated compatibility function \(\widehat{f} : V(G) \to 2^R\) as follows. For every \(u \in V(G)\), \(\widehat{f}(u)\) is the maximal subset of \(f(u)\) that satisfies the following conditions. For every crossing \(x = (i_1, i_2, \cdot, \cdot, \cdot, \cdot) \in X\) such that \(u \in W_x \cup W'_x\), we have:

• If \(\phi(x) = \bot\) then \(\widehat{f}(u) \subseteq \{v_{i_2, j_2} : j_2 \in [p], (i_2, j_2) \in \mathcal{R}\}\).

• Otherwise, let \(D_x\) be the crossing digraph for \(x\). If \(\phi(x)\) can reach \(u\) in \(D_x\) then \(\widehat{f}(u) \subseteq \{v_{i_1, j_1} : j_1 \in [p], (i_1, j_1) \in \mathcal{R}\}\). If \(\phi(x)\) cannot reach \(u\) but \(u\) can reach \(\phi(x)\) in \(D_x\) then \(\widehat{f}(u) \subseteq \{v_{i_2, j_2} : j_2 \in [p], (i_2, j_2) \in \mathcal{R}\}\).

We then define \(\tau : \mathcal{U} \to [t]\) as follows: for every \(U \in \mathcal{U}\), \(\tau(U) = \{i \in [t] : \forall u \in U, \exists j \in [p] : v_{i, j} \in \widehat{f}(u)\}\). Intuitively, \(\widehat{f}\) stores where each vertex can go with respect to \(\mathcal{P}^*\) and the partition into components of \(G+G^*\). Given [cl:conflicting-same-cc], for every \(U \in \mathcal{U}\), we want to put all vertices of \(U\) in the same component of \(G+G^*\). Then, \(\tau(U)\) represents the set of all eligible components (among those from \(\mathcal{K}^*\)). Let \(\widehat{f^*}\) be the updated compatibility function obtained from \(f^*\) and \(\phi^*\), and let \(\tau^* : \mathcal{U}^* \to [t^*]\) be the corresponding function. It will follow from [cl:updated-compatibility-info] that \(\tau^*(U) \neq \emptyset\) for every \(U \in \mathcal{U}^*\).

The next lemma gives a sufficient condition for a part \(U \in \mathcal{U}^*\) to be contained in one of the components that were selected in \(\mathcal{K}^*\). It turns out that this condition is also necessary, although we do not state it since we will not use it (explicitly).

Proof of [cl:updated-compatibility-info].  Consider such a \(U \in \mathcal{U}^*\). By [cl:conflicting-same-cc], all vertices of \(U\) belong to the same component \(K_i\) of \(G+G^*\), for some \(i \in [c^*]\). By contradiction, suppose that \(i \notin [t^*]\). Since \(\mathcal{K}^*\) is a typical set of components of \(G+G^*\), there exist distinct \(i_1, i_2, i_3 \in [t^*]\) such that \(K_{i_1}, K_{i_2}, K_{i_3}\) all have the same signature as \(K_i\). Let \(u \in U\) and let \(j \in [p^*]\) such that \(u \in P_j\). Then, \(v_{i_1, j}, v_{i_2, j}, v_{i_3, j} \in f^*(u)\) by [cl:f42-faithful], so \(u\) is flagged. Furthermore, \(|f^*(u)| \geq 3\) so \(\widehat{f^*}(u) = f^*(u)\). Thus, \(i_1, i_2, i_3 \in \tau^*(U)\), so \(|\tau^*(U)| \geq 3\), a contradiction.

Thus, we have \(i \in [t^*]\). Let \(u \in U\) and let \(j \in [p^*]\) such that \(u \in P_j\). Then, \(v_{i, j} \in f^*(u)\) by [cl:f42-faithful]. Using that \(\phi^*\) is a crossing solver, it then follows from unpacking the definitions of crossing solver and of updated compatibility function that \(v_{i, j} \in \widehat{f^*}(u)\). Thus, \(i \in \tau^*(U)\).

Suitable partition.

The next step will be to solve an auxiliary problem to try to compute the partition into components of \(G+G^*\). We will prove in [cl:C42-cc-G43G39] that if the guesses are \((t^*, p^*, \mathcal{R}^*, R^*, G^*/\mathcal{P}^*)\) then the partition we compute is (roughly) the partition into components of some rank-\(k\) perturbation \(G'\) of \(G\) that minimizes the largest component size.

The width of a partition \(\mathcal{C}\) is the maximum size of a part of \(\mathcal{C}\). Say that a partition \(\mathcal{C}\) of \(V(G)\) is suitable if it satisfies the following constraints:

• \(\mathcal{U}\) refines \(\mathcal{C}\),

• For every \(i \in [t]\) there exists \(C_i \in \mathcal{C}\) such that \(v_{i, j} \in C_i\) for every \(j \in [p]\) such that \((i, j) \in \mathcal{R}\).

• If \(U \in \mathcal{U}\) is such that \(|\tau(U)| \leq 2\) or some \(u \in U\) is not flagged then there exists \(i \in \tau(U)\) such that \(U \subseteq C_i\).

The algorithm computes a suitable partition \(\mathcal{C}\) of \(V(G)\) of minimum width. If there is no such partition, the algorithm aborts. Note that the partition with a single part equal to \(V(G)\) is always suitable, unless there exists \(U \in \mathcal{U}\) with \(\tau(U) = \emptyset\), in which case there is no suitable partition. Thus, the algorithm only aborts if there exists \(U \in \mathcal{U}\) with \(\tau(U) = \emptyset\). Note that in the case where we guessed \((t^*, p^*, \mathcal{R}^*, R^*, G^*/\mathcal{P}^*)\) and \(\phi^*\), the partition into components of \(G+G^*\) is a suitable partition by [cl:conflicting-same-cc], by definition of \(R^*\) and by [cl:updated-compatibility-info].

We now argue that such a partition \(\mathcal{C}\) can be computed efficiently. Note that there is always a partition of minimum width where \(C_i \neq C_{i'}\) for all \(i \neq i'\), so we can restrict our attention to such partitions. Similarly, there is always a partition of minimum width where every \(U \in \mathcal{U}\) such that \(|\tau(U)| \geq 3\) and every \(u \in U\) is flagged forms its own part of \(\mathcal{C}\), so we can restrict our attention to such partitions. Then, denote the other parts of \(\mathcal{U}\) by \(U_1, \ldots, U_r\). For each \(i \in [r]\), let \(w_i \mathrel{\vcenter{:}}= |U_i|\) and \(L_i \mathrel{\vcenter{:}}= \tau(U_i) \subseteq [t]\). Note that \(\sum_{i = 1}^r|U_i| \leq n\). Observe now that our problem is simply an instance of weighted list balancing, as we want to find an assignment \(\alpha : [r] \to [t]\) of the \(U_i\) to \(C_1, \ldots, C_t\) such that \(\alpha(i) \in L_i\) for every \(i \in [r]\). Note that the fact that \(v_{i, j} \in C_i\) for all \(v_{i, j} \in R\) will follow from the fact that \(f(v_{i, j}) = \{v_{i, j}\}\) so the part \(U \in \mathcal{U}\) that contains \(v_{i, j}\) satisfies \(\tau(U) \subseteq \{i\}\). By 5, we can then find the desired suitable partition \(\mathcal{C}\) in time \(\mathcal{O}(t\cdot |\mathcal{U}| \cdot |V(G)|^{t-1}) = n^{f(k)}\) for some computable function \(f\).

Perturbation.

We would now like to say that \(\mathcal{C}\) can be realized as the partition into components of some rank-\(k\) perturbation \(G+\widehat{G}\) of \(G\). Note that since we are given \(G\) and the partition \(\mathcal{C}\), this uniquely determines the edges of \(\widehat{G}\) between vertices of \(G\) that belong to different parts of \(\mathcal{C}\). Thus, it suffices to figure out whether there is a way to choose the edges inside each part of \(\mathcal{C}\) so that the resulting looped graph has rank at most \(k\). It follows from the work of Peeters [69] that the general problem of deciding whether a partial binary matrix can be completed to a binary matrix of rank at most \(k\) is already -hard for \(k=3\), and we do not see how to solve this problem more efficiently in our context.

However, with all the information that we have gathered up to this point, there is a natural way to define a candidate looped graph \(\widehat{G}\) of rank at most \(k\) such that the partition into components of \(G+\widehat{G}\) might refine \(\mathcal{C}\).

We define a function \(\psi : V(G) \to [p]\). We will then define \(\widehat{G}\) as the graph on vertex set \(V(G)\) where \(u, u' \in V(G)\) are adjacent if and only if \(\psi(u)\) and \(\psi(u')\) are adjacent in \(H\). Since \(H\) has rank at most \(k\), it follows from [obs:rank-quotient] that \(\widehat{G}\) has rank at most \(k\).

Let \(u \in V(G)\) and let \(U \in \mathcal{U}\) such that \(u \in U\). Suppose first that \(|\tau(U)| \geq 3\) and every \(u \in U\) is flagged. Then, by [cl:flagged-unique], there exists a unique \(j \in [p]\) such that \(|\{i \in [t] : v_{i, j} \in f(u)\}| \geq 2\). We set \(\psi(u) = j\). Otherwise, by assumption there exists \(i \in \tau(U)\) such that \(U \subseteq C_i\). Since \(i \in \tau(U)\), there exists \(j \in [p]\) such that \(v_{i, j} \in \widehat{f}(u) \subseteq f(u)\). Such a \(j\) is unique since \(f\) is functional. We set \(\psi(u) = j\).

The algorithm then verifies that the partition into components of \(G+\widehat{G}\) refines \(\mathcal{C}\). If so, it returns the width of \(\mathcal{C}\), and if not it aborts. Then, the algorithm outputs the minimum width that was returned among all guesses for which the corresponding run did not abort.

Correctness.

Let \(OPT\) be the solution of the instance \((G, k)\), so \(OPT\) is the maximum size of a component of \(G+G^*\) since \(G^*\) is \(k\)-optimal for \(G\). Let \(w\) be the value output by the algorithm. We now argue that \(w = OPT\).

First, observe that for every guess, if the algorithm returns some value \(v\) then there is a rank-\(k\) perturbation of \(G\) whose maximum component has size at most \(v\).

Consider now the run of the algorithm where the guesses are \((t^*, p^*, \mathcal{R}^*, R^*, G^*/\mathcal{P}^*)\) and \(\phi^*\). As before, let \(f^*, \mathcal{U}^*, X^*, \widehat{f^*}, \tau^*, \mathcal{C}^*, \psi^*\) be the values computed by the algorithm during this run. Note that \(R^*\) is consistent with \(G^*/\mathcal{P}^*\) by [cl:consistent], \(f^*\) is faithful and functional by [cl:f42-faithful] [f42-functional] and the partition into components of \(G+G^*\) is a candidate for the partition \(\mathcal{C}^*\) as we already argued. Thus, this run does not abort before computing \(\widehat{G}\), and the width of the partition \(\mathcal{C}^*\) is at most \(OPT\). We now show that this run does not abort at all.

Proof of [cl:C42-cc-G43G39].  It suffices to prove that any two vertices that are adjacent in \(G+\widehat{G}\) are in the same part of \(\mathcal{C}^*\). Let \(uu' \in E(G+\widehat{G})\), let \(U \in \mathcal{U}^*\) (resp. \(U' \in \mathcal{U}^*\)) be the part of \(\mathcal{U}^*\) that contains \(u\) (resp. \(u'\)), and let \(j = \psi^*(u)\) and \(j' = \psi^*(u')\). We show that \(u\) and \(u'\) belong to the same part of \(\mathcal{C}^*\). Note that \(\mathcal{U}^*\) refines \(\mathcal{C}^*\) by definition of \(\mathcal{C}^*\), so if \(U = U'\) then we are done. From now on, we assume that \(U \neq U'\), so \(u\) and \(u'\) are not strongly conflicting.

Suppose first that \(|\tau^*(U)| \geq 3\) and every \(v \in U\) is flagged. Since \(|\tau^*(U)| \geq 3\), we have \(|f^*(u)| \geq 3\). Then, \(u\) and \(u'\) are not weakly conflicting by [cl:setup-weakly-conflicting]. By definition of \(\psi^*\), we have \(|\{i \in [t^*] : v_{i, j} \in f^*(u)\}| \geq 2\) and there exists \(i' \in [t^*]\) such that \(v_{i', j'} \in f^*(u')\). Thus, there exist \(i \neq i' \in [t^*]\) such that \(v_{i, j} \in f^*(u)\) and \(v_{i', j'} \in f^*(u')\). Using that \(u\) and \(u'\) are not conflicting, that \(R^*\) is consistent with \(G^*/\mathcal{P}^*\) and the definition of \(\widehat{G}\), we have: \[\begin{align} uu' \in E(G) &\iff v_{i, j}v_{i', j'} \in E(G) \\ &\iff jj' \in E(G^*/\mathcal{P}^*) \\ &\iff uu' \in E(\widehat{G}). \end{align}\] This contradicts that \(uu' \in E(G+\widehat{G})\).

By symmetry, it is also not the case that \(|\tau^*(U')| \geq 3\) and every \(v' \in U'\) is flagged. Thus, by definition of \(\mathcal{C}^*\), there exist \(i \in \tau^*(U)\) and \(i' \in \tau^*(U')\) such that \(U \subseteq C_i\) and \(U' \subseteq C_{i'}\). By definition of \(\psi^*\), we have \(v_{i, j} \in f^*(u)\) and \(v_{i', j'} \in f^*(u')\). By contradiction, suppose \(i \neq i'\). Consider first the case where \(u\) and \(u'\) are not conflicting. Then, using also that \(R\) is consistent with \(H\) and the definition of \(\widehat{G}\), we have: \[\begin{align} uu' \in E(G) &\iff v_{i, j}v_{i', j'} \in E(G) \\ &\iff jj' \in E(G^*/\mathcal{P}^*) \\ &\iff uu' \in E(\widehat{G}). \end{align}\] Again, this contradicts that \(uu' \in E(G+\widehat{G})\). Consider now the case where \(u\) and \(u'\) are conflicting, in which case they must be weakly conflicting. By [cl:setup-weakly-conflicting], there exists \(x = (i_1, i_2, j_1, j_2, j'_1, j'_2) \in X^*\) such that \(u \in W_x\) and \(u' \in W'_x\), say. Recall that \(D_x\) denotes the crossing digraph for \(x\). Suppose first that \(\phi^*(x) = \bot\). By definition of \(\widehat{f^*}\), we have \(\widehat{f^*}(u) \subseteq \{v_{i_2, j_2}\}\) and \(\widehat{f^*}(u') \subseteq \{v_{i_2, j'_2}\}\). But then \(\tau^*(U), \tau^*(U') \subseteq \{i_2\}\) so \(i = i_2 = i'\), a contradiction.

Otherwise, we have \(\phi^*(x) \in W_x \cup W'_x\). By symmetry between \(u\) and \(u'\), we may assume that \(\phi^*(x) \in W_x\). Note that any vertex of \(W_x\) and any vertex of \(W'_x\) are connected by an arc in \(D_x\). Then, either \(\phi^*(x)\) can reach \(u'\) in \(D_x\) or \(u'\) can reach \(\phi^*(x)\) in \(D_x\). By definition of \(\widehat{f}\), in the first case we have \(\tau^*(U') \subseteq \{i_1\}\), and if the first case does not hold we have \(\tau^*(U') \subseteq \{i_2\}\).

Suppose that \(\phi^*(x)\) can reach \(u'\) in \(D_x\), so \(\tau^*(U') \subseteq \{i_1\}\) so \(i' = i_1\) and \(j' = j'_1\). Since \(i \neq i'\), we have \(i = i_2\) and \(j = j_2\). Since \(x\) is crossing, we have \(v_{i_1, j'_1}v_{i_2, j_2} \notin E(G)\) so \(j'_1j_2 \notin E(G^*/\mathcal{P}^*)\) since \(R^*\) is consistent with \(G^*/\mathcal{P}^*\) by [cl:consistent]. Thus, \(uu' \notin E(\widehat{G})\) by definition of \(\widehat{G}\), so \(uu' \in E(G)\). Thus, there is an arc from \(u'\) to \(u\) in \(D_x\), so \(\phi^*(x)\) can reach \(u\) in \(D_x\) so \(\tau^*(U) \subseteq \{i_1\}\) and \(i = i_1\), a contradiction.

Suppose finally that \(\phi^*(x)\) cannot reach \(u'\) in \(D_x\), so \(u'\) can reach \(\phi^*(x)\) in \(D_x\), so \(\tau^*(U') \subseteq \{i_2\}\) so \(i' = i_2\) and \(j' = j'_2\). Since \(i \neq i'\), we have \(i = i_1\) and \(j = j_1\). Since \(x\) is crossing, we have \(v_{i_1, j_1}v_{i_2, j'_2} \in E(G)\) so \(j_1j'_2 \in E(G^*/\mathcal{P}^*)\) since \(R^*\) is consistent with \(G^*/\mathcal{P}^*\) by [cl:consistent]. Thus, \(uu' \in E(\widehat{G})\) by definition of \(\widehat{G}\), so \(uu' \notin E(G)\). Thus, there is an arc from \(u\) to \(u'\) in \(D_x\), so \(u\) can reach \(u'\) in \(D_x\). Furthermore, \(\phi^*(x)\) cannot reach \(u\) in \(D_x\), otherwise \(\phi^*(x)\) could reach \(u'\) in \(D_x\). Thus, \(\tau^*(U) \subseteq \{i_2\}\) and \(i=i_2\), a contradiction. We obtained a contradiction in all cases, so we must have \(i = i'\), so \(u \in C_i = C_{i'} \ni u'\), as desired.

Therefore, when the guesses are \((t^*, p^*, \mathcal{R}^*, R^*, G^*/\mathcal{P}^*)\) and \(\phi^*\), the run returns a value \(v \leq OPT\), so \(w \leq OPT\). This concludes the proof that \(w = OPT\), which proves the correctness of the algorithm.

Running time.

Let \(n\) be the number of vertices of \(G\). It follows from the description and analysis of the algorithm that each run can be performed in time \(n^{f(k)}\) for some (computable) function \(f\) (actually, all steps can be performed in time except the computation of \(\mathcal{C}\)). The number of possible choices for \(t, p, \mathcal{R}\) and \(H\) is bounded by a function of \(k\). Thus, the size of \(R\) is bounded by a function of \(k\). The size of \(X\) is also bounded by a function of \(k\) so the “size” of \(\phi\) is also bounded by a function of \(k\). Thus, the total number of runs of the algorithm is \(n^{g(k)}\) for some (computable) function \(g\). Thus, this algorithm is indeed an algorithm solving rank integrity. ◻

Proof. Since \(H_n[X, Y]\) is complete or empty, for all \(x, x' \in X\) and \(y, y' \in Y\) we have \(x \cdot y = x' \cdot y'\). If \(X = \emptyset\) then we are done, so suppose \(X \neq \emptyset\). Fix \(x_0 \in X\) arbitrarily. Then, for all \(x \in X\) and \(y \in Y\) we have \((x-x_0)\cdot y = x_0 \cdot y - x \cdot y = 0\).

Let \(X - x_0 \mathrel{\vcenter{:}}= \{x - x_0 : x \in X\} \subseteq \{0, 1\}^n\) and let \(U \mathrel{\vcenter{:}}= \text{span}(X-x_0) \subseteq \{0, 1\}^n\). We showed that \(Y \subseteq (X - x_0)^{\perp} = U^{\perp}\). The scalar product is a non-degenerate bilinear form over \(\{0, 1\}^n\) so \(\dim(U) + \dim(\text{span}(Y)) \leq \dim(U) + \dim(U^{\perp}) = n\). Therefore, \(|X|\cdot|Y| \leq 2^{\dim(U)} \cdot 2^{n - \dim(U)} = 2^n\). ◻

Proof. Since the cut \((A, B)\) has rank at most \(k\), we can partition \(A\) into \(r \leq 2^k\) parts \(A_1, \ldots, A_{r}\) and \(B\) into \(s \leq 2^k\) parts \(B_1, \ldots, B_s\) such that each bipartite graph \(H_n[A_i, B_j]\) is complete or empty. Thus, 7 implies that \(|A_i| \cdot |B_j| \leq 2^n\) for all \(i \in [r]\) and \(j \in [s]\). Altogether, this implies \(|A| \cdot |B| \leq 2^{2k} \cdot 2^n\). Without loss of generality, we may assume that \(|A| \leq |B|\) so \(|B| \geq 2^{n-1}\) since \((A, B)\) is a partition of \(\{0, 1\}^n\). Then, \(|A| \cdot |B| \geq |A| \cdot 2^{n-1}\) so \(|A| \cdot 2^{n-1} \leq 2^{2k} \cdot 2^n\) so \(|A| \leq 2^{2k+1}\). ◻

Proof. By contradiction, suppose that all the components of \(H_n + \widehat{H}\) have less than \(2^n-2^{2k+1}\) vertices. If one component has more than \(2^{n-2}\) vertices, let \(A\) be the vertex set of such a component. Then, \(|A|, |V(H_n) \setminus A| > 2^{2k+1}\) and there is no edge between \(A\) and \(V(H_n) \setminus A\) in \(H_n + \widehat{H}\). If all components have size at most \(2^{n-2}\), by considering a minimal collection of components whose union has size at least \(2^{n-1}\), we obtain a set \(A\) satisfying \(2^{n}/2 \leq |A| <3 \cdot 2^n/4\). Thus, \(|A|, |V(H_n) \setminus A| > 2^{2k+1}\) and there is no edge between \(A\) and \(V(H_n) \setminus A\) in \(H_n + \widehat{H}\). In both cases, the graph \((H_n + \widehat{H})[A, V(H_n) \setminus A]\) is edgeless, so \(H_n[A, V(H_n) \setminus A] = \widehat{H}[A, V(H_n) \setminus A]\), which implies that \(H_n[A, V(H_n) \setminus A]\) has rank at most \(k\). Thus, \((A, V(H_n) \setminus A)\) is a cut of \(H_n\) of rank at most \(k\) with \(\min(|A|, |V(H_n) \setminus A|) > 2^{2k+1}\), which contradicts 8. ◻

Proof. Let \(e_1, \ldots, e_{k-1}\) denote the canonical basis of \(\{0, 1\}^{k-1}\). For every \(i \in [k-1]\), let \(u_i \mathrel{\vcenter{:}}= e_i\), and let \(u_k \mathrel{\vcenter{:}}= e_1 + \ldots + e_k\). For all \(i < j \in [k-1]\), let \(u_{i, j} \mathrel{\vcenter{:}}= e_i + e_j\), and for every \(i \in [k-1]\), let \(u_{i, k} \mathrel{\vcenter{:}}= e_i\). Let \(U_1 \mathrel{\vcenter{:}}= \begin{bmatrix} u_1 \ldots u_k \end{bmatrix} \in (\{0, 1\}^{k-1})^{k}\), \(U_2 \mathrel{\vcenter{:}}= \begin{bmatrix} u_{1, 2} \ldots u_{k-1, k} \end{bmatrix} \in (\{0, 1\}^{k-1})^{\binom{k}{2}}\) and \(U \mathrel{\vcenter{:}}= \begin{bmatrix} U_1 U_2 \end{bmatrix} \in (\{0, 1\}^{k-1})^{k + \binom{k}{2}}\). We claim that \((U_1)^{\intercal}U_2 = B_k\). Indeed, let \(i \in [k]\) and \(j < j' \in [k]\). We consider four cases depending on the values of \(i\) and \(j'\).

• If \(i \in [k-1]\) and \(j' \in [k-1]\) then \(u_i \cdot u_{j, j'} = e_i \cdot (e_j + e_{j'})\) is \(1\) if and only if \(i \in \{j, j'\}\).

• If \(i \in [k-1]\) and \(j' = k\) then \(u_i \cdot u_{j, j'} = e_i \cdot e_j\) is \(1\) if and only if \(i \in \{j, j'\}\).

• If \(i = k\) and \(j' \in [k-1]\) then \(u_i \cdot u_{j, j'} = (e_1 + \ldots + e_{k-1}) \cdot (e_j + e_{j'}) = 0\).

• If \(i = k\) and \(j' = k\) then \(u_i \cdot u_{j, j'} = (e_1 + \ldots + e_{k-1}) \cdot e_j = 1\).

Let \(A_k \mathrel{\vcenter{:}}= (U_1)^{\intercal} U_1\) and \(C_k \mathrel{\vcenter{:}}= (U_2)^{\intercal} U_2\), and note that \(A_k\) and \(C_k\) are symmetric matrices. Note that \(U\) consists of vectors of \(\{0, 1\}^{k-1}\) so \(U\) has rank at most \(k-1\). Then, setting \(M_k \mathrel{\vcenter{:}}= U^{\intercal}U\), it follows that \(M_k\) has rank at most \(k-1\) and \[M_k= \begin{bmatrix} A_k & B_k \\ (B_k)^{\intercal} & C_k \end{bmatrix}.\]

Finally, note that the \(k-1\) first rows of \(B_k\) are linearly independent (because for each row, there is a column in which it has entry \(1\), while all the other first \(k-1\) rows have entry \(0\)), so \(\text{rk}(M_k) \geq \text{rk}(B_k) \geq k-1\). ◻

Proof. By contradiction, suppose that \(n - c \leq k-1\). As long as there are (at least) two components of \(G\) of size at least \(2\), move one vertex from the smallest such component to the largest one, and make it adjacent to all the vertices in its new component. Then, add all the missing edges inside each component. Observe that each modification adds at least one edge. Eventually, we obtain the graph \(G^*\) with \((c-1)\) components of size \(1\) and one component of size \(n-(c-1) \leq k\) which forms a clique. Note that \(G^*\) has exactly \(\binom{n-c+1}{2} \leq \binom{k}{2}\) edges, so both \(G\) and \(G^*\) have exactly \(\binom{k}{2}\) edges. Thus, we did not add any edge when going from \(G\) to \(G^*\), which means that \(G = G^*\). Since \(G^*\) has \(\binom{k}{2}\) edges, \(G^*\) must contain \(K_k\), so \(G\) contains a clique of size \(k\), a contradiction. ◻

Proof. Let \(I_G\) denote the vertex-edge incidence matrix of \(G\). Let \(n\) denote the number of vertices of \(G\) and \(c\) its number of components. Combining 11 and 12, we get \(\text{rk}(I_G) = n-c \geq k\). ◻

Proof. Suppose first that \(G\) contains a clique \(C\) of size \(k\). By 10, there exists a looped graph \(G_k\) of rank \(k-1\) on vertex set \(V(C) \cup E(C)\) such that \(G_k[V(C), E(C)]\) is isomorphic to the vertex-edge incidence graph between \(V(C)\) and \(E(C)\) in \(G\). By replacing each vertex in \(V(C) \cup E(C)\) by a clique or a stable set of size \(2^{2k}\), according to whether the corresponding vertex is looped or not, it follows that there exists a graph \(G'_k\) of rank \(k-1\) on vertex set \(\bigcup_{v \in V(C)} V_v \cup \bigcup_{e \in E(C)} V_e\) such that \(G'_k[\bigcup_{v \in V(C)} V_v, \bigcup_{e \in E(C)} V_e] = \Gamma_k(G)[\bigcup_{v \in V(C)} V_v, \bigcup_{e \in E(C)} V_e]\). Let \(\widehat{\Gamma}\) be the graph on vertex set \(V(\Gamma_k(G))\) obtained from \(G'_k\) by adding the vertices of \(V(\Gamma_k(G)) \setminus V(G'_k)\) as isolated vertices. Then, \(\widehat{\Gamma}\) is a graph of rank \(k-1\) on the same vertex set as \(\Gamma_k(G)\). Furthermore, the vertices in \(\bigcup_{e \in E(C)} V_e\) are separated from the other vertices in \(\Gamma_k(G) + \widehat{\Gamma}\), so the largest component of \(\Gamma_k(G)+\widehat{\Gamma}\) has size at most \(|\Gamma_k(G)| - \binom{k}{2} \cdot 2^{2k}\). Note that we are using here that \(|\Gamma_k(G)| \geq |(V \times [2^{2k}]) \cup D| \geq \binom{k}{2} \cdot 2^{2k+1}\), so \(\left|\bigcup_{e \in E(C)} V_e\right| \leq |\Gamma_k(G)| - \binom{k}{2} \cdot 2^{2k}\).

Conversely, suppose that there exists a rank-\((k-1)\) perturbation \(\Gamma_k(G) + \widehat{\Gamma}\) of \(\Gamma_k(G)\) whose largest component has size at most \(|\Gamma_k(G)| - \binom{k}{2} \cdot 2^{2k}\). Note that \(2^p \geq 2^{2k+1}\) by construction so \(p \geq 2k+1 = 2(k-1) + 3\). By 9, some component \(K\) of \((\Gamma_k(G) + \widehat{\Gamma})[(V \times [2^{2k}]) \cup D]\) has size at least \(2^p - 2^{2k-1}\). Therefore, \(K\) intersects all sets \(V_v\) for \(v \in V(G)\). Let \(K'\) be the component of \(\Gamma_k(G) + \widehat{\Gamma}\) that contains \(K\). Then, \(K'\) misses at least \(\binom{k}{2} \cdot 2^{2k} - 2^{2k-1} > \left(\binom{k}{2} - 1\right) \cdot 2^{2k}\) vertices in \(\bigcup_{e \in E(G)}V_e\). Thus, \(K'\) must miss at least one vertex from at least \(\binom{k}{2}\) sets \(V_e\). Let \(F \subseteq E(G)\) be the set of all edges \(e \in E(G)\) such that \(K'\) misses at least one vertex from \(V_e\). Note that \(|F| \geq \binom{k}{2}\).

By contradiction, suppose that \(G[F]\) does not contain a clique of size \(k\). Let \(I_{G[F]}\) denote the vertex-edge incidence matrix of \(G[F]\). By [prop:find-Kk], we have \(\text{rk}(I_{G[F]}) \geq k\). Since \(K'\) intersects all sets \(V_v\) for \(v \in V(G)\) and misses at least one vertex from each set \(V_e\) for \(e \in F\), it follows that \(\widehat{\Gamma}\) contains the vertex-edge incidence graph of \(G[F]\) as a (bipartite) semi-induced subgraph. Thus, the adjacency matrix of \(\widehat{\Gamma}\) contains \(I_{G[F]}\) as a submatrix, so \(rk(\widehat{\Gamma}) \geq rk(I_{G[F]}) \geq k\), a contradiction. Therefore, \(G[F]\) contains a clique of size \(k\), so \(G\) contains a clique of size \(k\). ◻

Proof. Given an instance \((G, k)\) of clique, we construct the graph \(\Gamma_k(G)\), which has size \(|\Gamma_k(G)| \leq \max\{2n \cdot 2^{2k}, n \cdot 2^{2k} + \binom{k}{2} \cdot 2^{2k+2}\} + \binom{n}{2} \cdot 2^{2k}\), and consider the instance \((\Gamma_k(G), k-1)\) of rank integrity. By 13, the solution to this instance is at most \(|\Gamma_k(G)| - \binom{k}{2} \cdot 2^{2k}\) if and only if \(G\) contains a clique of size \(k\). ◻

Proof. First we prove that the \(1\)-ancilla-integrity of \(G\) is at most the claimed value. There are two cases. For the first case, suppose that the minimum is achieved by the graph \(G\) itself, and let \(S^* \subseteq V(G)\) be an optimal flip set of \(G\). Then \(G\) and \(G \circ S^*\) are \(1\)-perturbations of each other as we can add a vertex whose neighborhood is \(S^*\) to \(G\) and then locally complement and delete it to form \(G \circ S^*\). This finishes the first case.

Next suppose that the minimum is achieved by the graph \(G*u\) for some vertex \(u\) of \(G\), and let \(S^* \subseteq V(G)\) be an optimal flip set of \(G*u\). Let \(\widehat{G}\) be the graph which is obtained from \(G*u\) by adding a new vertex \(a\) whose neighborhood is \(S^*\). Then \(G\) is obtained from \(\widehat{G}\) by deleting \(a\) and then locally complementing on \(u\). Moreover, \((G*u) \circ S^*\) is obtained from \(\widehat{G}\) by locally complementing on \(a\) and then deleting \(a\). So \(G\) and \((G*u) \circ S^*\) are \(1\)-perturbations of each other, which finishes the second case.

It just remains to show that the claimed value is at most the \(1\)-ancilla-integrity of \(G\). So, consider a graph \(G^*\) which is a \(1\)-perturbation of \(G\) which minimizes the maximum component size. Thus there exists a graph \(\widehat{G}\) with one additional vertex so that both \(G\) and \(G^*\) are vertex-minors of \(\widehat{G}\). By locally complementing in \(\widehat{G}\), we may assume that \(G\) is an induced subgraph of \(\widehat{G}\), that is, there exists a vertex \(a\) so that \(G=\widehat{G}-a\). By 1, the graph \(G^*\) is a vertex-minor of at least one of the following three graphs:

1. the graph obtained from \(\widehat{G}\) by deleting \(a\),

2. the graph obtained from \(\widehat{G}\) by locally complementing at \(a\) and then deleting \(a\), or

3. the graph obtained from \(\widehat{G}\) by selecting an arbitrary neighbor \(u\) of \(a\), locally complementing on \(u\) then \(a\) then \(u\) again, and finally deleting \(a\).

In the first case, \(G^*=G\), which is trivially a flip of \(G\). In the second case, \(G^*\) is also a flip of \(G\), as desired. So we may assume that \(G^* = \widehat{G}*u*a*u-a\) for some neighbor \(u\) of \(a\).

Since locally complementing at \(u\) does not change the maximum component size of \(G^*\), it suffices to consider the graph \(\widehat{G}*u*a-a\). This graph is a flip of the graph \(G*u\), as desired. This completes the proof. ◻

Proof. Certainly the flip-integrity of \(G\) is at most the desired quantity since we can select \(S\) to be an optimal flip-set of \(C_1\). Also notice that the flip-integrity of \(G\) is at least the flip-integrity of \(C_1\) (or indeed, of any of its induced subgraphs). Thus it suffices to show that for any \(S \subseteq V(G)\), there exists a component of \(G \circ S\) of size at least \(|C_2|\).

Let \(S \subseteq V(G)\). If \(S\) does not contain any vertex of \(C_2\), then \(C_2\) is a component of \(G\circ S\), and we are done. So we may assume that there exists a vertex \(v\) which is in both \(S\) and \(C_2\). Now, let \(H_1, \ldots, H_t\) be the components of \(C_1 \circ (S \cap V(C_1))\). We may assume that \(t \geq 2\) since otherwise \(|H_1|= |C_1|\geq |C_2|\), and we are done. Since \(t \geq 2\), every component \(H_i\) contains a vertex \(v_i \in S\). Then \(v\) and \(v_i\) are adjacent in \(G \circ S\). It follows that all of the vertices of \(C_1\) are in the same component of \(G \circ S\). This completes the proof as \(|C_1| \geq |C_2|\). ◻

Proof. Let \(v\) be any vertex of \(G\), and let \(S\) be the set which contains \(v\) and all of its neighbors. Then \(v\) is isolated in \(G \circ S\), and so the largest component of \(G\circ S\) has size at most \(|G|-1\). ◻

Proof. Let \(G\) be a connected graph, and consider a set \(S\in \mathcal{S}_{\geq 3}(G)\) which minimizes, among all sets in \(\mathcal{S}_{\geq 3}(G)\), the maximum size of a component of \(G \circ S\). Let \(C_1, C_2, \cdots, C_r\) be the components of \(G \circ S\). Then in the original graph \(G\), for any vertices \(u \in C_i \cap S\) and \(v \in C_j \cap S\) where \(i\) and \(j\) are distinct, \(u\) and \(v\) must have been adjacent in \(G\). This is because there are no edges between \(u\) and \(v\) in \(G \circ S\) and these relationships have been flipped. A similar argument shows that for any vertices \(u \in C_i \setminus S\) and \(v \in C_j \setminus S\) where \(i\) and \(j\) are distinct, \(u\) and \(v\) are nonadjacent in \(G\).

Thus, since \(G \circ S\) has at least three components, \(G\) contains a triangle whose vertices \(x\), \(y\), and \(z\) are in three different components of \(G \circ S\). Notice that every vertex in \(S\) forms a triangle (in \(G\)) with at least two of the vertices from the triangle \(x, y, z\). In fact this characterizes \(S\); no vertex outside of \(S\) forms such a triangle in \(G\). So, by iterating through all triangles \(x,y,z\) in \(G\) and deriving the set \[\begin{align} \{u \in V(G) : u \text{ is in a triangle in G with at least two of the vertices }x,y,z\}, \end{align}\] we will consider all sets in \(\mathcal{S}_{\geq 3}(G)\) and thus find \(S\) (when \(S\) is non-empty). Note that we can also efficiently test whether a given set is in \(\mathcal{S}_{\geq 3}(G)\).

This procedure is summarized in Algorithm 3; we are done with the proof of correctness. In terms of time complexity, every graph with \(m\) edges has \(\mathcal{O}(m^{1.5})\) triangles [71]. For each triangle, we can compute the flip set \(S'\) in time \(\mathcal{O}(n^2)\). We can then compute \(G \circ S'\) and the size of its largest component in time \(\mathcal{O}(n^2)\) using Breadth-First Search (BFS). Therefore, the total time complexity is \(\mathcal{O}(m^{1.5}n^2)\). ◻

Proof. Given \(G\), we start by computing the split decomposition \(T\) of \(G\). This can be done in time \(\mathcal{O}(n^2)\) by 1. Note that \(T\) has \(\mathcal{O}(n)\) nodes by 19.

We view \(T\) as being rooted at an arbitrary node. Given a node \(x\) of \(T\), let \(d(x)\) denote the number of vertices of \(G\) which are a descendant of \(x\) in \(T\). First, by performing bottom-up dynamic programming on \(T\), we compute all values of \(d(x)\) in time \(\mathcal{O}(n^2)\). From there, we determine in time \(\mathcal{O}(n^2)\) the minimum width of a split of \(G\) induced by an edge of \(T\).

Now we consider all internal nodes \(x\) of \(T\) which are not prime in arbitrary order. Thus \(G_x\) is either a clique or a star, and all cuts of \(G_x\) are splits. Note that we can use the values of \(d(\cdot)\) to compute, for each vertex \(u\) of \(G_x\), how many vertices \(w(u)\) of \(G\) are in the subtree of \(T-x\) corresponding to \(u\). We would like to compute a partition of \(V(G_x)\) into two parts which minimizes the maximum weight of a part. Write \(V(G_x) = \{u_1, \ldots, u_{t}\}\). The problem we are trying to solve is an instance of weighted list balancing with \(m = 2\) and items \(u_1, \ldots, u_{t}\), each with weight \(w(u_i)\) and list \(L_i = \{1, 2\}\). By 5, this can be done in time \(\mathcal{O}(t \cdot n)\). In this manner, we compute the minimum width of a lift of a split of \(G_x\). Running this procedure on all internal nodes \(x\) of \(T\) takes time \(\mathcal{O}(n^2)\) by 19.

At this point, we have computed at most \(|I(T)| + 1 = \mathcal{O}(n)\) widths of splits of \(G\) (including minimum width of a split of \(G\) induced by an edge of \(T\)). We simply return the minimum among all of them. The correctness follows immediately from 18. ◻

Proof. By 14, we can compute the \(1\)-ancilla integrity of an \(n\)-vertex graph by \(n+1\) instances of computing the flip-integrity of an \(n\)-vertex graph. So in this step we gain an extra factor of \(n\). Now we consider computing the flip-integrity of an \(n\)-vertex graph \(G\).

By 15, it suffices to compute the flip-integrity of the largest component \(H\) of \(G\). We now apply the algorithms in 17 and [thm:compute-most-balanced-split] to \(H\). Thus, in time \(\mathcal{O}(n^5)\), we find a set \(S \in \mathcal{S}_{\geq 3}(H)\) which minimizes the maximum size of a component of \(H \circ S\). We also find a most balanced split \((A,B)\) of \(H\) in time \(\mathcal{O}(n^2)\). Let \(S'\) be the set of all vertices in \(A\) which have a neighbor in \(B\) and all vertices in \(B\) which have a neighbor in \(A\). We return the minimum maximum component size of the two graphs \(H \circ S\) and \(H \circ S'\).

Now, consider an optimal flip set \(S^*\) of \(H\). Note that \(H \circ S^*\) has at least two components by 16. If \(H \circ S^*\) has at least three components, then we have found a flip which is at least as good since we considered \(H \circ S\). If \(H \circ S^*\) has exactly two components, we let \(A^*\) and \(B^*\) denote their vertex sets. Then \((A^*, B^*)\) is a split of \(H\), and so it has width at least the width of \((A,B)\). This means that \(\max(|A|, |B|)\leq \max(|A^*|, |B^*|)\). Thus we have found a flip which is at least as good since every component of \(H \circ S'\) has size at most \(\max(|A|, |B|)\). This completes the proof of [thm:ancillaVuln]. ◻