Clearing directed subgraphs by mobile agents : Variations on covering with paths
(2019) In Journal of Computer and System Sciences 102. p.57-68- Abstract
We study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H=(VH,AH) of D such that (a) S⊆VH, (b) H is the union of k directed walks in D, and (c) the underlying graph of H includes a Steiner tree for S in D. Since a directed walk is a not necessarily a simple directed path, the problem is actually on covering with paths. We provide several results on the polynomial time tractability, hardness, and... (More)
We study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H=(VH,AH) of D such that (a) S⊆VH, (b) H is the union of k directed walks in D, and (c) the underlying graph of H includes a Steiner tree for S in D. Since a directed walk is a not necessarily a simple directed path, the problem is actually on covering with paths. We provide several results on the polynomial time tractability, hardness, and parameterized complexity of the problem. Our main fixed-parameter algorithm is randomized.
(Less)
- author
- Dereniowski, Dariusz ; Lingas, Andrzej LU ; Osula, Dorota ; Persson, Mia LU and Żyliński, Paweł
- organization
- publishing date
- 2019
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Covering with paths, FPT-algorithm, Monomial, NP-hardness
- in
- Journal of Computer and System Sciences
- volume
- 102
- pages
- 57 - 68
- publisher
- Elsevier
- external identifiers
-
- scopus:85057120191
- ISSN
- 0022-0000
- DOI
- 10.1016/j.jcss.2018.11.002
- language
- English
- LU publication?
- yes
- id
- a67939b2-0187-48b3-9183-6d0eb40ee068
- date added to LUP
- 2018-12-04 12:11:06
- date last changed
- 2022-04-25 19:40:32
@article{a67939b2-0187-48b3-9183-6d0eb40ee068, abstract = {{<p>We study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H=(V<sub>H</sub>,A<sub>H</sub>) of D such that (a) S⊆V<sub>H</sub>, (b) H is the union of k directed walks in D, and (c) the underlying graph of H includes a Steiner tree for S in D. Since a directed walk is a not necessarily a simple directed path, the problem is actually on covering with paths. We provide several results on the polynomial time tractability, hardness, and parameterized complexity of the problem. Our main fixed-parameter algorithm is randomized.</p>}}, author = {{Dereniowski, Dariusz and Lingas, Andrzej and Osula, Dorota and Persson, Mia and Żyliński, Paweł}}, issn = {{0022-0000}}, keywords = {{Covering with paths; FPT-algorithm; Monomial; NP-hardness}}, language = {{eng}}, pages = {{57--68}}, publisher = {{Elsevier}}, series = {{Journal of Computer and System Sciences}}, title = {{Clearing directed subgraphs by mobile agents : Variations on covering with paths}}, url = {{http://dx.doi.org/10.1016/j.jcss.2018.11.002}}, doi = {{10.1016/j.jcss.2018.11.002}}, volume = {{102}}, year = {{2019}}, }