3
$\begingroup$

Currently I'm using the well-known ratio-2 algorithm which is nice and fast, but I'm looking for an intuitive way to improve my results.

All the articles I read so far were way too complicated for me, I'm looking for simple ideas to improve the results.

What I got so far:

    def approx_vc(g):
        """
        Find a vertex cover that in the worst case is twice the size of the mvc (ratio 2).
        :param g: Graph object
        :return: Set of integers as vertices.
        """
        c = Set()
        e = g.get_edges()
        while len(e):
            u, v = e.pop()
            c.update([u, v])
            for edge in list(e):
                if u in edge or v in edge:
                    e.remove(edge)
        return c
$\endgroup$
3
  • $\begingroup$ In the instances that you care about, how large are the solutions typically found by your algorithm? The reason I ask is this: there are (even quite simple) algorithms that determine if there is a vertex cover of size at most $k$, and they run quickly when $k$ is small (say, $k \leq 50$ or so). $\endgroup$
    – Juho
    Nov 27, 2016 at 9:44
  • $\begingroup$ @Juho : ​ ​ ​ Are you aware of such an algorithm which improves in some respect on the Jianer-Iyad-Ge algorithm my answer links to? ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user12859
    Nov 27, 2016 at 16:46
  • $\begingroup$ @RickyDemer No, it's the current champion (still). What I was thinking was an earlier and slower algorithm running in $1.466^k$ time (and linear in the size of the graph), which should be easier to implement than the fastest one. Also, to be honest, I didn't notice your answer was already mentioning FPT algorithms. $\endgroup$
    – Juho
    Nov 27, 2016 at 16:54

4 Answers 4

9
$\begingroup$

A short trip to wikipedia will tell you that there is no known better approximation algorithm for vertex cover (at least when by "better" we require an improvement by a constant independent of the input).

This is what is known so far:

  • The best known approximation achieves an approximation factor of $2-\Theta\left(\frac{1}{\sqrt{\log V}}\right)$ [1].

  • VC is NP-hard to approximate within a factor of $1.3606$ (meaning that if we have a polynomial approximation algorithm with this factor then $\mathsf{P}=\mathsf{NP})$ [2].

  • If the unique games conjecture holds, then VC is NP-hard to approximate within a factor of $2-\epsilon$, for all $\epsilon>0$ [3]. So if there exists a $2-\epsilon$ approximation for VC, then either $\mathsf{P}=\mathsf{NP}$, or the unique games conjecture fails.

Thus, any better approximations than the naive one you presented will solve open questions in complexity, so you are not likely to find them here (and they might not exist at all).


1. G. Karakostas, A better approximation ratio for the vertex cover problem, ACM Trans. Algorithms (TALG) 5 (4) (2009) 41.

2. Dinur, Irit; Safra, Samuel (2005). "On the hardness of approximating minimum vertex cover". Annals of Mathematics. 162 (1): 439–485.

3. Khot, Subhash; Regev, Oded (2008). "Vertex cover might be hard to approximate to within 2−ε". Journal of Computer and System Sciences. 74 (3): 335–349.

$\endgroup$
6
$\begingroup$

Although, as posted by Ariel, there is no known way to obtain theoretically better results, there are many ways to improve on it in practice. A typical technique is a local search algorithm, that applies some small modifications to the current solution to look for better results.

As a first improvement, I would try randomizing your algorithm and run it several times to get a better solution: u, v = random.sample(e, 1)

Then you can try using more elaborate algorithms, such as simulated annealing: you just need to define a way to find "close" solutions, such as removing a few vertices from your solution and restarting your (randomized) algorithm.

A few papers have been published on local search for this particular problem if you want even better - but more complex - algorithms. Here is an example: Shaowei Cai, Kaile Su, Abdul Sattar (2012), Two New Local Search Strategies for Minimum Vertex Cover

$\endgroup$
0
3
$\begingroup$

Ariel has covered worst-case approximation, so I'll mention two cases in which you can efficiently get an exact answer.

By this paper, that can be done whenever the size of the minimum vertex cover is not too large. ​ (i.e., the size of the graph is otherwise mostly-irrelevant.)

Like lots of graph problems, that can also be done whenever the treewidth is not too large.

This paper gives efficient way of approximating the treewidth, and section 1.2 cites ways of efficiently finding low-width tree-decompositions.

$\endgroup$
-1
$\begingroup$

I proposed a better approximation algorithm for vertex cover problem (a 1.999999-approximation algorithm by solving a well-known SDP model and a randomized procedure). It is not published, yet. But, I am sure that it is true (I am grateful if anyone identify any potential issues).

To clarify the main topics of the idea, first of all, we prove that,

  1. If the optimal VCP value is greater than $n/2+n/k$ then for all VCP feasible solutions, we have the approximation ratio $2k/(k+2)<2$,
  2. Based on a feasible VCP solution with objective value smaller than $kn/(k+1)$ , we have the approximation ratio $2k/(k+1)<2$.

Then, to fix the value $k$ and to produce a constant factor better than $2$, we solve a well-known SDP relaxation and do as follows:

Step 1. Let $V_{-1}=\{j:v_o^* v_j^*<0\}$, and $V_1=V-V_{-1}$ which is a feasible VCP solution.

If $|V_{-1}|>0.000001n$ then $|V_1 |< 0.999999n$ and based on (2) we have an approximation ratio $(2(999999))/(999999+1)≤1.999999$. Else, let $ε=0.0004$ and $G_ε=\{j∈V│0≤v_o^* v_j^*≤+ε\}$ and $A=\{j∈V│v_o^* v_j^*>+ε\}$.

Step 2. If $|A|>0.01n$, then, we can prove that the optimal VCP value is greater than $n/2+0.0000015n$ and then based on (1) we have an approximation ratio $(2×1/0.0000015)/(1/0.0000015+2)≤1.999999$. Else, we know that $|G_ε |≥(1-0.000001-0.01)n=0.989999n$. Now, it is sufficient to introduce a suitable feasible VCP solution based on $G_ε$.

Step 3. We prove that for any normalized vector $w$, the induced subgraph on $H_w=\{j∈G_ε;|wv_j^*|>0.5003\}$ is a bipartite graph. As a result, by introducing a set $H_w$ where $|H_w |>0.000001n$, we can produce a feasible VCP solution where $|V_{-1}|≥0.000001n/2$ and $|V_1|≤(1-0.000001/2)n= 1999999n/2000000$, with a performance ratio of $(2(1999999))/(1999999+1)= 1.999999$.

Finally, to introduce a suitable set $H_w$, we prove that, by introducing two random vectors $u$ and $w$, one of the sets $H_u$ or $H_w$ has more than $0.000001n$ members. As a result we could introduce an approximation ratio of $1.999999$ on arbitrary graphs and based on the proposed $1.999999$- approximation algorithm for VCP, the unique games conjecture is not true.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.