# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Find a vertex cover not much larger than the minimal cover

Contributed by:
Wolfram Staff (original content by Sriram V. Pemmaraju, Steven S. Skiena and Daniel Lichtblau)

ResourceFunction["ApproximateVertexCover"][ returns a vertex cover of graph | |

ResourceFunction["ApproximateVertexCover"][ tries to improve the vertex cover |

Possible forms for *vlist* are:

All | all vertices of g |

Automatic | endpoints of the largest independent edge set of g |

{v_{1},v_{2},…} | specified vertices v_{i} |

The default value of *vlist* is All.

The greedy heuristic deletes edges that are incident on the maximum degree vertex in *vlist* and repeats the procedure until all edges of *g* are covered.

The greedy algorithm is a natural heuristic for constructing a vertex cover, but it can produce poor vertex covers.

ResourceFunction["ApproximateVertexCover"][*g*,Automatic] uses a vertex cover constructed with FindIndependentEdgeSet[*g*] and is guaranteed to be within two times the minimal.

ResourceFunction["ApproximateVertexCover"][*g*,*vlist*] does not necesserily improve the size of the vertex cover.

ResourceFunction["ApproximateVertexCover"] works with undirected graphs, directed graphs, multigraphs and mixed graphs.

ResourceFunction["ApproximateVertexCover"] works with large graphs.

ResourceFunction["ApproximateVertexCover"] takes the Method option, with possible values as follows:

Automatic | pick the method automatically |

"Greedy" | greedy heuristic with dynamic updates |

"IndexedHeap" | greedy heuristic with tracking vertices in an indexed heap |

"GreedyStatic" | simplified greedy heuristic |

With Method→Automatic (default), ResourceFunction["ApproximateVertexCover"] switches from the "Greedy" method to "IndexedHeap" for larger graphs.

The simplified greedy heuristic "GreedyStatic" is generally faster than other methods, but can give somewhat larger covers.

Find an approximate vertex cover:

In[1]:= |

In[2]:= |

Out[2]= |

Show the cover:

In[3]:= |

Out[3]= |

Use the greedy heuristic to find an approximate vertex cover starting from the full vertex set:

In[4]:= |

Out[4]= |

In[5]:= |

Out[5]= |

This is the same as:

In[6]:= |

Out[6]= |

Improve a vertex cover:

In[7]:= |

Out[7]= |

In[8]:= |

Out[8]= |

Use endpoints of the largest independent edge set of *g* as a starting point:

In[9]:= |

Out[9]= |

In[10]:= |

Out[10]= |

ApproximateVertexCover works with undirected graphs:

In[11]:= |

Out[11]= |

Directed graphs:

In[12]:= |

Out[12]= |

Multigraphs:

In[13]:= |

Out[13]= |

Mixed graphs:

In[14]:= |

Out[14]= |

ApproximateVertexCover works with large graphs:

In[15]:= |

In[16]:= |

Out[16]= |

In[17]:= |

In[18]:= |

Out[18]= |

In[19]:= |

Out[19]= |

In[20]:= |

Out[20]= |

The dynamic greedy heuristic is the default for relatively small graphs:

In[21]:= |

Out[21]= |

In[22]:= |

Out[22]= |

In[23]:= |

Out[23]= |

Method→"IndexedHeap" is most advantageous for larger graphs, for which it is the default:

In[24]:= |

Out[24]= |

In[25]:= |

Out[26]= |

For relatively smaller graphs, Method→"Greedy" can be faster, while giving a comparable cover:

In[27]:= |

Out[28]= |

In[29]:= |

Out[29]= |

In[30]:= |

Out[30]= |

Method→"GreedyStatic" is faster for both small and large graphs, at the expense of giving somewhat larger covers:

In[31]:= |

In[32]:= |

In[33]:= |

In[34]:= |

In[35]:= |

Out[35]= |

In[36]:= |

Out[36]= |

The result of ApproximateVertexCover can be tested by VertexCoverQ:

In[37]:= |

Out[37]= |

In[38]:= |

Out[38]= |

ApproximateVertexCover may return results similar to FindVertexCover:

In[39]:= |

Out[39]= |

In[40]:= |

Out[40]= |

In[41]:= |

Out[41]= |

In[42]:= |

Out[42]= |

However, it does this in less time:

In[43]:= |

Out[43]= |

However, ApproximateVertexCover may also return covers of a larger size compared to FindVertexCover:

In[44]:= |

Out[44]= |

In[45]:= |

Out[45]= |

Using the Automatic value for *vlist* may give a smaller cover:

In[46]:= |

Out[46]= |

In[47]:= |

Out[47]= |

ApproximateVertexCover[*g*,All] may return covers that are equivalent, smaller or larger than ones given by ApproximateVertexCover[*g*,Automatic]:

In[48]:= |

Out[48]= |

Although the algorithm in ApproximateVertexCover[*g*,Automatic] is guaranteed to give results not exceeding the minimal size by a factor of two, in practice the difference is often smaller:

In[49]:= |

Out[49]= |

Similarly, although ApproximateVertexCover[*g*] comes with no performance guarantees, in practice it often gives results that are not much worse than the minimal:

In[50]:= |

Out[50]= |

ApproximateVertexCover[*g*,{*v*_{1},*v*_{2},…}] works only if {*v*_{1},*v*_{2},…} is a vertex cover:

In[51]:= |

In[52]:= |

Out[52]= |

If you do not have a suitable vertex cover to improve, try using ApproximateVertexCover[*g*] without *vlist*:

In[53]:= |

Out[53]= |

- 2.0.0 – 02 October 2020
- 1.0.0 – 21 September 2020

This work is licensed under a Creative Commons Attribution 4.0 International License