Active vertices in optimal lollipop cycle

Question 4.2 · arXiv:2502.04726

arXiv Question high confidence— first stated 2025-10-10

Authors: Zdeněk Dvořák, Beatriz Martins, Stéphan Thomassé, Nicolas Trotignon

Status open high confidence

Question 4.2 from arXiv:2502.04726 asks whether there is a simple way to compute all active vertices in the cycle of an optimal lollipop; it appears in the concluding open problems section of the paper. The paper itself establishes that finding an optimal lollipop is NP-hard (solving it in polynomial time would imply finding a Hamiltonian cycle in polynomial time), and provides a weaker polynomial-time procedure that finds only sufficiently many active paths with distinct ends. No follow-up work addressing this specific algorithmic question was found in a broad web search conducted in May 2026.

Reviewer notes. No follow-up found. The question is inherently tied to NP-hardness of optimal lollipop computation, making a simple closed-form characterization of active vertices unlikely without additional structural assumptions. Paper 2502.10657 (Chords of longest cycles passing through a specified small set) uses related lollipop-style techniques but does not address Question 4.2.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Question. Is there a simple way to compute all the active vertices in the cycle of an optimal lollipop?

Context

Active vertices determine the number of distinct chords produced by the lollipop argument. In the lollipop argument, the number of distinct active vertices (and thus chords) increases with the girth $g$ of the host graph, motivating the search for an efficient procedure to identify them.

Source paper

Lollipops, dense cycles and chords
Zdeněk Dvořák, Beatriz Martins, Stéphan Thomassé, Nicolas Trotignon · 2025-10-10
https://arxiv.org/abs/2502.04726