Node coverage problem

The articles node coverage problem and node coverage overlap thematically. Help me to better differentiate or merge the articles (→  instructions ) . To do this, take part in the relevant redundancy discussion . Please remove this module only after the redundancy has been completely processed and do not forget to include the relevant entry on the redundancy discussion page{{ Done | 1 = ~~~~}}to mark. Raynswor ( discussion ) 3:33 PM, May 22, 2017 (CEST)

The vertex coverage problem (often notated with VERTEX COVER ) is a problem of graph theory .

It asks whether, for a given simple graph and a natural number k, there is a vertex coverage of at most k . That is, if there is a maximum of k existing node subset U is the set of nodes such that each edge of the graph with at least one node U is connected.

The node coverage problem belongs to the list of 21 classical NP-complete problems, which Richard Karp was able to show in 1972 to belong to this class.