2026/05/13 by Amir Nikabadi, Eva Rotenberg, Lasse Wulf · 1 voice
Computer Science · #cs.DM #cs.CC
When a graph G admits a vertex v that is contained in all its longest paths, we call v a Gallai vertex. These are named after Gallai, who in 1966 asked the question if it is true that every connected graph contains such a vertex. This was soon answered in the negative by Walther and Zamfirescu, who presented a graph in which every vertex is omitted by some longest path of the graph. In spite of its long history, the Gallai Vertex Problem, i.e. determining whether a graph has a Gallai vertex, was until now neither known to be NP- nor co-NP-hard. In this work, we show something much stronger, as we completely settle the computational complexity of determining whether a graph has a Gallai vertex: we show that it is complete for the complexity class Θ2p = PNP[log n]. This class, also known as parallel access to NP, is a complexity class larger than NP situated just below the class Σp2 in Stockmeyer's polynomial hierarchy. In more generality, the longest path transversal number of a connected graph is the minimum size of a set of vertices that intersects all its longest paths. I.e. if the graph has a Gallai vertex, its longest path transversal number is 1. Thus, as a consequence of our theorem, the longest path transversal number of a graph cannot be approximated in polynomial time by a factor better than 2, unless P = NP. In fact, using related techniques, we show a strengthening of this result: For any constant C, if there is a graph with longest path transversal number C, then there is no polynomial time algorithm for approximating the longest path transversal number by a factor better than C, unless P = NP. In particular, this excludes approximation by a factor below 3. Similar results hold for the longest cycle transversal.