# A Quasi-Hole Detection Algorithm for Recognizing \(k\)-Distance-Hereditary Graphs, with \(k<2\)
## 5 Recognition Algorithm
### Detecting Quasi-Hole on at Least \(k\) Vertices  
As in [15], the strategy described above to define a quasi-hole detection algorithm can be generalized to built algorithms for the detection of quasi-holes on at least \(k\) vertices, with \(k\geq 5\). For any input graph \(G\), we consider the following family of directed graphs \(G^{(t)}\):  
* \(\{v_{u_{1}u_{2}\cdots u_{t-1}}\mid(u_{1},u_{2},\ldots,u_{t-1})\) _is an induced path_ \(P_{t-1}\) in \(G\}\) is the vertex set of \(G^{(t)}\),
* \(\{(v_{u_{1}u_{2}\cdots u_{t-1}},v_{u_{2}u_{3}\cdots u_{t}})\mid(u_{1},u_{2}, \ldots,u_{t})\) _is an induced path_ \(P_{t}\) in \(G\}\) is the edge set of \(G^{(t)}\).  
By definition, \(G\equiv G^{(2)}\) and \(G^{+}\equiv G^{(4)}\) where \(G^{+}\) is the direct graph associated to \(G\) in Section 5.2. Therefore, in the same way that running DFS on \(G^{+}\equiv G^{(4)}\) allowed us to detect quasi-holes (on at least five vertices), running DFS on \(G^{(k-1)}\) allows us to detect (extended) quasi-holes on at least \(k\) vertices, for each constant \(k\geq 5\). This is ensured by the following statement, which represents a generalization of Lemma 5:  
**Lemma 7**.: _Given a constant \(k\geq 5\), a graph \(G\) contains a quasi-hole on at least \(k\) vertices if and only if \(G\) contains a cycle \((u_{0},u_{1},\ldots,u_{t})\), with \(t\geq k-1\), such that \((u_{i},u_{i+1},\ldots,u_{i+k-2})\) is an induced path \(P_{k-1}\) of \(G\) for each \(i=1,2,\ldots,t-k+2\)._  
Lemmas 6 and 7 induce the following statement:  
**Corollary 2**.: _Let \(G\) be a connected graph and let \(k\geq 5\) be a constant. Assume that a DFS is executed on \(G^{(k-1)}\), the directed graph associated to \(G\). If the active path computed by the DFS is \(v_{u_{0}u_{1}\cdots u_{k-3}},v_{u_{1}u_{2}\cdots u_{k-2}},\ldots,v_{u_{r-k+3} },v_{r-k+4}\cdots u_{r}\), where \(u_{i}\
eq u_{j}\) for all \(0\leq i<j<r\), and \(u_{r}=u_{p}\) for some \(p\) such that \(0\leq p<r\), then \(u_{p},u_{p+1},\ldots,u_{r-1}\) are vertices forming a cycle in \(G\) that fulfill the conditions of Lemma 7. Conversely, if \(G\) contains a quasi-hole on at least \(k\) vertices, the DFS on \(G^{(k-1)}\) will meet a sequence of vertices whose associated \(P_{k-2^{5}}\) in \(G\) form a path as the path \((u_{1},u_{2},\ldots,u_{t})\) in the cycle of Lemma 7._  
Additionally, in this situation we do not build \(G^{(k-1)}\) since we implicitly run DFS on this associated graph. In particular, we process each unvisited \(P_{k-2}\) of \(G\) as follows: we try to extend the induced path \(P_{k-2}\) formed by \((u_{0},u_{1},\ldots,u_{k-3})\) into \(P_{k-1}\)s of the form \((u_{0},u_{1},\ldots,u_{k-3},u_{k-2})\); then, for each such \(P_{k-1}\), we proceed by extending the \(P_{k-2}\)\((u_{1},u_{2},\ldots,u_{k-2})\) into \(P_{k-1}\)s, and so on. Since there exist \(O(m^{2})\) induced paths on \(2a\) vertices and \(O(nm^{4})\) on \(2a+1\) vertices, and it requires \(O(k)\) time to detect whether a vertex extends a \(P_{k-1}\) into a \(P_{k}\), we have the following corollary:  
**Corollary 3**.: _Let \(G=(V,E)\) be a connected graph with \(|V|=n\) and \(|E|=m\), and let \(k\geq 5\) be a constant. By implicitly running DFS on \(G^{(k-1)}\) it is possible to detect whether \(G\) contains a quasi-hole on at least \(k\) vertices in \(O(n^{2}m^{p-1})\) time when \(k=2p\), and in \(O(n^{2}+nm^{p})\) time when \(k=2p+1\)._  
The space required is \(O(m^{p-1})\) when \(k=2p\), and \(O(nm^{p-1})\) when \(k=2p+1\). According to Lemma 4 and Corollary 3, we finally get the following result:  
**Theorem 9**.: _Let \(G=(V,E)\) be a connected graph with \(|V|=n\) and \(|E|=m\). It is possible to recognize whether \(G\in\operatorname{sDH}(2)\) in \(O(n^{2}m^{2})\) time and \(O(m^{2})\) space._