The problem of searching for a Hamiltonian cycle or path is fundamental in graph theory and useful in modelling real-life problems. Electronic circuit design, job scheduling, and sequencing of DNA chains are just a few examples of such an application. In its decision version, the problem for directed or undirected graphs belongs to the NP-complete class of computationally hard problems. As the problem is regularly used, a lot of effort was put into designing more and more efficient algorithms (see, e.g., Jäger and Zhang, 2010; Björklund, 2014). On a more theoretical ground, research was directed toward proving polynomial-time solvability of Hamiltonicity for subsequent classes of graphs. There are many works related to the problem in undirected graphs (see surveys of Gould, 1991; Gross et al., 2013), its directed version was not so extensively studied (e.g., Favaron and Ordaz, 1986; Bang-Jensen and Gutin, 1999).

In the paper, superclasses of (directed) quasi-adjoint graphs are defined and proven to have a polynomial-time solution of the Hamiltonian cycle problem and, partially, the Hamiltonian path problem. Section 2 introduces necessary definitions and summarizes previous work, Section 3 contains theoretical results including algorithms, and a conclusion is given in Section 4.

The following statements refer to directed graphs with, in general, loops and multiple arcs accepted. Throughout the paper, standard terminology from graph theory is used, see, e.g. Berge (1973). Let V stand for the set of vertices of a graph G = ( V , A ), and A for its set of arcs. The Hamiltonian cycle (path) in G is a directed cycle (path) including every vertex v ∈ V exactly once; the Eulerian cycle (path) is a directed cycle (path) including every arc a ∈ A exactly once. Transpose graph G T = ( V , A ′ ) of a digraph G = ( V , A ) has ( u , v ) ∈ A ′ if and only if ( v , u ) ∈ A.

The problem of searching for a Hamiltonian cycle or a Hamiltonian path is NP-hard even if all vertices in a digraph have their indegree and outdegree not exceeding 2 (Garey and Johnson, 1979). It is solvable in polynomial time when restricted to special subclasses of digraphs, for example, acyclic digraphs (Lawler, 1976), directed line graphs (Kasteleyn, 1963), or specific variations of dense digraphs (Bang-Jensen and Gutin, 2002).

A directed line graph is a 1-graph (a graph with no multiple arcs) where the following holds for all pairs u , v of its vertices: N + ( u ) ∩ N + ( v ) ≠ ∅ ⇒ N + ( u ) = N + ( v ) ∧ N − ( u ) ∩ N − ( v ) = ∅ , where N + ( u ) is the set of (direct) successors of vertex u and N − ( u ) is the set of its (direct) predecessors (Blazewicz et al., 1999). As defined in Berge (1973) in the context of directed graphs, adjoint G = ( V , A ) of a graph H = ( U , V ) is a 1-graph whose vertices represent arcs of H and in which ( u , v ) ∈ A if and only if the head of arc u is the tail of arc v in H. H is not necessarily a 1-graph. If H is a 1-graph, its adjoint G is a directed line graph (Blazewicz et al., 1999). 1-graph G is an adjoint if and only if the following property is satisfied for all u , v ∈ V (Berge, 1973): N + ( u ) ∩ N + ( v ) ≠ ∅ ⇒ N + ( u ) = N + ( v ) . The relation between vertices of adjoint G and arcs of the corresponding graph H leads to the polynomial-time solvability of the Hamiltonian cycle and path problems in adjoints. There is a Hamiltonian cycle (path) in graph G if and only if graph H contains an Eulerian cycle (path) (Blazewicz et al., 1999), this property follows from the definitions. Such a conversion of problems is not possible for analogous situation of an undirected line graph and its corresponding graph (Bertossi, 1981).

