Independent domination versus weighted independent domination

Lozin, Vadim, Malyshev, Dmitriy, Mosca, Raffaele and Zamaraev, Viktor ORCID: 0000-0001-5755-4141 (2020) Independent domination versus weighted independent domination. INFORMATION PROCESSING LETTERS, 156. p. 105914.

Text
versus-rev-2.pdf - Author Accepted Manuscript
Download (256kB) | Preview

Official URL: http://dx.doi.org/10.1016/j.ipl.2020.105914

Abstract

INDEPENDENT DOMINATION is one of the rare problems for which the complexity of weighted and unweighted versions is known to be different in some classes of graphs. Trying to better understand the gap between the two versions of the problem, in the present paper we prove two complexity results. First, we extend NP-hardness of the weighted version in a certain class to the unweighted case. Second, we strengthen polynomial-time solvability of the unweighted version in the class of P2+P3-free graphs to the weighted case. This result is tight in the sense that both versions are NP-hard in the class of P3+P3-free graphs, i.e. P3+P3 is a minimal graph forbidding of which produces an NP-hard case for both versions of the problem.

Item Type:	Article
Uncontrolled Keywords:	Independent domination, Weighted independent domination, Polynomial-time, NP-hardness, Algorithms
Depositing User:	Symplectic Admin
Date Deposited:	03 Feb 2020 16:39
Last Modified:	19 Jan 2023 00:05
DOI:	10.1016/j.ipl.2020.105914
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3073237