Minimum Vertex Cover Brute Force

[Accname]

Hi guys.

I need an algorithm which solves the minimum vertex cover problem deterministicly.
I need a definitely correct result, no approximation.

Has somebody a good suggestion how I write it in java?

I thought of something like this:

for i in [0...vertexCount]
    for every set of vertices S of size i
        if S is a vertex cover
            return i
        end
    end
end

But I have a problem with the "every set of vertices S of size i" part. How would I make it at least a little bit efficient.

Thanks guys.

 

[s3rius]

The minimum vertex cover (MVC from here on) is a NP-complete problem so you wont fare much better than that.

One thing I could think of is:
If you have an outlier - a vertex A that has only a single edge leading to a vertex B - then you know that either A or B will always have to be in the set that compose the MVC.

You can now simply decide that B will always have to be in the MVC set and A will never be. That's the best decision since B potentially has a lot of edges, while A only has one.
With this you can reduce your 0...vertexCount because you don't have to consider A and B as candidates.

 

[Accname]

Yeah, I know that.
I am currently working on an approximation algorithm which works kinda like what you described there.
However, I need a brute force algorithm to test the results of my algorithm and see how good it is.
But since I need to run the brute force algorithm to see the difference in result it should better not have completely terrible performance.

I currently have like an array of vertices v1...vn each with an individual weight(v) := "number of adjacent vertices" and a list of adjacent vertices.