<p>closest ref I found was-- <a href="http://dl.acm.org/citation.cfm?id=1435375.1435382" rel="nofollow noreferrer">On hard instances of approximate vertex cover</a> by Sundar Vishwanathan. did not see refs for looking at hard instances of the exact problem.</p>

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

<p>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] </p>

<p>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.</p>

<p>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.</p>

<p>[1] <a href="https://cstheory.stackexchange.com/a/5084/7884">experimental algorithmics</a></p>

<p>[2] <a href="https://cstheory.stackexchange.com/a/4404/7884">SAT phase transition research</a></p>

<p>[3] <a href="https://cstheory.stackexchange.com/questions/3841/phase-transitions-in-np-hard-problems">Phase Transitions in NP Hard Problems</a></p>

<p>[4] <a href="http://www.math.ucla.edu/~roch/ams2010_files/moore.pdf" rel="nofollow noreferrer">Phase transitions in NP-complete problems:
a challenge for probability, combinatorics, and
computer science</a> by Moore</p>

<p>[5] <a href="http://www.cse.unsw.edu.au/~tw/phase.ppt" rel="nofollow noreferrer">Phase transition behavior</a> by Walsh</p>

CC BY-SA 3.0
2012-08-17T18:21:24.780Z
2012-08-17T19:15:01.527Z
2017-04-13T12:32:28.053Z
vzn
<p>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).</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-08-20T22:31:52.507Z
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.
Jukka Suomela
CC BY-SA 3.0
2012-08-19T21:37:15.510Z
2012-08-19T21:37:15.510Z
David Eppstein
<p>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.</p>

<p><em>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</em></p>

<p>I found the paper <a href="http://www.jstor.org/discover/10.2307/2582378?uid=3737512&amp;uid=2&amp;uid=4&amp;sid=21101132412531">Arthur, J. &amp; 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</a> for generating TSP with known optimal, alas I cannot access it.</p>

<p>Is there a known algorithm?</p>

