Node overlap

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:34 PM, May 22, 2017 (CEST)

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

Two (non-minimal) node coverages.

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 . ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle U\subseteq V}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle U}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle U}$ ${\displaystyle G}$ ${\displaystyle v\in U}$ ${\displaystyle U}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle U}$ ${\displaystyle U}$ ${\displaystyle G}$ ${\displaystyle G}$

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

1. 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 .
2. 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.
3. 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. ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle k}$

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. ${\displaystyle M}$ ${\displaystyle G}$

 ${\displaystyle G=(V,E)}$: Graph

approx_vertex_cover( ${\displaystyle G}$)
1    ${\displaystyle K\leftarrow \varnothing }$
2  solange   ${\displaystyle E\neq \varnothing }$:
3      wähle eine beliebige Kante  ${\displaystyle e={u,v}\in E}$
4       ${\displaystyle K\leftarrow K\cup \left\{u,v\right\}}$
5      entferne alle Kanten aus  ${\displaystyle E}$, die inzident zu  ${\displaystyle u}$ oder  ${\displaystyle v}$ sind
6  return  ${\displaystyle K}$

With a suitable data structure, the algorithm has a runtime of . ${\displaystyle O(|E|)}$

Web links

Wikiversity: A lecture on node coverages as part of a discrete mathematics  course - course materials

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 .