pith. sign in

arxiv: 2605.13488 · v1 · pith:G634POW4new · submitted 2026-05-13 · 💻 cs.DM · cs.CC

The Gallai Vertex Problem is Theta₂^p-Complete

Amir Nikabadi , Eva Rotenberg , Lasse Wulf This is my paper

Pith reviewed 2026-05-14 18:21 UTC · model grok-4.3

classification 💻 cs.DM cs.CC
keywords Gallai vertexlongest pathΘ₂^p-completenesslongest path transversalapproximation hardnessNP queriesgraph complexitylongest cycle
4
0 comments X

The pith

Deciding whether a graph has a vertex on all its longest paths is complete for the class Θ₂^p.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the Gallai Vertex Problem—deciding if a connected graph has a vertex contained in every longest path—is Θ₂^p-complete. This class consists of problems solvable in polynomial time using a logarithmic number of parallel queries to an NP oracle, placing the problem above NP but below Σ₂^p in the polynomial hierarchy. The result also yields inapproximability for the smallest set of vertices intersecting all longest paths, showing that no polynomial-time algorithm can achieve a ratio better than 2 unless P equals NP, with a strengthening to any fixed constant ratio.

Core claim

We prove that the Gallai Vertex Problem is Θ₂^p-complete via a polynomial-time reduction from a known complete problem for the class. Consequently the longest-path transversal number—the minimum size of a vertex set hitting all longest paths—cannot be approximated in polynomial time within a factor better than 2 unless P=NP. For any constant C, if graphs with transversal number C exist then no polynomial-time algorithm approximates the number to a factor better than C unless P=NP; analogous statements hold for longest-cycle transversals.

What carries the argument

A polynomial-time reduction from a known Θ₂^p-complete problem to the Gallai Vertex Problem that maps yes-instances to graphs possessing a vertex common to all longest paths and no-instances to graphs lacking such a vertex.

If this is right

  • The longest-path transversal number admits no polynomial-time approximation algorithm with ratio better than 2 unless P=NP.
  • For any fixed constant C, the longest-path transversal number admits no polynomial-time approximation with ratio better than C unless P=NP.
  • The same inapproximability statements hold for the longest-cycle transversal number.
  • A graph has longest-path transversal number 1 precisely when it possesses a Gallai vertex.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The exact placement in Θ₂^p suggests that any practical exact algorithm would need to orchestrate a logarithmic number of NP-subproblem calls in parallel rather than sequential adaptive queries.
  • Similar reduction patterns may classify related minimum hitting-set problems for longest structures in directed graphs or hypergraphs at the same complexity level.
  • The constant-factor inapproximability implies that any heuristic for computing small transversals on large graphs must accept linear-factor error on some infinite family of instances.

Load-bearing premise

The reduction from the known Θ₂^p-complete problem correctly preserves yes and no answers for the existence of a Gallai vertex and runs in polynomial time.

What would settle it

A polynomial-time algorithm that decides the Gallai Vertex Problem using o(log n) adaptive or parallel queries to an NP oracle on worst-case instances would separate the problem from Θ₂^p-completeness.