Adjoints have this useful property because of the vertex-arc relation with their graphs H, and a question arose whether this class could be widened. In 2008, its superclass of quasi-adjoint graphs was defined and a polynomial-time exact algorithm solving the Hamiltonian cycle problem was provided (Blazewicz et al., 2008). Digraph G is a quasi-adjoint graph if and only if, for all u , v ∈ V, the following property holds: N + ( u ) ∩ N + ( v ) ≠ ∅ ⇒ N + ( u ) = N + ( v ) ∨ N + ( u ) ⊂ N + ( v ) ∨ N + ( v ) ⊂ N + ( u ) . Quasi-adjoint graphs, unlike adjoints, can be multigraphs. They are a superclass of, among others, digraphs modelling a bioinformatical problem of isothermic DNA sequencing by hybridization, which are 1-graphs intersecting the class of adjoints (Blazewicz et al., 2004; Blazewicz and Kasprzak, 2006). (For more relations of quasi-adjoint graphs and adjoints with other classes of digraphs, see the systematization made in Blazewicz and Kasprzak (2012) and Kasprzak (2018).) The recognition whether a graph is a quasi-adjoint graph can be done in O ( n 3 ) time, and the exact algorithm solving the Hamiltonian cycle problem within it works in O ( n 2 + m 2 ) time, where n is the number of its vertices and m the number of arcs (Blazewicz et al., 2008). The algorithm also uses a transformation of a graph G into the corresponding graph H, but this time it is more complicated and includes insertion of extra structures. There, the numbers of vertices before the transformation and arcs after the transformation differ, nevertheless, the correspondence between the Hamiltonian and Eulerian cycles is preserved. This algorithm can be easily adjusted to solve the Hamiltonian path problem (Kasprzak, 2018).

The considered class of polynomially solvable instances of the Hamiltonian cycle/path problem can be further extended. The simplest extension is to add to quasi-adjoint graphs their counterparts with the adjacency matrix transposed. Obviously, digraph G has a Hamiltonian cycle/path if and only if its transposed counterpart G T has (see an example in Fig. 1). Adjoints are digraphs whose membership in this class does not change after the transposition, however, it is not the case of quasi-adjoint graphs. Let G a be the class of adjoints, and G q the class of quasi-adjoint graphs.

The following extension of the quasi-adjoint graphs takes into account the above property. Let G ′ be the class of digraphs where the following holds for all u , v ∈ V: (3.1) N + ( u ) ∩ N + ( v ) ≠ ∅ ⇒ | ⋃ z ∈ Z N − ( z ) | ⩽ | Z | , where Z = N + ( u ) ∖ N + ( v ) or Z = N + ( v ) ∖ N + ( u ) (a choice made independently for each pair u , v toward satisfying the clause). Analogously, let G ″ be the class of digraphs with the property (3.2) N − ( u ) ∩ N − ( v ) ≠ ∅ ⇒ | ⋃ z ∈ Z N + ( z ) | ⩽ | Z | satisfied for all u , v ∈ V, where Z = N − ( u ) ∖ N − ( v ) or Z = N − ( v ) ∖ N − ( u ).

The joint class G ′ ∪ G ″ is interesting in such a sense that its elements are polynomially solvable instances of the Hamiltonian cycle problem. It should be noticed that these graphs can bring the positive, as well as the negative answer to the problem. The recognition whether a graph belongs to this class can be done in O ( n 4 ) time (clause (3.1) or (3.2) checked in O ( n 2 ) time for all pairs of vertices).

If graph G has m significantly greater than n 2 , we can simply reduce the overall time complexity by analysing its underlying 1-graph.

As we see, the algorithms for recognizing graphs from G ′ ∪ G ″ and for solving the Hamiltonian cycle problem in these graphs are of the same computational complexity as the algorithm solving the problem in quasi-adjoint graphs. Keeping the same complexity function, we can further extend the class of polynomially solvable instances of the problem. The reduction made by the procedure from the proof of Theorem 2 for a pair of vertices can make another pair consistent with the condition for G ′ or G ″ . Therefore, some graphs outside G ′ ∪ G ″ may, after the reduction, become members of this class. An example of such a situation is shown in Fig. 2(B).

Precisely, the reduction from the proof of Theorem 2 in the case of a graph outside G ′ ∪ G ″ can be applied to these pairs of its vertices that fulfill the appropriate condition (either for G ′ or G ″ , see the caption of Fig. 2(B)). However, the reduction can be naturally extended as in Algorithm 1.

