Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number

April 24, 2025 Β· Declared Dead Β· πŸ› International Symposium on Parameterized and Exact Computation

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Prafullkumar Tale arXiv ID 2504.17862 Category cs.DS: Data Structures & Algorithms Cross-listed cs.CC Citations 3 Venue International Symposium on Parameterized and Exact Computation Last Checked 4 months ago
Abstract
In the \textsc{Geodetic Set} problem, the input consists of a graph $G$ and a positive integer $k$. The goal is to determine whether there exists a subset $S$ of vertices of size $k$ such that every vertex in the graph is included in a shortest path between two vertices in $S$. Kellerhals and Koana [IPEC 2020; J. Graph Algorithms Appl 2022] proved that the problem is $\W[1]$-hard when parameterized by the pathwidth and the feedback vertex set number of the input graph. They posed the question of whether the problem admits an $\XP$ algorithm when parameterized by the combination of these two parameters. We answer this in negative by proving that the problem remains \NP-hard on graphs of constant pathwidth and feedback vertex set number.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted