Advanced

Clearing directed subgraphs by mobile agents : Variations on covering with paths

Dereniowski, Dariusz ; Lingas, Andrzej LU ; Osula, Dorota ; Persson, Mia LU and Żyliński, Paweł (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)
Please use this url to cite or link to this publication:
author
organization
publishing date
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
2019-11-25 09:25:49
@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},
  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},
}