Target Set Selection in Dense Graph Classes
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10386996" target="_blank" >RIV/00216208:11320/18:10386996 - isvavai.cz</a>
Alternative codes found
RIV/68407700:21240/18:00326433
Result on the web
<a href="http://drops.dagstuhl.de/opus/volltexte/2018/9966/pdf/LIPIcs-ISAAC-2018-18.pdf" target="_blank" >http://drops.dagstuhl.de/opus/volltexte/2018/9966/pdf/LIPIcs-ISAAC-2018-18.pdf</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.ISAAC.2018.18" target="_blank" >10.4230/LIPIcs.ISAAC.2018.18</a>
Alternative languages
Result language
angličtina
Original language name
Target Set Selection in Dense Graph Classes
Original language description
In this paper we study the Target Set Selection problem from a parameterized complexity perspective. Here for a given graph and a threshold for each vertex the task is to find a set of vertices (called a target set) to activate at the beginning which activates the whole graph during the following iterative process. A vertex outside the active set becomes active if the number of so far activated vertices in its neighborhood is at least its threshold. We give two parameterized algorithms for a special case where each vertex has the threshold set to the half of its neighbors (the so called Majority Target Set Selection problem) for parameterizations by the neighborhood diversity and the twin cover number of the input graph. We complement these results from the negative side. We give a hardness proof for the Majority Target Set Selection problem when parameterized by (a restriction of) the modular-width - a natural generalization of both previous structural parameters. We show that the Target Set Selection problem parameterized by the neighborhood diversity when there is no restriction on the thresholds is W[1]-hard.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
29th International Symposium on Algorithms and Computation (ISAAC 2018)
ISBN
978-3-95977-094-1
ISSN
1868-8969
e-ISSN
neuvedeno
Number of pages
13
Pages from-to
1-13
Publisher name
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Place of publication
Dagstuhl, Germany
Event location
Jiaoxi
Event date
Dec 16, 2018
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—