Parameterized Complexity of Minimum Membership Dominating Set

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F23%3A00374506" target="_blank" >RIV/68407700:21240/23:00374506 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s00453-023-01139-7" target="_blank" >https://doi.org/10.1007/s00453-023-01139-7</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00453-023-01139-7" target="_blank" >10.1007/s00453-023-01139-7</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Parameterized Complexity of Minimum Membership Dominating Set

Popis výsledku v původním jazyce

Given a graph G = (V, E) and an integer k, the Minimum Membership Dominating Set (MMDS) problem seeks to find a dominating set S subset of V of G such that for each v is an element of V, vertical bar N[v] boolean AND S vertical bar is at most k. We investigate the parameterized complexity of the problem and obtain the following results for the MMDS problem. First, we show that the MMDS problem is NP-hard even on planar bipartite graphs. Next, we show that the MMDS problem is W[1]-hard for the parameter pathwidth (and thus, for treewidth) of the input graph. Then, for split graphs, we show that the MMDS problem is W[2]-hard for the parameter k. Further, we complement the pathwidth lower bound by an FPT algorithm when parameterized by the vertex cover number of input graph. In particular, we design a 2(O(vc))vertical bar V vertical bar(O(1)) time algorithm for the MMDS problem where vc is the vertex cover number of the input graph. Finally, we show that the running time lower bound based on ETH is tight for the vertex cover parameter.

Název v anglickém jazyce

Parameterized Complexity of Minimum Membership Dominating Set

Popis výsledku anglicky

Given a graph G = (V, E) and an integer k, the Minimum Membership Dominating Set (MMDS) problem seeks to find a dominating set S subset of V of G such that for each v is an element of V, vertical bar N[v] boolean AND S vertical bar is at most k. We investigate the parameterized complexity of the problem and obtain the following results for the MMDS problem. First, we show that the MMDS problem is NP-hard even on planar bipartite graphs. Next, we show that the MMDS problem is W[1]-hard for the parameter pathwidth (and thus, for treewidth) of the input graph. Then, for split graphs, we show that the MMDS problem is W[2]-hard for the parameter k. Further, we complement the pathwidth lower bound by an FPT algorithm when parameterized by the vertex cover number of input graph. In particular, we design a 2(O(vc))vertical bar V vertical bar(O(1)) time algorithm for the MMDS problem where vc is the vertex cover number of the input graph. Finally, we show that the running time lower bound based on ETH is tight for the vertex cover parameter.

Druh

J_imp - Článek v periodiku v databázi Web of Science

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í

2023

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 periodika

Algorithmica

ISSN

0178-4617

e-ISSN

1432-0541

Svazek periodika

85

Číslo periodika v rámci svazku

11

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

23

Strana od-do

3430-3452

Kód UT WoS článku

001010001200001

EID výsledku v databázi Scopus

2-s2.0-85163100740