Target Set Selection in Dense Graph Classes

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/68407700:21240/18:00326433

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Target Set Selection in Dense Graph Classes

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Target Set Selection in Dense Graph Classes

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2018

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

29th International Symposium on Algorithms and Computation (ISAAC 2018)

ISBN

978-3-95977-094-1

ISSN

1868-8969

e-ISSN

neuvedeno

Počet stran výsledku

13

Strana od-do

1-13

Název nakladatele

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Místo vydání

Dagstuhl, Germany

Místo konání akce

Jiaoxi

Datum konání akce

16. 12. 2018

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—