REVIEW 2 cited by
Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
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.
Forward citations
Cited by 2 Pith papers
-
Hitting Geodesic Intervals in Structurally Restricted Graphs
Hitting Geodesic Intervals is NP-complete on graphs that are almost disjoint paths or triangles, yet becomes fixed-parameter tractable when the solution size is combined with modular-width, vertex integrity, or multiw...
-
Distance-based (and path-based) covering problems for graphs of given cyclomatic number
For every connected graph, the distance-edge-monitoring number is at most the cyclomatic number plus one, and similar linear bounds hold for metric dimension, geodetic number, and isometric path covers.
Discussion (0). Sign in to comment.