Upper Domination: Towards a Dichotomy Through Boundary Properties

Hassan M. AbouEisha; Shahid Hussain; Vadim Lozin; Jérôme Monnot; Bernard Ries; Viktor Zamaraev

doi:10.1007/s00453-017-0346-9

Upper Domination: Towards a Dichotomy Through Boundary Properties

Hassan M. AbouEisha, Shahid Hussain, Vadim Lozin, Jérôme Monnot, Bernard Ries, Viktor Zamaraev

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

An upper dominating set in a graph is a minimal dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard. We study the complexity of this problem in finitely defined classes of graphs and conjecture that the problem admits a complexity dichotomy in this family. A helpful tool to study the complexity of an algorithmic problem is the notion of boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. We discover the first boundary class for this problem and prove the dichotomy for monogenic classes.

Original language	English (US)
Pages (from-to)	2799-2817
Number of pages	19
Journal	Algorithmica
Volume	80
Issue number	10
DOIs	https://doi.org/10.1007/s00453-017-0346-9
State	Published - Jul 14 2017

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: Vadim Lozin and Viktor Zamaraev gratefully acknowledge support from EPSRC, Grant EP/L020408/1. Part of this research was carried out when Vadim Lozin was visiting the King Abdullah University of Science and Technology (KAUST). This author thanks the University for hospitality and stimulating research environment.

Access to Document

10.1007/s00453-017-0346-9

Cite this

@article{361cff8b38024fd8934814679d754d60,

title = "Upper Domination: Towards a Dichotomy Through Boundary Properties",

abstract = "An upper dominating set in a graph is a minimal dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard. We study the complexity of this problem in finitely defined classes of graphs and conjecture that the problem admits a complexity dichotomy in this family. A helpful tool to study the complexity of an algorithmic problem is the notion of boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. We discover the first boundary class for this problem and prove the dichotomy for monogenic classes.",

author = "AbouEisha, {Hassan M.} and Shahid Hussain and Vadim Lozin and J{\'e}r{\^o}me Monnot and Bernard Ries and Viktor Zamaraev",

note = "KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: Vadim Lozin and Viktor Zamaraev gratefully acknowledge support from EPSRC, Grant EP/L020408/1. Part of this research was carried out when Vadim Lozin was visiting the King Abdullah University of Science and Technology (KAUST). This author thanks the University for hospitality and stimulating research environment.",

year = "2017",

month = jul,

day = "14",

doi = "10.1007/s00453-017-0346-9",

language = "English (US)",

volume = "80",

pages = "2799--2817",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "10",

}

TY - JOUR

T1 - Upper Domination: Towards a Dichotomy Through Boundary Properties

AU - AbouEisha, Hassan M.

AU - Hussain, Shahid

AU - Lozin, Vadim

AU - Monnot, Jérôme

AU - Ries, Bernard

AU - Zamaraev, Viktor

N1 - KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: Vadim Lozin and Viktor Zamaraev gratefully acknowledge support from EPSRC, Grant EP/L020408/1. Part of this research was carried out when Vadim Lozin was visiting the King Abdullah University of Science and Technology (KAUST). This author thanks the University for hospitality and stimulating research environment.

PY - 2017/7/14

Y1 - 2017/7/14

N2 - An upper dominating set in a graph is a minimal dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard. We study the complexity of this problem in finitely defined classes of graphs and conjecture that the problem admits a complexity dichotomy in this family. A helpful tool to study the complexity of an algorithmic problem is the notion of boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. We discover the first boundary class for this problem and prove the dichotomy for monogenic classes.

AB - An upper dominating set in a graph is a minimal dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard. We study the complexity of this problem in finitely defined classes of graphs and conjecture that the problem admits a complexity dichotomy in this family. A helpful tool to study the complexity of an algorithmic problem is the notion of boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. We discover the first boundary class for this problem and prove the dichotomy for monogenic classes.

UR - http://hdl.handle.net/10754/625686

UR - http://link.springer.com/article/10.1007/s00453-017-0346-9

UR - http://www.scopus.com/inward/record.url?scp=85023758076&partnerID=8YFLogxK

U2 - 10.1007/s00453-017-0346-9

DO - 10.1007/s00453-017-0346-9

M3 - Article

SN - 0178-4617

VL - 80

SP - 2799

EP - 2817

JO - Algorithmica

JF - Algorithmica

IS - 10

ER -

Upper Domination: Towards a Dichotomy Through Boundary Properties

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this