TY - GEN

T1 - Algorithmic aspect of minus domination on small-degree graphs

AU - Lin, Jin Yong

AU - Liu, Ching Hao

AU - Poon, Sheung Hung

N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

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

U2 - 10.1007/978-3-319-21398-9_27

DO - 10.1007/978-3-319-21398-9_27

M3 - Conference contribution

AN - SCOPUS:84951056725

SN - 9783319213972

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 337

EP - 348

BT - Computing and Combinatorics - 21st International Conference, COCOON 2015, Proceedings

A2 - Xu, Dachuan

A2 - Du, Donglei

A2 - Du, Dingzhu

PB - Springer Verlag

T2 - 21st International Conference on Computing and Combinatorics Conference, COCOON 2015

Y2 - 4 August 2015 through 6 August 2015

ER -