Parameterized complexity of geodetic set

DOI10.7155/JGAA.00601MaRDI QIDQ5050005zbMATH OpenOpenAlexFDO

Authors Leon Kellerhals, Tomohiro Koana

Publication date 14 November 2022

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2001.03098

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: A vertex set $S$ of a graph $G$ is geodetic if every vertex of $G$ lies on a shortest path between two vertices in $S$. Given a graph $G$ and $kinmathbbN$, the NP-hard Geodetic Set problem asks whether there is a geodetic set of size at most $k$. 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

• Computational Complexity of Geodetic Set
• Hardness and approximation for the geodetic set problem in some graph classes
• Some remarks on the geodetic number of a graph
• On the hardness of finding the geodetic number of a subcubic graph
• On the geodetic and geodetic domination numbers of a graph

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

(10)

• Algorithms and complexity for geodetic sets on partial grids
• Block decomposition approach to compute a minimum geodetic set
• Computational Complexity of Geodetic Set
• Hardness and approximation for the geodetic set problem in some graph classes
• Distance-based covering problems for graphs of given cyclomatic number
• Monitoring edge-geodetic sets in graphs: extremal graphs, bounds, complexity
• On the parameterized complexity of the geodesic hull number
• Monitoring edge-geodetic sets in graphs
• Geometric complexity of some location problems
• scientific article; zbMATH DE number 7765365 (Why is no real title available?)

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)