Basic Examples (2) 

Find an approximate vertex cover:

In[1]:=

In[2]:=

Out[2]=

Show the cover:

In[3]:=

Out[3]=

Scope (5) 

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]=

Options (2) 

Method (2) 

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]=

Properties and Relations (7) 

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]=

Possible Issues (2) 

ApproximateVertexCover[g,{v₁,v₂,…}] works only if {v₁,v₂,…} 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]=