PDF

Discussiones Mathematicae Graph Theory 29(2) (2009) 253-261
DOI: https://doi.org/10.7151/dmgt.1445

MINIMUM VERTEX RANKING SPANNING TREE PROBLEM FOR CHORDAL AND PROPER INTERVAL GRAPHS

Dariusz Dereniowski

Department of Algorithms and System Modeling
Gdańsk University of Technology, Poland
e-mail: deren@eti.pg.gda.pl

Abstract

A vertex k-ranking of a simple graph is a coloring of its vertices with k colors in such a way that each path connecting two vertices of the same color contains a vertex with a bigger color. Consider the minimum vertex ranking spanning tree (MVRST) problem where the goal is to find a spanning tree of a given graph G which has a vertex ranking using the minimal number of colors over vertex rankings of all spanning trees of G. K. Miyata et al. proved in [NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem, Discrete Appl. Math. 154 (2006) 2402-2410] that the decision problem: given a simple graph G, decide whether there exists a spanning tree T of G such that T has a vertex 4-ranking, is NP-complete. In this paper we improve this result by proving NP-hardness of finding for a given chordal graph its spanning tree having vertex 3-ranking. This bound is the best possible. On the other hand we prove that MVRST problem can be solved in linear time for proper interval graphs.

Keywords: computational complexity, vertex ranking, spanning tree.

2000 Mathematics Subject Classification: 68R10, 68Q25, 05C15.

References

[1]	A.S. Arefin and M.A. Kashem, NP-Completeness of the minimum edge-ranking spanning tree problem on series-parallel graphs, Proc. 10th International Conference on Computer and Information Technology, 2008 (ICCIT 2007) 1-4.
[2]	K.S. Booth and G.S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. System Sci. 13 (1976) 335-379, doi: 10.1016/S0022-0000(76)80045-1.
[3]	D.Z. Chen, D. Lee, R. Sridhar and C.N. Sekharan, Solving the all-pair shortest path query problem on interval and circular-arc graphs, Networks 31 (1998) 249-257, doi: 10.1002/(SICI)1097-0037(199807)31:4<249::AID-NET5>3.0.CO;2-D.
[4]	J.S. Deogun, T. Kloks, D. Kratsch and H. Müller, On the vertex ranking problem for trapezoid, circular-arc and other graphs, Discrete Appl. Math. 98 (1999) 39-63, doi: 10.1016/S0166-218X(99)00179-1.
[5]	D. Dereniowski, Edge ranking and searching in partial orders, Discrete Appl. Math. 156 (2008) 2493-2500, doi: 10.1016/j.dam.2008.03.007.
[6]	D. Dereniowski and M. Kubale, Efficient parallel query processing by graph ranking, Fundamenta Informaticae 69 (2006) 273-285.
[7]	D. Dereniowski and A. Nadolski, Vertex rankings of chordal graphs and weighted trees, Inform. Process. Letters 98 (2006) 96-100, doi: 10.1016/j.ipl.2005.12.006.
[8]	S.-Y. Hsieh, On vertex ranking of a starlike graph, Inform. Process. Letters 82 (2002) 131-135, doi: 10.1016/S0020-0190(01)00262-9.
[9]	M.A. Kashem, M.A. Haque, M.R. Uddin and S.A. Sharmin, An algorithm for finding minimum edge-ranking spanning tree of series-parallel graphs, Proc. of the 9th International Conference on Computer and Information Technology (ICCIT 2006) 108-112.
[10]	K. Makino, Y. Uno and T. Ibaraki, Minimum edge ranking spanning trees of threshold graphs, Lecture Notes in Comp. Sci. 2518 (2002) 59-77.
[11]	K. Makino, Y. Uno and T. Ibaraki, On minimum edge ranking spanning trees, J. Algorithms 38 (2001) 411-437, doi: 10.1006/jagm.2000.1143.
[12]	K. Miyata, S. Masuyama, S. Nakayama and L. Zhao, Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem, Discrete Appl. Math. 154 (2006) 2402-2410, doi: 10.1016/j.dam.2006.04.016.
[13]	S. Nakayama and S. Masuyama, An algorithm for solving the minimum vertex ranking spanning tree problem on interval graphs, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E86-A (2003) 1019-1026.
[14]	S. Nakayama and S. Masuyama, A polynomial time algorithm for obtaining a minimum vertex ranking spanning tree in outerplanar graphs, IEICE Transactions on Information and Systems E89-D (2006) 2357-2363, doi: 10.1093/ietisy/e89-d.8.2357.
[15]	A. Pothen, The complexity of optimal elimination trees, Tech. Report CS-88-13, The Pennsylvania State University, 1988.
[16]	A.A. Schäffer, Optimal node ranking of trees in linear time, Inform. Process. Letters 33 (1989) 91-96, doi: 10.1016/0020-0190(89)90161-0.

Received 3 December 2007
Revised 10 March 2009
Accepted 10 March 2009