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

Dariusz Dereniowski , Andrzej Lingas , Dorota Osula , Mia Persson , Paweł Żyliński


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 H ,A H ) of D such that (a) S⊆V H , (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.
Author Dariusz Dereniowski
Dariusz Dereniowski,,
, Andrzej Lingas
Andrzej Lingas,,
, Dorota Osula
Dorota Osula,,
, Mia Persson
Mia Persson,,
, Paweł Żyliński (FMPI/II)
Paweł Żyliński,,
- Institute of Informatics
Journal seriesJournal of Computer and System Sciences, ISSN 0022-0000, (N/A 100 pkt)
Issue year2019
Publication size in sheets0.55
Keywords in Englishcovering with paths, FPT-algorithm, NP-hardness, monomial
ASJC Classification1703 Computational Theory and Mathematics; 1705 Computer Networks and Communications; 2604 Applied Mathematics; 2614 Theoretical Computer Science
Languageen angielski
Score (nominal)100
Score sourcejournalList
ScoreMinisterial score = 100.0, 28-01-2020, ArticleFromJournal
Publication indicators WoS Citations = 0.000; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 1.334; WoS Impact Factor: 2018 = 1.129 (2) - 2018=1.739 (5)
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?