The Gallai Vertex Problem is ${\Theta }_2^p$-Complete

Amir Nikabadi, Eva Rotenberg, Lasse Wulf

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…