This paper is motivated by the concept of
the signed k-domination problem and dedicated to the complexity of the problem
on graphs. For any fixed nonnegative integer k, we show that the signed k-domination
problem is NP-complete for doubly chordal graphs. For strongly chordal graphs
and distance-hereditary graphs, we show that the signed k-domination problem
can be solved in polynomial time. We also show that the problem is linear-time
solvable for trees, interval graphs, and chordal comparability graphs.
References
[1]
Wang, C. (2012) The Signed k-Domination Numbers in Graphs. Ars Combinatoria, 106, 205-211.
[2]
Hattingh, J.H., Henning, M.A. and Slater, P.J. (1995) The Algorithmic Complexity of Signed Domination in Graphs. Australasian Journal of Combinatorics, 12, 101-112.
[3]
Lee, C.-M. and Chang, M.-S. (2008) Variations of Y-Dominating Functions on Graphs. Discrete Mathematics, 308, 4185-4204. http://dx.doi.org/10.1016/j.disc.2007.08.080
[4]
Lee, C.-M. (2014) Remarks on the Complexity of Non-negative Signed Domination. Journal of Networks, 9, 2051- 2058. http://dx.doi.org/10.4304/jnw.9.8.2051-2058
[5]
Brandst?dt, A., Dragan, F.F., Chepoi, V.D. and Voloshin, V. (1998) Dually Chordal Graphs. SIAM Journal on Discrete Mathematics, 11, 437-455. http://dx.doi.org/10.1137/S0895480193253415
[6]
Cai, L., Chen, J., Downey, R.G. and Fellows, M.R. (1997) Advice Classes of Parameterized Tractability. Annals of Pure and Applied Logic, 84, 119-138. http://dx.doi.org/10.1016/S0168-0072(95)00020-8
[7]
Downey, R.G. and Fellows, M.R. (1999) Parameterized Complexity. Monographs in Computer Science, Springer- Verlag.
[8]
Moscarini, M. (1993) Doubly Chordal Graphs, Steiner Trees, and Connected Domination. Networks, 23, 59-69.
http://dx.doi.org/10.1002/net.3230230108
[9]
Rose, D.J. (1970) Triangulated Graphs and the Elimination Process. Journal of Mathematical Analysis and Applications, 32, 597-609. http://dx.doi.org/10.1016/0022-247X(70)90282-9
[10]
Farber, M. (1983) Characterizations of Strongly Chordal Graphs. Discrete Mathematics, 43, 173-189.
http://dx.doi.org/10.1016/0012-365X(83)90154-1
[11]
Paige, R. and Tarjan, R.E. (1987) Three Partition Refinement Algorithms. SIAM Journal on Computing, 16, 973-989.
http://dx.doi.org/10.1137/0216062
[12]
Spinrad, J.P. (1993) Doubly Lexical Ordering of Dense 0-1 Matrices. Information Processing Letters, 45, 229-235.
http://dx.doi.org/10.1016/0020-0190(93)90209-R
[13]
Brandst?dt, A., Le, V.B. and Spinrad, J.P. (1999) Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia 1999. http://dx.doi.org/10.1137/1.9780898719796
[14]
Tarjan, R.E. and Yannakakis, M. (1984) Simple Linear Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs. SIAM Joural on Computing, 13, 566-579.
http://dx.doi.org/10.1137/0213035
[15]
Booth, S. and Lueker, S. (1976) Testing for the Consecutive Ones Property, Interval Graphs, Graph Planarity Using PQ-Trees Algorithms. Journal of Computer and System Sciences, 13, 335-379.
http://dx.doi.org/10.1016/S0022-0000(76)80045-1
[16]
Borie, R.B. and Spinrad, J.P. (1999) Construction of a Simple Elimination Scheme for a Chordal Comparability Graph in Linear Time. Discrete Applied Mathematics, 91, 287-292. http://dx.doi.org/10.1016/S0166-218X(98)00137-1
[17]
Sawada, J. and Spinrad, J.P. (2003) From a Simple Elimination Ordering to a Strong Elimination Ordering in Linear Time. Information Processing Letters, 86, 299-302. http://dx.doi.org/10.1016/S0020-0190(03)00228-X
[18]
Chang, M.-S., Hsieh, S.-Y. and Chen, G.-H. (1997) Dynamic Programming on Distance-Hereditary Graphs. Proceedings of the 8th International Symposium o Algorithms and Computation, Lecture Notes in Computer Science, Vol. 1350, 344-353.
