Abstract: A vertex set of a graph is geodetic if every vertex of lies on a shortest path between two vertices in . Given a graph and , the NP-hard Geodetic Set problem asks whether there is a geodetic set of size at most . Complementing various works on Geodetic Set restricted to special graph classes, we initiate a parameterized complexity study of Geodetic Set and show, on the negative side, that Geodetic Set is W[1]-hard when parameterized by feedback vertex number, path-width, and solution size, combined. On the positive side, we develop fixed-parameter algorithms with respect to the feedback edge number, the tree-depth, and the modular-width of the input graph.
Recommendations
Cites work
- A survey of the algorithmic aspects of modular decomposition
- Computational Complexity of Geodetic Set
- Hardness and approximation for the geodetic set problem in some graph classes
- Hull number: \(P_5\)-free graphs and reduction rules
- Integer Programming with a Fixed Number of Variables
- Linear time solvable optimization problems on graphs of bounded clique-width
- Metric Dimension of Bounded Tree-length Graphs
- Metric dimension parameterized by max leaf number
- Metric dimension parameterized by treewidth
- Notes on complexity of packing coloring
- On the Relationship Between Clique-Width and Treewidth
- On the geodetic hull number of \(P_{k}\)-free graphs
- On the geodetic number and related metric sets in Cartesian product graphs
- On the hardness of finding the geodetic number of a subcubic graph
- On the parameterized complexity of the geodesic hull number
- Parameterized algorithms
- Some remarks on the geodetic number of a graph
- Sparsity. Graphs, structures, and algorithms
- The (weighted) metric dimension of graphs: hard and easy cases
- The geodetic hull number is hard for chordal graphs
Cited in
(17)- Computational Complexity of Geodetic Set
- Distance-based (and path-based) covering problems for graphs of given cyclomatic number
- Geometric complexity of some location problems
- Bounds and extremal graphs for monitoring edge-geodetic sets in graphs
- Structural parameterizations of the biclique-free vertex deletion problem
- Fine-grained meta-theorems for vertex integrity
- Algorithms and complexity for geodetic sets on partial grids
- Hardness and approximation for the geodetic set problem in some graph classes
- Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover
- Monitoring edge-geodetic sets in graphs
- On the parameterized complexity of the geodesic hull number
- scientific article; zbMATH DE number 7765365 (Why is no real title available?)
- Structural parameterization of locating-dominating set and test cover
- Block decomposition approach to compute a minimum geodetic set
- Enumerating minimal solution sets for metric graph problems
- Distance-based covering problems for graphs of given cyclomatic number
- Monitoring edge-geodetic sets in graphs: extremal graphs, bounds, complexity
This page was built for publication: Parameterized complexity of geodetic set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5050005)
