Node overlap
In graph theory, a node cover denotes a subset of the node set of a graph that contains at least one end node from each edge. Finding the smallest nodal coverages is considered to be algorithmically difficult, because the closely related nodal cover problem is NP-complete .
Definitions
Let be an undirected graph with the node set and the edge set . Then a subset of a vertex cover (Vertex Cover) of , when each edge of at least one node contains. Correspondingly, an edge covering of the graph is a subset of its edge set, so that each node is contained in at least one edge from . A node coverage of is called minimal if there is no node , so that without there is still a node coverage. If there is no node coverage in which contains fewer elements than it is called a smallest node coverage . The number of nodes of a smallest node coverage of is called the node coverage number of .
Directed graphs or graphs with multiple edges are not the subject of such considerations, since the direction or multiplicity of the edges is not important.
Important statements and sentences
- The vertex coverage number of a graph is at least as large as its pairing number , since the vertices of the edges of a largest pairing can only be incident to one pairing edge .
- On the other hand, the node coverage number can be at most twice the pairing number, since the nodes of all pairing edges result in a valid node coverage.
- In bipartite graphs, the node coverage number and the pairing number match.
Problems and complexities
The decision problem for a graph and a natural number to decide whether a node coverage of the size contains at most is called the node coverage problem . The associated optimization problem asks for the number of vertex coverage of a graph. The associated search problem asks for a smallest node coverage.
Proof of NP severity
The node coverage problem is NP-complete , the associated optimization and search problem is NP-equivalent . The NP severity of the node coverage problem follows from the theorem that the stability number of a graph always corresponds to the number of nodes in a graph minus its node coverage number, because the complement of a smallest node coverage is always a largest stable set and vice versa. 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.
Cases solvable in polynomial time
However, König was able to show as early as 1931 that the vertex coverage number in bipartite graphs corresponds to the pairing number ( König theorem ). However , there is a polynomial algorithm for the problem of finding a largest pairing . In bipartite graphs, therefore, even the smallest vertex coverage and the largest stable set can be calculated in polynomial time. In fact, it is even more true that the vertex coverage number in perfect graphs can be calculated in polynomial time.
Approximation of a node cover
There is an approximation algorithm that calculates a node coverage with relative quality 2. No better fixed-quality algorithm is known.
The algorithm computes a non-extensible pairing in . Since such a pairing always represents a node coverage and is at most twice as large as a minimum node coverage, the algorithm calculates a node coverage with relative quality 2.
: Graph
approx_vertex_cover() 1 2 solange : 3 wähle eine beliebige Kante 4 5 entferne alle Kanten aus , die inzident zu oder sind 6 return
With a suitable data structure, the algorithm has a runtime of .
Web links
literature
- Reinhard Diestel : graph theory . 4th edition. Springer, Berlin 2010, ISBN 978-3-642-14911-5 ( diestel-graph-theory.com ).
- Bernhard Korte , Jens Vygen : Combinatorial Optimization. Theory and algorithms (= Springer spectrum ). 2nd Edition. Springer, Heidelberg 2012, ISBN 978-3-642-25400-0 .