k-path Vertex Cover
doc. RNDr. Gabriel Semanišin, PhD.
Ústav informatiky, PF UPJŠ, Košice
The central problem is related to the concept of minimum k-path vertex cover. The same concept was studied also under the name k-observer problem. In both cases the concept is motivated by a real-life problems: the design of secure protocols for com- munication in wireless sensor networks and a controlling traffic in computer networks. Given a graph G = (V;E) and a positive integer k, a subset S of vertices of G is called a k-path vertex cover if S intersects all paths of order k in G; in other words, each path of order k contains a vertex from S. The minimum cardinality of a k-path vertex cover is called the k-path vertex cover number of a graph G, denoted by \psi_k(G). It is also natural to consider the weighted version of the k-path vertex cover problem. Obviously this problem is a generalization of the Minimum Weight Cover Problem that plays a central role in the Computational Complexity Theory. It is a special case of the Vertex Deletion Problem and provides an alternative to Feedback Problem.