11
$\begingroup$

I'm looking for a way to generate graphs so that the optimal vertex cover is known. There are no restrictions on the number of nodes or edges, only that the graph is completely connected.

the idea is to generate a graph that's not easy to find the optimal vertex cover, to be able to test different heuristics on it

I found the paper Arthur, J. & Frendeway, J. Generating Travelling-Salesman Problems with Known Optimal Tours, The Journal of the Operational Research Society, Vol. 39, No. 2 (Feb., 1988), pp. 153-159 for generating TSP with known optimal, alas I cannot access it.

Is there a known algorithm?

$\endgroup$
  • 6
    $\begingroup$ "There are no restrictions on the number of nodes or edges, only that the graph is completely connected." You need more restrictions that this. Otherwise, I generate the set of complete graphs and know optimal vertex covers for each one. $\endgroup$ – Tyson Williams Aug 14 '12 at 12:45
  • 3
    $\begingroup$ Here is a very simple approach: First, construct a matching $M$. For each edge $e \in M$, add one endpoint to your vertex cover $C$. Then add any number of additional nodes. Then add any number of edges, so that each edge has at least one endpoint in $C$. Necessarily $C$ will be a minimum vertex cover. (Unfortunately, there are lots of graphs that cannot be generated this way: e.g., $K_3$.) $\endgroup$ – Jukka Suomela Aug 14 '12 at 12:59
  • 5
    $\begingroup$ I suppose "generate a random bipartite graph and compute its vertex cover" doesn't count as a useful answer... $\endgroup$ – David Eppstein Aug 16 '12 at 19:00
  • 2
    $\begingroup$ there are many strategies for creating "hard" SAT instances & also repositories of archived "hard" instances if you're willing to go that route-- ie converting an instance of SAT to vertex cover. also theres much research studying SAT from an empirical pov which naturally translates into all other NP complete problems eg transition point etc. many refs on all of this... $\endgroup$ – vzn Aug 17 '12 at 17:57
  • 2
    $\begingroup$ Even more generally than the polynomial time solvability of Vertex cover on Koning graphs as noted by David, the following result is known from the area of parameterized complexity: there is a constant c such that for every fixed integer k, there is an O(n^c) time algorithm to test whether a graph has a vertex cover that exceeds its maximum matching size by at most k. Konig graphs are the special case when k=0. $\endgroup$ – Bart Jansen Aug 19 '12 at 12:31
9
+50
$\begingroup$

Expanding vzn's comment into an answer: The standard reduction from CNF-SAT to vertex cover is pretty easy: make a vertex for each term (variable or its negation), connect each variable to its negation by an edge, make a clique for each clause, and connect each vertex in the clique to the vertex for one of the terms in the clause. If you start with a satisfiability problem with a known satisfying assignment, this will give you a vertex cover problem with a known optimal solution (choose the term vertices given by the assignment, and in each clause clique choose all but one vertex, so that the clause vertex that is not chosen is adjacent to a term vertex that is chosen).

So now you need to find satisfiability problems that have a known satisfying assignment but where the solution is hard to find. There are many known ways of generating hard satisfiability problems (e.g. generate random k-SAT instances close to the satisfiability threshold) but the extra requirement that you know the satisfying assignment restricts the possibilities. One thing you can do here is go through another level of reduction, from a cryptographically hard problem such as factorization. I.e. choose two large primes p and q, set up a Boolean circuit for multiplying p and q as binary numbers, and translate it into a CNF formula in which there is a variable for each input (p and q) and for each intermediate value on a wire in the circuit, a clause for each output forcing it to have the right value, and a clause for each gate forcing the inputs and outputs of the gate to be consistent with each other. Then translate this CNF formula into vertex cover.

For a simpler strategy, choose the satisfying assignment to a 3CNF formula first, and then generate clauses at random, keeping only the clauses that are consistent with the assignment, and then convert to vertex cover. If the clauses have uniform probability this will be vulnerable to a degree-based heuristic (the term vertices that match the chosen assignment will have lower degree than the term vertices that do not) but this shortcoming can be avoided by adjusting the probabilities of the clauses according to how many of the clause's terms agree with the chosen assignment. Probably this is vulnerable to some kind of polynomial time attack but it might not be one that's natural for vertex cover, so it might make a good set of test instances despite not having much guarantee of hardness.

$\endgroup$
  • 2
    $\begingroup$ Relying on the hardness of factorisation is a very good idea. I think something along those lines is the best that we can expect if we want an efficient algorithm for generating vertex cover instances. Informally, this requirement forces us to focus on co-NP $\cap$ NP type problems, instead of NP-hard problems. $\endgroup$ – Jukka Suomela Aug 20 '12 at 22:31
1
$\begingroup$

closest ref I found was-- On hard instances of approximate vertex cover by Sundar Vishwanathan. did not see refs for looking at hard instances of the exact problem.

as in my comment, there is massive amt of research into this corresponding approach for SAT which is reducible to vertex cover.

re DEs comment, the idea of generating random instances and just choosing those instances that are hard for a standard algorithm seems totally reasonable to me esp with an empirical/experimental research approach[1], its a standard operating procedure for similar research into the SAT transition point.[2]

which by the way does have something to say where the "hard" region is for any other NP complete problem[3,4,5] which relates roughly to a critical point in the "density" of 1s in random instances specified in binary. for vertex cover this would probably correspond to edge density.

note that proving one can construct a set of hard instances, and only hard instances, is basically equivalent to the P vs NP problem. a more formal analysis of this equivalence is in the Razborov/Rudich Natural Proofs paper.

[1] experimental algorithmics

[2] SAT phase transition research

[3] Phase Transitions in NP Hard Problems

[4] Phase transitions in NP-complete problems: a challenge for probability, combinatorics, and computer science by Moore

[5] Phase transition behavior by Walsh

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.