Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
April 24, 2025 Β· Declared Dead Β· π International Symposium on Parameterized and Exact Computation
"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 Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
π Similar Papers
In the same crypt β Data Structures & Algorithms
π
π
The Cartographer
R.I.P.
π»
Ghosted
Route Planning in Transportation Networks
R.I.P.
π»
Ghosted
Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
R.I.P.
π»
Ghosted
Hierarchical Clustering: Objective Functions and Algorithms
R.I.P.
π»
Ghosted
Graph Isomorphism in Quasipolynomial Time
π
π
The Cartographer
Simulation optimization: A review of algorithms and applications
Died the same way β π» Ghosted
R.I.P.
π»
Ghosted
Federated Learning: Strategies for Improving Communication Efficiency
R.I.P.
π»
Ghosted
In-Datacenter Performance Analysis of a Tensor Processing Unit
R.I.P.
π»
Ghosted
Deep Convolutional Neural Networks for Computer-Aided Detection: CNN Architectures, Dataset Characteristics and Transfer Learning
R.I.P.
π»
Ghosted