{'fraction_non_alphanumeric': 0.029045643153526972, 'fraction_numerical': 0.0, 'mean_word_length': 4.2846715328467155, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Polynomial algorithms for finding paths and cycles in quasi-transitive digraphs

A digraph D is called quasi-transitive if for any triple x, y, z of distinct vertices of D such that (x, y) and (y, z) are arcs of D there is at least one arc from x to z or from z to x. A minimum path factor of a digraph D is a collection of the minimum number of pairwise vertex disjoint paths covering the vertices of D. J. Bang-Jensen and J. Huang conjectured that there exist polynomial algorithms for the Hamiltonian path and cycle problems for quasi-transitive digraphs. We solve this conjecture by describing polynomial algorithms for finding a minimum path factor and a Hamiltonian cycle (if it exists) in a quasi-transitive digraph.