Upper Domination: Towards a Dichotomy Through Boundary Properties

AbouEisha, Hassan, Hussain, Shahid, Lozin, Vadim, Monnot, Jerome, Ries, Bernard and Zamaraev, Viktor ORCID: 0000-0001-5755-4141 (2018) Upper Domination: Towards a Dichotomy Through Boundary Properties. ALGORITHMICA, 80 (10). pp. 2799-2817.

Text up-tcs_rev.pdf - Author Accepted Manuscript Download (279kB) | Preview

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.

Item Type:	Article
Uncontrolled Keywords:	Upper dominating set, Boundary class, Complexity dichotomy, NP-hard
Depositing User:	Symplectic Admin
Date Deposited:	29 Oct 2019 09:49
Last Modified:	19 Jan 2023 00:21
DOI:	10.1007/s00453-017-0346-9
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3059778