Parameterized complexity of geodetic set

DOI10.7155/JGAA.00601zbMATH Open1499.68152arXiv2001.03098OpenAlexW2999989716MaRDI QIDQ5050005FDOQ5050005

Tomohiro Koana, Leon Kellerhals

Publication date: 14 November 2022

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• Linear time solvable optimization problems on graphs of bounded clique-width
• Integer Programming with a Fixed Number of Variables
• On the Relationship Between Clique-Width and Treewidth
• Parameterized Algorithms
• Sparsity. Graphs, structures, and algorithms
• Some remarks on the geodetic number of a graph
• Hull number: \(P_5\)-free graphs and reduction rules
• The (weighted) metric dimension of graphs: hard and easy cases
• A survey of the algorithmic aspects of modular decomposition
• On the geodetic number and related metric sets in Cartesian product graphs
• Metric Dimension Parameterized by Max Leaf Number
• Hardness and approximation for the geodetic set problem in some graph classes
• Metric Dimension of Bounded Tree-length Graphs
• Computational Complexity of Geodetic Set
• Notes on complexity of packing coloring
• On the geodetic hull number of \(P_{k}\)-free graphs
• On the hardness of finding the geodetic number of a subcubic graph
• The Geodetic Hull Number is Hard for Chordal Graphs
• On the parameterized complexity of the geodesic hull number
• Metric dimension parameterized by treewidth

Cited In (8)

• Computational Complexity of Geodetic Set
• Geometric complexity of some location problems
• Algorithms and complexity for geodetic sets on partial grids
• Monitoring edge-geodetic sets in graphs
• Title not available (Why is that?)
• Block decomposition approach to compute a minimum geodetic set
• 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)