一個在圖G中的點集合S稱之為K長度路徑之點覆蓋集合，假如每條長度為k的路徑上，至少包含一個點是屬於S.最小的K長度路徑之點覆蓋集合的元素個數稱之為K長度路徑數。在此篇論文，我們考慮具權重的K長度路徑之點覆蓋問題，我們將每個點給予權重，並其提出一個時間複雜度是O(n3)演算法解在仙人掌圖上

A subset S of vertices in graph G is a k-path vertex cover if every path of order
k in G contains at least one vertex from S. The cardinality of a minimum k-path
vertex cover is called the k-path vertex cover number of a graph G. In this thesis, we consider the weighted version of a k-path vertex cover problem, in which vertices are given weights, and propose an O(n3) algorithm for solving this problem in cactus graphs.

[1] H. B. Acharya, T. Choi, R. A. Bazzi, and M. G. Gouda, The K-observer problem in computer networks, in : Lecture Notes in Computer Science, 6976 (2011) 5–18.
[2] R. Boliac, K. Cameron, V.V. Lozin, On computing the dissociation number and the induced matching number of bipartite graphs, Ars Combin, 72 (2004) 241–253.
[3] B. Breˇsar, F. Kardoˇs, J. Katreniˇc, and G. Semaniˇsin, Minimum k-path vertex cover, Discrete Applied Mathematics, 159 (2011) 1189–1195.
[4] B. Breˇsar, M. Jakovac, J. Katreniˇc, G. Semaniˇsin, and A. Taranenko, On the vertex k-path cover, Discrete Applied Mathematics, 161 (2013) 1943–1949.
[5] B. Breˇsar, R. Krivoˇs-Belluˇs, G. Semaniˇsin, and P.ˇSparl, On the weighted k-path vertex cover problem, Discrete Applied Mathematics, 177 (2014) 14–18.
[6] F. G‥oring. J. Harant, D. Rautenbach, and I. Schiermeyer, On F-independence in graphs, Discussiones Mathematicae Graph Theory, 29 (2009) 377–383.
[7] F. Grandoni, J. Knemann, A. Panconesi, M. Sozio, A primaldual bicriteria distributed algorithm for capacitated vertex cover, SIAM J. Comput, 38 (2008) 825–840
[8] F. Harary, A chracterization of block graphs, Canadian Mathematic Bull, 6 (1982) 1–6
[9] M. Jakovac, The k-path vertex cover of rooted product graphs, Discrete Applied Mathematics, 187 (2015) 111–119
[10] M. Jakovac and A. Taranenko, On the k-path vertex cover of some graph products,Discrete Mathematics, 313 (2013) 94–100.
[11] F. Kardoˇs, J. Katreniˇc, I. Schiermeyer, On computing the minimum 3-path vertex cover and dissociation number of graphs, Theoret. Comput. Sci, 412 (2011) 7009–7017.
[12] R. M. Karp, Reducibility among combinatorial problems, in: R.E. Miller, J.W.
Thatcher (Eds.), Complexity of Computer Computations, Plenum Press, New York,
(1972) , pp. 85-104
[13] X. Liu, H. Lu, W. Wang, W. Wu, PTAS for the minimum k-path connected vertex
cover problem in unit disk graphs, J. Global Optim, 56 (2013) 449-458.
[14] Y. Li, J. A 2-approximation algorithm for the vertex cover P4 problem in cubic graphs,International Journal of Computer Mathematics, 91 (2014) 2103-2108.
[15] M. Novotny, Design and analysis of a generalized canvas protocol, in: Proceedings of WISTP 2010, in: LNCS, vol. 6033, Springer-Verlag, (2010), pp. 106-121.
[16] N. Safina Devia, Aniket C. Maneb, S. Mishra, Computational complexity of minimum P4 vertex cover problem for regular and k1,4-free graphs, Discrete Applied Mathematics, 184 (2015) 114–121
[17] J. Tu, F. Yang, The vertex cover P3 problem in cubic graphs, Inform. Process. Lett.113 (2013) 481-485.
[18] J. Tu, W. Zhou, A factor 2 approximation algorithm for the vertex cover P3 problem,Inform. Process. Lett. 111 (2011) 683–686.
[19] J. Tu, W. Zhou, A primaldual approximation algorithm for the vertex cover P3 problem, Theoret. Comput. Sci. 412 (2011) 7044-7048.
[20] D.B. West, Introduction to Graph Theory.(2nd ed.), River, N.J.: Prentice-Hall, 2001.
[21] M. Yannakakis, Node-deletion problems on bipartite graphs, SIAM Journal on Computing, 10 (1981) 310–327.