CC BY-SA 3.0
2012-08-14T12:45:51.650Z
"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.
Tyson Williams
CC BY-SA 3.0
2012-08-14T12:59:38.487Z
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$.)
Jukka Suomela
CC BY-SA 3.0
2012-08-14T15:27:38.763Z
@JukkaSuomela I've been doing some tests, but I must be doing something wrong. When you say "add one endpoint to your vertex cover" does it mean any endpoint of the edge? Because I tried this and sometimes the cover doesn't cover all edges, and if I add both nodes then it isn't minimal
AndresQ
CC BY-SA 3.0
2012-08-15T01:06:48.817Z
@Shaga, Jukka's construction works, you have a set of independent vertices $I$ with a matching to a set of vertices $C$. You can stick any edges in that maintain $I$'s independence (assuming you have the matching as a base). In this case $|I| = |C|$, you can push it a little further and have $|I|\geq|C|$, as long as $C$ is matched into $I$ (i.e. there's a matching between $C$ and $I$ such that all the vertices in $C$ are matched).
Luke Mathieson
CC BY-SA 3.0
2012-08-15T15:43:32.080Z
I'm sorry but I still can't figure it out.
On [this image](http://i45.tinypic.com/arsw1.png) is a generated graph that I made with Jukka's method.

The yellow edges are the matching, and the yellow vertices are the vertex cover, if I add *both* vertices for each edge of the matching

However, if I'm not mistaken, the left vertex of the upper right matching edge isn't necessary, and it can be removed from the cover set, hence the cover isn't minimal.

On the other hand if I add to C only one vertex for each M, then it isn't a proper vertex cover... what am I missing?
AndresQ
CC BY-SA 3.0
2012-08-16T15:48:18.290Z
@Shaga: You start with an empty graph $G$. You first construct $M$; you add these edges and their endpoints to $G$. Then you choose your $C$, *one* endpoint of each edge in $M$; now your $C$ is fixed. Then you can add any number of nodes and edges to $G$, but every time you add an edge, you have to make sure that at least one endpoint of the edge is in $C$.
Jukka Suomela
CC BY-SA 3.0
2012-08-16T19:00:14.307Z
I suppose "generate a random bipartite graph and compute its vertex cover" doesn't count as a useful answer...
David Eppstein
CC BY-SA 3.0
2012-08-17T00:12:45.960Z
@JukkaSuomela I understand now you algorithm, and it works, the problem is that the kind of graphs it generates are almost always (_I think always_) solvable with a simple **max degree** heuristic. I'm wondering if there's another way to generate _harder_ graphs. If not I'll give you the answer and the bounty :)
AndresQ
CC BY-SA 3.0
2012-08-17T01:20:34.640Z
I doubt max degree works for Jukka's graphs, but I think they can still be solved in polynomial time. Find and remove the edges that cannot be part of a perfect matching (they are all the C-C edges, and possibly some others); then the remaining graph is bipartite and the optimal cover is one side of the bipartition in each of its connected components. To choose which side to use, solve a 2-sat problem with a variable for each component and a constraint for each of the removed edges.
David Eppstein
CC BY-SA 3.0
2012-08-17T07:19:46.460Z
On further searching: Jukka's graphs appear to be exactly the König-Egerváry graphs (graphs in which vertex cover = maximum matching). And polynomial time algorithms for finding vertex covers in these graphs (not necessarily the same as the one I outlined in my comment) have been long known.
David Eppstein
CC BY-SA 3.0
2012-08-17T17:57:22.367Z
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...
vzn
CC BY-SA 3.0
2012-08-19T12:31:29.850Z
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.
Bart Jansen
<ds.algorithms><graph-theory><graph-algorithms>
How to generate graphs with known optimal vertex cover
AndresQ
# How to generate graphs with known optimal vertex cover

(Asked by: username_0 on 2012-08-14)

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](http://www.jstor.org/discover/10.2307/2582378?uid=3737512&uid=2&uid=4&sid=21101132412531) for generating TSP with known optimal, alas I cannot access it.

Is there a known algorithm?

**Tags:** ds.algorithms, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: "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.  
> **username_2**: 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$.)  
> **username_0**: @JukkaSuomela I've been doing some tests, but I must be doing something wrong. When you say "add one endpoint to your vertex cover" does it mean any endpoint of the edge? Because I tried this and sometimes the cover doesn't cover all edges, and if I add both nodes then it isn't minimal  
> **username_3**: @Shaga, Jukka's construction works, you have a set of independent vertices $I$ with a matching to a set of vertices $C$. You can stick any edges in that maintain $I$'s independence (assuming you have the matching as a base). In this case $|I| = |C|$, you can push it a little further and have $|I|\geq|C|$, as long as $C$ is matched into $I$ (i.e. there's a matching between $C$ and $I$ such that all the vertices in $C$ are matched).  
> **username_0**: I'm sorry but I still can't figure it out. On [this image](http://i45.tinypic.com/arsw1.png) is a generated graph that I made with Jukka's method.  The yellow edges are the matching, and the yellow vertices are the vertex cover, if I add *both* vertices for each edge of the matching  However, if I'm not mistaken, the left vertex of the upper right matching edge isn't necessary, and it can be removed from the cover set, hence the cover isn't minimal.  On the other hand if I add to C only one vertex for each M, then it isn't a proper vertex cover... what am I missing?  
> **username_2**: @Shaga: You start with an empty graph $G$. You first construct $M$; you add these edges and their endpoints to $G$. Then you choose your $C$, *one* endpoint of each edge in $M$; now your $C$ is fixed. Then you can add any number of nodes and edges to $G$, but every time you add an edge, you have to make sure that at least one endpoint of the edge is in $C$.  
> **username_4**: I suppose "generate a random bipartite graph and compute its vertex cover" doesn't count as a useful answer...  
> **username_0**: @JukkaSuomela I understand now you algorithm, and it works, the problem is that the kind of graphs it generates are almost always (_I think always_) solvable with a simple **max degree** heuristic. I'm wondering if there's another way to generate _harder_ graphs. If not I'll give you the answer and the bounty :)  
> **username_4**: I doubt max degree works for Jukka's graphs, but I think they can still be solved in polynomial time. Find and remove the edges that cannot be part of a perfect matching (they are all the C-C edges, and possibly some others); then the remaining graph is bipartite and the optimal cover is one side of the bipartition in each of its connected components. To choose which side to use, solve a 2-sat problem with a variable for each component and a constraint for each of the removed edges.  
> **username_4**: On further searching: Jukka's graphs appear to be exactly the König-Egerváry graphs (graphs in which vertex cover = maximum matching). And polynomial time algorithms for finding vertex covers in these graphs (not necessarily the same as the one I outlined in my comment) have been long known.  
> **username_5**: 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...  
> **username_6**: 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.  

---

## 2 answers

### Answer by username_4 on 2012-08-19. Score: 10 | Accepted answer

Expanding username_5'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.

> **Comments:**
> **username_2**: 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.  

---

### Answer by username_5 on 2012-08-17. Score: 2

closest ref I found was-- [On hard instances of approximate vertex cover](http://dl.acm.org/citation.cfm?id=1435375.1435382) 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](https://cstheory.stackexchange.com/a/5084/7884)

[2] [SAT phase transition research](https://cstheory.stackexchange.com/a/4404/7884)

[3] [Phase Transitions in NP Hard Problems](https://cstheory.stackexchange.com/questions/3841/phase-transitions-in-np-hard-problems)

[4] [Phase transitions in NP-complete problems:
a challenge for probability, combinatorics, and
computer science](http://www.math.ucla.edu/~roch/ams2010_files/moore.pdf) by Moore

[5] [Phase transition behavior](http://www.cse.unsw.edu.au/~tw/phase.ppt) by Walsh


---