read the original abstract

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 $\Theta_2^p = \text{P}^{\text{NP}[\log n]}$. This class, also known as parallel access to NP, is a complexity class larger than NP situated just below the class $\Sigma^p_2$ 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 $\text{P} = \text{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 $\text{P} = \text{NP}$. In particular, this excludes approximation by a factor below $3$. Similar results hold for the longest cycle transversal.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript proves that the Gallai Vertex Problem—deciding whether a connected graph has a vertex contained in every longest path—is complete for Θ₂^p = P^{NP[log n]}. The proof proceeds by a polynomial-time many-one reduction from a known Θ₂^p-complete problem. As a consequence, the longest-path transversal number cannot be approximated to within any constant factor C (for graphs whose transversal number is C) unless P=NP; analogous results are stated for longest-cycle transversals.

Significance. If the reduction is correct, the result is significant: it places a natural, long-studied graph-theoretic decision problem precisely in the polynomial hierarchy (between NP and Σ₂^p) and yields tight inapproximability for the longest-path transversal number. The paper also supplies a strengthening that rules out approximation factors below any fixed C when such graphs exist.

major comments (1)
  1. [main reduction (proof of Theorem 1)] The Θ₂^p-hardness proof (main reduction, presumably §4): the gadget construction must guarantee that every longest path in the constructed graph G' intersects the designated vertex set if and only if the source instance is a yes-instance, without creating spurious longer paths or changing the transversal number. The manuscript should supply an explicit calculation of the longest-path length in G' (including all gadget attachments) to confirm that the reduction preserves yes/no instances.
minor comments (1)
  1. [Abstract] The abstract and introduction should include a one-sentence sketch of the reduction technique (e.g., which canonical Θ₂^p-complete problem is used and the high-level idea of the Gallai-forcing gadgets) to help readers assess the claim before reading the full proof.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the constructive major comment. We address it directly below.

read point-by-point responses

  1. Referee: [main reduction (proof of Theorem 1)] The Θ₂^p-hardness proof (main reduction, presumably §4): the gadget construction must guarantee that every longest path in the constructed graph G' intersects the designated vertex set if and only if the source instance is a yes-instance, without creating spurious longer paths or changing the transversal number. The manuscript should supply an explicit calculation of the longest-path length in G' (including all gadget attachments) to confirm that the reduction preserves yes/no instances.

    Authors: We agree that an explicit calculation of the longest-path length in the constructed graph G' would improve the transparency of the argument. While the existing proof establishes by construction that each gadget admits no path longer than the base longest-path length of the source instance (and that attachments are made only at designated vertices without extending any path beyond this bound), we acknowledge that spelling out the global longest-path length explicitly would eliminate any residual doubt about spurious paths. In the revised manuscript we will insert a dedicated lemma (placed immediately after the gadget definitions) that computes this length by enumerating the possible cases: paths that remain entirely within the source graph, paths that traverse one or more gadgets, and paths that combine source edges with gadget edges. The calculation will show that the maximum length remains exactly equal to the source longest-path length plus a fixed additive constant independent of the yes/no status, and that any longest path in G' must intersect the designated vertex set precisely when the source instance is a yes-instance. This addition does not alter the correctness of the reduction but directly addresses the request for verification. revision: yes

Circularity Check

0 steps flagged

Direct reduction from known Θ₂^p-complete problem; no circularity

full rationale

The paper establishes Θ₂^p-completeness of the Gallai Vertex Problem via membership in the class (standard oracle access) plus a polynomial-time many-one reduction from a previously known Θ₂^p-complete problem. No step defines the target property in terms of itself, renames a fitted quantity as a prediction, or relies on a load-bearing self-citation whose cited result is itself unverified. The derivation chain is therefore independent of the target result and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof relies on standard definitions of paths, longest paths, and polynomial reductions together with the known Θ₂^p-completeness of a base problem; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)
  • standard math Standard graph-theoretic definitions of paths and longest paths
    Invoked in the problem statement and reduction construction.
  • domain assumption Θ₂^p-completeness of a known base problem (e.g., a suitable variant of vertex cover or similar)
    The reduction starts from this established complete problem.

pith-pipeline@v0.9.0 · 5681 in / 1211 out tokens · 61416 ms · 2026-05-14T18:21:15.868585+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

