# A Quasi-Hole Detection Algorithm for Recognizing \(k\)-Distance-Hereditary Graphs, with \(k<2\)
## 5 Recognition Algorithm
### Quasi-Hole Detection Algorithm  
We call _quasi-hole_ any cycle \(C_{k}\) such that \(k\geq 5\) and \(cd(C_{k})\leq 1\). In what follows, we show that the hole-detection algorithms recalled in Theorem 7 and Corollary 1 can be adapted to detect quasi-holes in any connected graph \(G\). This adapted version is called QuasiHoleDetection and it is described in pseudo-code as shown in Algorithms 1 and 2. The strategy behind QuasiHoleDetection is based on the following result:  
**Lemma 5**. : _A connected graph \(G\) contains a quasi-hole if and only if there exists a cycle \((v_{0},v_{1},\dots,v_{\ell})\), \(\ell\geq 4\), in \(G\) such that each path \((v_{i},v_{i+1},v_{i+2},v_{i+3})\), \(i=1,\dots,\ell-3\), is a \(P_{4}\) of \(G\)._  
Proof. : \((\Rightarrow)\) If \(G\) contains a quasi-hole \(C_{k}\) then the vertices of \(C_{k}\) form a cycle fulfilling the conditions of the statement (where \(v_{0}\) is the only vertex incident to possible chords of the cycle). \((\Leftarrow)\) Suppose that \(G\) admits cycles as described in the statement, and let \(C=(v_{0},v_{1},\dots,v_{\ell})\) be _the shortest_ among such cycles. We now show that \((i)\)\(C\) has at least \(5\) vertices and \((ii)\)\(cd(C)\leq 1\):  
\((i)\) Since \(C\) fulfills the conditions of the statement, then \(C\) contains at least \(5\) vertices;  
\((ii)\) Suppose by contradiction that \(cd(C)>1\). Then, there must exist chords \((v_{i},v_{j})\) with both \(v_{i}\) and \(v_{j}\) different from \(v_{0}\). To each chord \((v_{i},v_{j})\) not incident on \(v_{0}\), we associatea \"length\" defined as \(\textit{length}(v_{l},v_{j})=|j-i|\). Now, let \((v_{l},v_{r})\), with \(l<r\), be a chord with minimum length. By definition, \(0<l<r\leq\ell\) holds. Since \((v_{l},v_{l+1},v_{l+2},v_{l+3})\) is a \(P_{4}\), then \(r\geq l+4\), and hence \(C^{\prime}=(v_{l},v_{l+1},\ldots,v_{r})\) results to be a cycle with at least 5 vertices. Moreover, between \(v_{l}\) and \(v_{j}\), for each \(l\leq i<i+2\leq j\leq r\), \((i,j)\
eq(l,r)\), cannot exist an edge, otherwise it would be a chord with length smaller than \(\textit{length}(v_{l},v_{r})\). Since \(C^{\prime}\) is a cycle with at least 5 vertices and with chord distance zero, then it contradicts the fact that \(C\) is the shortest among the cycles fulfilling the conditions of the statement. Hence, \(cd(C)\leq 1\). Since both the properties at points \((i)\) and \((ii)\) hold, it follows that \(C\) is a quasi-hole. ```
Algorithm:QuasiHoleDetection Input:a connected undirected graph \(G=(V,E)\) Output:\"true\" if \(G\) contains a quasi-hole, \"false\" otherwise. 1 calculate the adjacency matrix \(M[\,]\) of \(G\) ;
2 foreach\(v_{1}\in V\)do
3 set each entry of the arrays \(\textit{walked\_P}_{3}[\,]\) and \(AP[\,]\) to 0;
4\(\textit{base}\gets v_{1}\);
5\(\textit{AP}[v_{1}]\gets 1\);
6 foreach\((v_{2},v_{3})\in E\)do
7 if\((v_{1},v_{2})\in E\)and \(v_{1}\
eq v_{3}\)then
8\(\textit{AP}[v_{2}]\gets 1\);
9\(\texttt{Visit}(\textit{base},v_{1},v_{2},v_{3})\);
10\(\textit{AP}[v_{2}]\gets 0\);
11 end if
12 if\((v_{1},v_{3})\in E\)and \(v_{1}\
eq v_{2}\)then
13\(\textit{AP}[v_{3}]\gets 1\);
14\(\texttt{Visit}(\textit{base},v_{1},v_{3},v_{2})\);
15\(\textit{AP}[v_{3}]\gets 0\);
16
17 end if
18\(\textit{AP}[v_{1}]\gets 0\);
19
20 end for
21 print \"false\". ```  
**Algorithm 1**A quasi-hole detection algorithm. The above lemma is used by the provided algorithm for the detection of quasi-holes in \(G\). To this end, we associate to \(G\) a directed graph \(G^{+}\) defined as follows:  
* \(\{v_{abc}\mid(a,b,c)\) _is a_ \(P_{3}\) _in the graph_ \(G\}\) is the vertex set of \(G^{+}\);
* \(\{(v_{abc},v_{bcd})\mid(a,b,c,d)\) _is a_ \(P_{4}\) _in the graph_ \(G\}\) is the edge set of \(G^{+}\). If \((a,b,c)\) is a path \(P_{3}\) of \(G\), then both the vertices \(v_{abc}\) and \(v_{cba}\) belong to \(G^{+}\). In a similar way, if \((a,b,c,d)\) is a path \(P_{4}\) of \(G\), then the edges \((v_{abc},v_{bcd})\) and \((v_{dcb},v_{cba})\) must be contained in \(G^{+}\).