By re-running the algorithm, one increases its efficiency as new pairs of vertices can meet the required criteria. If the number of runs is constant, the complexity function does not grow. If one decides to re-run the algorithm as long as there are some reductions made, the number of runs is upper bounded by O ( m ).

Another observation led to a further extension of the considered classes. If, among all successors (resp. predecessors) of a pair of vertices, there is one with a unique predecessor (resp. successor), it binds in any Hamiltonian cycle its predecessor (resp. successor). Such a case can be added to the clauses defining G q , { G : G T ∈ G q }, G ′ , and G ″ without changing their property of polynomial-time solvability of the Hamiltonian cycle problem. Let G ′ ∗ be a class of digraphs having the following property satisfied for all u , v ∈ V: (3.3) N + ( u ) ∩ N + ( v ) ≠ ∅ ⇒ | ⋃ z ∈ Z N − ( z ) | ⩽ | Z | ∨ min y ∈ Y { N − ( y ) } = 1 , where Z = N + ( u ) ∖ N + ( v ) or Z = N + ( v ) ∖ N + ( u ) (a choice made independently for each pair u , v toward satisfying the clause) and Y = N + ( u ) ∪ N + ( v ). Let G ″ ∗ be a class of digraphs with the following property satisfied for all u , v ∈ V: (3.4) N − ( u ) ∩ N − ( v ) ≠ ∅ ⇒ | ⋃ z ∈ Z N + ( z ) | ⩽ | Z | ∨ min y ∈ Y { N + ( y ) } = 1 , where Z = N − ( u ) ∖ N − ( v ) or Z = N − ( v ) ∖ N − ( u ) and Y = N − ( u ) ∪ N − ( v ).

It should be noticed that the example graph from Fig. 2(B) does not belong to any of the classes G ′ , G ″ , G ′ ∗ , G ″ ∗ , but can be reduced to be a member of any of them by Algorithm 1 run once or the procedure from the proof of Theorem 2. It shows potential wide applicability of the approach proposed here.

When solving the Hamiltonian path problem in graphs from class G ′ ∪ G ″ , one encounters a complication. A natural approach consisting in running O ( n 2 ) times an algorithm for the Hamiltonian cycle problem, with successive pairs of vertices assumed as the ends of the path and their connection fixed in the cycle, cannot be easily applied here. It works for quasi-adjoint graphs, where, after the appropriate modification, a graph still belongs to this class (Kasprzak, 2018). Here, the addition of the arc from the last to the first vertex, accompanied by the removal of some arcs or not, can make the graph no longer an element of G ′ ∪ G ″ .

Let a be the assumed beginning of the path, b its end, and the added arc be ( b , a ) (not present in the initial graph). The complication is for the cases where, for a pair u , v, clause (3.1) or (3.2) was fulfilled with | ⋃ z ∈ Z N − ( z ) | = | Z | or | ⋃ z ∈ Z N + ( z ) | = | Z |, respectively, and a or b supplied one of the sides of these equations. Whether the arcs initially entering a/leaving b (or both) will be removed or not, the pair u , v can lose the required property. Therefore, the case of the Hamiltonian path in the considered classes (also G ′ ∗ and G ″ ∗ ) needs a special treatment, including such exceptions. The algorithm from the proof of Theorem 2 could be used directly to these elements of the classes, supplemented by arc ( b , a ), that are not such problematic instances.

Until now, the quasi-adjoint graphs were the widest class of digraphs proven to have a polynomial-time solution of the Hamiltonian cycle and path problems based on the transformation of graphs G into H. The extended classes of digraphs defined in the paper add new cases to this class. In addition, the reduction of arcs being a part of the proposed algorithms can function standalone and can be applied to digraphs outside the classes, possibly resulting in polynomial-time solutions for them.

The case of the Hamiltonian path has a more complicated solution because of the underlying assumptions in the definitions of the classes. Research on the algorithm for this problem could especially benefit, as the Hamiltonian path model is willingly used for real-life problems. As one of the current applications, the computational part of the process of genome assembly can be given, modelled, among others, as searching for variants of such a path (Swat et al., 2021).