55 extracted references · 55 canonical work pages

  1. [1]

    Finding large

    Chudnovsky, Maria and King, Jason and Pilipczuk, Micha. Finding large. SIAM Journal on Discrete Mathematics , volume=. 2021 , publisher=

    work page 2021

  2. [2]

    Finding large

    Hodur, Nadzieja and Pil. Finding large. arXiv preprint arXiv:2504.04984 , year=

    work page arXiv

  3. [3]

    2020 , issn =

    Intersection of longest paths in graph classes , journal =. 2020 , issn =. doi:https://doi.org/10.1016/j.dam.2019.03.022 , author =

    work page doi:10.1016/j.dam.2019.03.022 2020

  4. [4]

    2020 , doi =

    Transversals of longest paths , journal =. 2020 , doi =

    work page 2020

  5. [5]

    2022 , issn =

    Well-partitioned chordal graphs , journal =. 2022 , issn =. doi:https://doi.org/10.1016/j.disc.2022.112985 , author =

    work page doi:10.1016/j.disc.2022.112985 2022

  6. [6]

    Combinatorics, Probability and Computing , volume=

    Longest paths in circular arc graphs , author=. Combinatorics, Probability and Computing , volume=. 2004 , publisher=

    work page 2004

  7. [7]

    Precoloring extension

    Bir. Precoloring extension. Discrete Mathematics , volume=. 1992 , publisher=

    work page 1992

  8. [8]

    Chaplick, Steven and T. On. International Workshop on Graph-Theoretic Concepts in Computer Science , pages=. 2017 , organization=

    work page 2017

  9. [9]

    Combinatorial problems on

    Chaplick, Steven and Zeman, Peter , journal=. Combinatorial problems on. 2017 , publisher=

    work page 2017

  10. [10]

    Recognizing

    A. Recognizing. 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) , pages=. 2023 , organization=

    work page 2023

  11. [11]

    Pacific journal of mathematics , volume=

    Incidence matrices and interval graphs , author=. Pacific journal of mathematics , volume=. 1965 , publisher=

    work page 1965

  12. [12]

    Non-empty intersection of longest paths in

    Long, JA and Milans, KG and Munaro, A and others , journal=. Non-empty intersection of longest paths in

    work page

  13. [13]

    Theoretical Computer Science , year=

    Two remarks on the power of counting , author=. Theoretical Computer Science , year=

    work page

  14. [14]

    1876 , publisher =

    A Method of Determining the Public Vote , author =. 1876 , publisher =

    work page

  15. [15]

    Discrete Applied Mathematics , volume=

    Nonempty intersection of longest paths in graphs without forbidden pairs , author=. Discrete Applied Mathematics , volume=. 2021 , publisher=

    work page 2021

  16. [16]

    Longest Path Transversals in Claw-Free and

    Lima, Paloma T and Nikabadi, Amir , booktitle=. Longest Path Transversals in Claw-Free and. 2025 , organization=

    work page 2025

  17. [17]

    Proceedings of the American Mathematical Society , year=

    Small hitting sets for longest paths and cycles , author=. Proceedings of the American Mathematical Society , year=

    work page

  18. [18]

    Discussiones Mathematicae Graph Theory , volume=

    A note on longest paths in circular arc graphs , author=. Discussiones Mathematicae Graph Theory , volume=. 2015 , publisher=

    work page 2015

  19. [19]

    Discrete Applied Mathematics , volume=

    Detour trees , author=. Discrete Applied Mathematics , volume=. 2016 , publisher=

    work page 2016

  20. [20]

    1968 , PAGES =

    Theory of Graphs , SERIES =. 1968 , PAGES =

    work page 1968

  21. [21]

    1969 , publisher=

    Walther, Hansjoachim , journal=. 1969 , publisher=

    work page 1969

  22. [22]

    Mathematica Scandinavica , volume=

    On longest paths and circuits in graphs , author=. Mathematica Scandinavica , volume=. 1976 , publisher=

    work page 1976

  23. [23]

    SIAM Journal on Discrete Mathematics , volume=

    Transversals of longest paths and cycles , author=. SIAM Journal on Discrete Mathematics , volume=. 2014 , publisher=

    work page 2014

  24. [24]

    SIAM Journal on Discrete Mathematics , volume=

    Sublinear longest path transversals , author=. SIAM Journal on Discrete Mathematics , volume=. 2021 , publisher=

    work page 2021

  25. [25]

    Discrete Mathematics , volume=

    Improved upper bounds on longest-path and maximal-subdivision transversals , author=. Discrete Mathematics , volume=. 2023 , publisher=

    work page 2023

  26. [26]

    Kernelization of graph hamiltonicity: Proper

    Chaplick, Steven and Fomin, Fedor V and Golovach, Petr A and Knop, Dusan and Zeman, Peter , journal=. Kernelization of graph hamiltonicity: Proper. 2021 , publisher=

    work page 2021

  27. [27]

    Theoretical Computer Science , volume=

    A width parameter useful for chordal and co-comparability graphs , author=. Theoretical Computer Science , volume=. 2017 , publisher=

    work page 2017

  28. [28]

    Journal of Combinatorial Theory, Series B , volume=

    The intersection graphs of subtrees in trees are exactly the chordal graphs , author=. Journal of Combinatorial Theory, Series B , volume=. 1974 , publisher=

    work page 1974

  29. [29]

    2012 , publisher=

    New width parameters of graphs , author=. 2012 , publisher=

    work page 2012

  30. [30]

    Journal of Combinatorial Theory, Series B , volume=

    Graph searching and a min-max theorem for tree-width , author=. Journal of Combinatorial Theory, Series B , volume=. 1993 , publisher=

    work page 1993

  31. [31]

    Computing the Polytope Diameter is Even Harder than

    Wulf, Lasse , journal=. Computing the Polytope Diameter is Even Harder than

    work page

  32. [32]

    arXiv preprint arXiv:2412.20729 , year=

    Longest Path and Cycle Transversals in Chordal Graphs , author=. arXiv preprint arXiv:2412.20729 , year=

    work page arXiv

  33. [33]

    Discrete Mathematics , volume=

    Intersecting longest paths in chordal graphs , author=. Discrete Mathematics , volume=. 2023 , publisher=

    work page 2023

  34. [34]

    Electronic Journal of Graph Theory and Applications (EJGTA) , volume=

    Intersecting longest paths and longest cycles: A survey , author=. Electronic Journal of Graph Theory and Applications (EJGTA) , volume=

    work page

  35. [35]

    Hitting all longest paths in

    de Lima, Paloma T and Nikabadi, Amir and Rz. Hitting all longest paths in. arXiv preprint arXiv:2510.17312 , year=

    work page arXiv

  36. [36]

    , author=

    Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems-a Survey. , author=. J. Univers. Comput. Sci. , volume=. 2006 , publisher=

    work page 2006

  37. [37]

    More complicated questions about maxima and minima, and some closures of

    Wagner, Klaus W , journal=. More complicated questions about maxima and minima, and some closures of. 1987 , publisher=

    work page 1987

  38. [38]

    and Tarjan, R Endre , journal=

    Garey, Michael R and Johnson, David S. and Tarjan, R Endre , journal=. The planar Hamiltonian circuit problem is. 1976 , publisher=

    work page 1976

  39. [39]

    Karp , editor =

    Richard M. Karp , editor =. Reducibility Among Combinatorial Problems , booktitle =. 1972 , url =. doi:10.1007/978-1-4684-2001-2\_9 , timestamp =

    work page doi:10.1007/978-1-4684-2001-2 1972

  40. [40]

    Intersecting longest paths or cycles: a short survey , author=. An. Univ. Craiova Ser. Mat. Inform , volume=

    work page

  41. [41]

    Exact analysis of Dodgson elections:

    Hemaspaandra, Edith and Hemaspaandra, Lane A and Rothe, J. Exact analysis of Dodgson elections:. Journal of the ACM (JACM) , volume=. 1997 , publisher=

    work page 1997

  42. [42]

    The complexity of

    Hemaspaandra, Edith and Spakowski, Holger and Vogel, J. The complexity of. Theoretical Computer Science , volume=. 2005 , publisher=

    work page 2005

  43. [43]

    Encyclopedia of computer science , pages=

    Computational complexity , author=. Encyclopedia of computer science , pages=

    work page

  44. [44]

    Schmitz, Werner , journal=

    work page

  45. [45]

    , author=

    Vertices Missed by Longest Paths or Circuits. , author=

    work page

  46. [46]

    Graphen, in welchen je zwei Eckpunkte von einem l

    Zamfirescu, Tudor , journal=. Graphen, in welchen je zwei Eckpunkte von einem l. 1975 , publisher=

    work page 1975

  47. [47]

    Theoretical computer science , volume=

    The polynomial-time hierarchy , author=. Theoretical computer science , volume=. 1976 , publisher=

    work page 1976

  48. [48]

    SIAM Journal on Computing , volume=

    Bounded query classes , author=. SIAM Journal on Computing , volume=. 1990 , publisher=

    work page 1990

  49. [49]

    1989 , publisher=

    Kadin, Jim , journal=. 1989 , publisher=

    work page 1989

  50. [50]

    Exact complexity of the winner problem for

    Rothe, J. Exact complexity of the winner problem for. Theory of Computing Systems , volume=. 2003 , publisher=

    work page 2003

  51. [51]

    arXiv preprint arXiv:2511.06505 , year=

    Stronger Hardness for Maximum Robust Flow and Randomized Network Interdiction , author=. arXiv preprint arXiv:2511.06505 , year=

    work page arXiv

  52. [52]

    The complexity class ^p_2 : Recent results and applications in

    Eiter, Thomas and Gottlob, Georg , booktitle=. The complexity class ^p_2 : Recent results and applications in. 1997 , organization=

    work page 1997

  53. [53]

    The difference and truth-table hierarchies for

    K. The difference and truth-table hierarchies for. RAIRO-Theoretical Informatics and Applications , volume=. 1987 , publisher=

    work page 1987

  54. [54]

    Proceedings of the nineteenth annual ACM symposium on Theory of computing , pages=

    The strong exponential hierarchy collapses , author=. Proceedings of the nineteenth annual ACM symposium on Theory of computing , pages=

    work page

  55. [55]

    Theoretical computer science , pages=

    The complexity of blocking all solutions , author=. Theoretical computer science , pages=. 2026 , publisher=

    work page 2026