Minimum k-path vertex cover

详细信息    查看全文

• 作者：Boš ; tjan Breš ; ar^a ; ^b ; ^{bostjan.bresar@uni-mb.si"" rel=""nofollow} ; Františ ; ek Kardoš ; ^c ; ^{frantisek.kardos@upjs.sk"" rel=""nofollow} ; Já ; n Katreni&#x10d ; ^d ; ^{jan.katrenic@upjs.sk"" rel=""nofollow} ; Gabriel Semaniš ; in^d ; ^{gabriel.semanisin@upjs.sk"" rel=""nofollow}
• 关键词：Algorithm ; Path ; Vertex cover ; Dissociation number ; Path vertex cover ; NP-complete
• 刊名：Discrete Applied Mathematics
• 出版年：2011
• 出版时间：28 July 2011
• 年：2011
• 卷：159
• 期：12
• 页码：1189-1195
• 全文大小：245 K

文摘

A subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. Denote by ψ_k(G) the minimum cardinality of a k-path vertex cover in G. It is shown that the problem of determining ψ_k(G) is NP-hard for each k≥2, while for trees the problem can be solved in linear time. We investigate upper bounds on the value of ψ_k(G) and provide several estimations and exact values of ψ_k(G). We also prove that ψ₃(G)≤(2n+m)/6, for every graph G with n vertices and m edges.