BARC talk by Andreas Björklund: Another Hamiltonian Cycle in Bipartite Pfaffian Graphs

Abstract:

Finding a Hamiltonian cycle in a given graph is computationally challenging, and in general remains so even when one is further given one Hamiltonian cycle in the graph and asked to find another. In fact, no significantly faster algorithms are known for finding another Hamiltonian cycle than for finding a first one even in the setting where another Hamiltonian cycle is structurally guaranteed to exist, such as for odd-degree graphs. We identify a graph class—the bipartite Pfaffian graphs of minimum degree three—where it is NP-complete to decide whether a given graph in the class is Hamiltonian, but when presented with a Hamiltonian cycle as part of the input, another Hamiltonian cycle can be found efficiently.

We prove that Thomason’s lollipop method [Ann. Discrete Math., 1978], a well-known algorithm for finding another Hamiltonian cycle, runs in linear time in cubic bipartite Pfaffian graphs. This was conjectured for cubic bipartite planar graphs by Haddadan [MSc thesis, Waterloo, 2015]; in contrast, examples are known of both cubic bipartite graphs and cubic planar graphs where the lollipop method takes exponential time.

Beyond the lollipop method, we address a slightly more general graph class and present two algorithms, one running in linear-time and one operating in logarithmic space, that take as input (i) a bipartite Pfaffian graph G of minimum degree three, (ii) a Hamiltonian cycle H in G, and (iii) an edge e in H, and output at least three other Hamiltonian cycles through the edge e in G.

We also present further improved algorithms for finding optimal traveling salesperson tours and counting Hamiltonian cycles in bipartite planar graphs with running times that are not known to hold in general planar graphs.

We prove our results by a new structural technique that efficiently witnesses each Hamiltonian cycle H through an arbitrary fixed anchor edge e in a bipartite Pfaffian graph using a two-coloring of the vertices as advice that is unique to H. Previous techniques—the Cut&Count technique of Cygan, Nederlof, Pilipczuk, Pilipczuk, Van Rooij, and Wojtaszczyk [FOCS’11, TALG’22] in particular—were able to reduce the Hamiltonian cycle problem only to essentially counting problems; our results show that counting can be avoided by leveraging properties of bipartite Pfaffian graphs. Our technique also has purely graph-theoretical consequences; for example, we show that every cubic bipartite Pfaffian graph has either zero or at least six distinct Hamiltonian cycles; the latter case is tight for the cube graph.

The talk is based on joint work with Petteri Kaski and Jesper Nederlof.