Algorithmic aspect of minus domination on small-degree graphs

Jin Yong Lin, Ching Hao Liu, Sheung Hung Poon

Research output: Chapter in Book/Conference proceedingConference contributionpeer-review

1 Citation (Scopus)

Abstract

Let G = (V,E) be an undirected graph. A minus dominating function for G is a function f : V → {-1, 0, +1} such that for each vertex v ∈ V , the sum of the function values over the closed neighborhood of v is positive. The weight of a minus dominating function f for G, denoted by w(f(V)), is ∑f(v) over all vertices v ∈ V. The minus domination (MD) number of G is the minimum weight for any minus dominating function for G. The minus domination (MD) problem asks for the minus dominating function which contributes the MD number. In this paper, we first show that the MD problem is W[2]-hard for general graphs. Then we show that the MD problem is NP-complete for subcubic bipartite planar graphs. We further show that the MD problem is APX-hard for graphs of maximum degree seven. Lastly, we present the first fixed-parameter algorithm for the MD problem on subcubic graphs, which runs in O (2.37615k) time, where k is the MD number of the graph.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 21st International Conference, COCOON 2015, Proceedings
EditorsDachuan Xu, Donglei Du, Dingzhu Du
PublisherSpringer Verlag
Pages337-348
Number of pages12
ISBN (Print)9783319213972
DOIs
Publication statusPublished - 2015
Externally publishedYes
Event21st International Conference on Computing and Combinatorics Conference, COCOON 2015 - Beijing, China
Duration: 4 Aug 20156 Aug 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9198
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st International Conference on Computing and Combinatorics Conference, COCOON 2015
Country/TerritoryChina
CityBeijing
Period4/08/156/08/15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'Algorithmic aspect of minus domination on small-degree graphs'. Together they form a unique fingerprint.

Cite this