Algorithms and hardness for Metric Dimension on digraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908968211709952 |
|---|---|
| author | Dailly, Antoine Foucaud, Florent Hakanen, Anni |
| author_facet | Dailly, Antoine Foucaud, Florent Hakanen, Anni |
| contents | In the Metric Dimension problem, one asks for a minimum-size set $R$ of vertices such that for any pair of vertices of the graph, there is a vertex from $R$ whose two distances to the vertices of the pair are distinct. This problem has mainly been studied on undirected graphs and has gained a lot of attention in the recent years. We focus on directed graphs, and show how to solve the problem in linear time on digraphs whose underlying undirected graph (ignoring multiple edges) is a tree. This (non-trivially) extends a previous algorithm for oriented trees. We then extend the method to orientations of unicyclic graphs. We also give a fixed-parameter-tractable algorithm for digraphs when parameterized by the directed modular-width, extending a known result for undirected graphs. Finally, we show that Metric Dimension is NP-hard even on planar triangle-free acyclic digraphs of maximum degree 6. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_09389 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Algorithms and hardness for Metric Dimension on digraphs Dailly, Antoine Foucaud, Florent Hakanen, Anni Combinatorics Discrete Mathematics In the Metric Dimension problem, one asks for a minimum-size set $R$ of vertices such that for any pair of vertices of the graph, there is a vertex from $R$ whose two distances to the vertices of the pair are distinct. This problem has mainly been studied on undirected graphs and has gained a lot of attention in the recent years. We focus on directed graphs, and show how to solve the problem in linear time on digraphs whose underlying undirected graph (ignoring multiple edges) is a tree. This (non-trivially) extends a previous algorithm for oriented trees. We then extend the method to orientations of unicyclic graphs. We also give a fixed-parameter-tractable algorithm for digraphs when parameterized by the directed modular-width, extending a known result for undirected graphs. Finally, we show that Metric Dimension is NP-hard even on planar triangle-free acyclic digraphs of maximum degree 6. |
| title | Algorithms and hardness for Metric Dimension on digraphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2307.09389 |