En delmängd S av hörn av en graf G kallas en k-pat vertex om varje sökväg av ordning k i G innehåller minst en vertex från S. Beteckna med  på k (G) den minsta kardinaliteten av en k-pat vertex omslag i G. Det visas att problemet med att bestämma  på k (G) är NP-hård för varje k ≥ 2, medan för träd problemet kan lösas i linjär tid. Vi undersöker övre gränser på värdet av  på k (G) och ger flera uppskattningar och exakta värden av  på k (G). Vi bevisar också att  med 3 (G) ≤ (2n + m)/6, för varje graf G med n hörn och m kanter.
Tyvärr, datorisering ett minimum k-path omslag är NP-hård REF.
Minimum k-path vertex cover
{'venue': 'Discret. Appl. Math.', 'journal': 'Discret. Appl. Math.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}