Study on Hamiltonian Graphs Excelled in Italy

The IWOCA (International Workshop on Combinatorial Algorithms) conference annually gathers researchers who design algorithms for various combinatorial problems that underpin computer applications in science, engineering, and business. At the 35th year of the conference, held in early July on the Italian island of Ischia, Matfyz PhD student Nikola Jedličková represented Matfyz. She shared insights from her paper On the Structure of Hamiltonian Graphs with Small Independence Number, co-authored by her advisor Prof. Jan Kratochvíl.

The award-winning publication provides a structural description of situations in which „dense graphs do not contain the so-called Hamiltonian path.” „A Hamiltonian path passes through all vertices in a graph exactly once. In other words, it is the most efficient way to connect all vertices of the graph into a continuous walk,“ the authors explain. Not every graph allows for such a connection, and for general graphs, the question of the existence of a Hamiltonian path is effectively unsolvable (known as NP-complete). „Our previous result shows that for dense graphs (measured by the maximum number of vertices amongst which there are no edges, known as the graph's independence), the existence of a Hamiltonian path can be decided in polynomial time. This was previously unknown even for graphs with an independence number of 3. In the awarded paper, we supplemented these polynomial algorithms with an explicit description of forbidden situations for graphs with independence numbers 2, 3, and 4.“