Algorithms and hardness for signed domination

Jin Yong Lin, Sheung Hung Poon

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

1 Citation (Scopus)

Abstract

A signed dominating function for a graph G = (V,E) is a function f: V → {+1,−1} such that for all v ∈ V, the sum of the function values over the closed neighborhood of v is at least one. The weight w(f(V)) of signed dominating function f for vertex set V is the sum of f(v) for v ∈ V. The signed domination number γs of G is the minimum weight of a signed dominating function for G. The signed domination (SD) problem asks for a signed dominating function which contributes the signed domination number. First we show that the SD problem is W[2]-hard. Next we show that the SD problem on graphs of maximum degree six is APX-hard. Then we present constant-factor approximation algorithms for the SD problem on subcubic graphs, graphs of maximum degree four, and graphs of maximum degree five, respectively. In addition, we present an alternative and more direct proof for the NP-completeness of the SD problem on subcubic planar bipartite graphs. Lastly, we obtain an O (5.1957k)-time FPT-algorithm for the SD problem on subcubic graphs G, where k is the signed domination number of G.

Original languageEnglish
Title of host publicationTheory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, Proceedings
EditorsRahul Jain, Sanjay Jain, Frank Stephan
PublisherSpringer Verlag
Pages453-464
Number of pages12
ISBN (Electronic)9783319171418
DOIs
Publication statusPublished - 2015
Externally publishedYes
Event12th Annual Conference on Theory and Applications of Models of Computation, TAMC 2015 - Singapore, Singapore
Duration: 18 May 201520 May 2015

Publication series

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

Conference

Conference12th Annual Conference on Theory and Applications of Models of Computation, TAMC 2015
Country/TerritorySingapore
CitySingapore
Period18/05/1520/05/15

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Algorithms and hardness for signed domination'. Together they form a unique fingerprint.

Cite this