Vertex Cover
In graph theory, a vertex cover is a subset of vertices that includes at least one endpoint of every edge. A minimum vertex cover is one of smallest possible size.
Find a vertex cover in an undirected graph.
Input
The input consists of the graph. The graph is represented as a list of edges. An edge is represented as a tuple of 2 integers: v u, where v and u are the vertices making the edge.
Vertex IDs are a consecutive range starting from 0, i.e., 0, 1, 2, ..., N - 1, where N is an arbitrary number of vertices. No edge connects a vertex to itself. Any pair of vertices has zero or one edge. Note: the graph is not necessarily connected.
Output
The output is expected to be whitespace separated list of integers denoting the vertices in the vertex cover.
Validation and Scoring
The output must:
- be a valid vertex cover
- not contain duplicates or invalid vertex IDs
The score is the size of the vertex cover. The objective is to minimize the score.
Example
Consider the following graph:
The trivial vertex cover is the set of all vertices with score 8. Here are two better vertex covers with scores 6 and 4.
Sample input
4 5
5 7
3 5
1 4
1 5
5 6
2 6
4 6
0 3
0 5
0 6
1 7
3 7
3 4
Inputs
| small_sparse.txt | 5.74KB | |
| small.txt | 14KB | |
| small_dense.txt | 22KB | |
| medium_sparse.txt | 777KB | |
| medium.txt | 1.94MB | |
| medium_dense.txt | 3.10MB | |
| large_sparse.txt | 97MB | |
| large.txt | 244MB | |
| large_dense.txt | 391MB |
[Log in] to test and submit a solution.