The Parameterized Complexity of Terminal Monitoring Set
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916272601563136 |
|---|---|
| author | Aravind, N. R. Saxena, Roopam |
| author_facet | Aravind, N. R. Saxena, Roopam |
| contents | In Terminal Monitoring Set (TMS), the input is an undirected graph $G=(V,E)$, together with a collection $T$ of terminal pairs and the goal is to find a subset $S$ of minimum size that hits a shortest path between every pair of terminals. We show that this problem is W[2]-hard with respect to solution size. On the positive side, we show that TMS is fixed parameter tractable with respect to solution size plus distance to cluster, solution size plus neighborhood diversity, and feedback edge number. For the weighted version of the problem, we obtain a FPT algorithm with respect to vertex cover number, and for a relaxed version of the problem, we show that it is W[1]-hard with respect to solution size plus feedback vertex number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_01730 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Parameterized Complexity of Terminal Monitoring Set Aravind, N. R. Saxena, Roopam Discrete Mathematics Computational Complexity In Terminal Monitoring Set (TMS), the input is an undirected graph $G=(V,E)$, together with a collection $T$ of terminal pairs and the goal is to find a subset $S$ of minimum size that hits a shortest path between every pair of terminals. We show that this problem is W[2]-hard with respect to solution size. On the positive side, we show that TMS is fixed parameter tractable with respect to solution size plus distance to cluster, solution size plus neighborhood diversity, and feedback edge number. For the weighted version of the problem, we obtain a FPT algorithm with respect to vertex cover number, and for a relaxed version of the problem, we show that it is W[1]-hard with respect to solution size plus feedback vertex number. |
| title | The Parameterized Complexity of Terminal Monitoring Set |
| topic | Discrete Mathematics Computational Complexity |
| url | https://arxiv.org/abs/2406.01730 |