CSC349-Assignment 5 Greedy Algorithms Solved

A greedy algorithm is one that assumes it can repeatedly make locally optimal choices, never having to backtrack, always arriving at a globally optimal solution. The greedy approach can be applied to a wide variety of problems, including those that involve graphs.

Part 1: k-Cores
A k-core is a maximal connected subgraph within which every vertex has degree at least k. They have applications in graph-based problems as a computationally inexpensive way of approximating the most densely connected regions of a graph. For example, consider the following undirected graph:

 

All seven vertices in this graph can be found within a 1-core, since they all have a degree of at least 1.

However, the 2-core contains only vertices v0, v1, and v2. Note that although the graph contains a vertex of degree 3 (as well as one of degree 5), there is no 3-core — there is no subgraph within which every vertex has degree 3. Vertex v2 has degree 3, but its neighbor v0, for example, only has degree 2. This means that v0 cannot be in a 3-core, and without v0, v2’s degree falls below 3.

Perhaps more importantly, from the perspective of a greedy approach, note that the k-cores form a nesting hierarchy of vertices: any vertices in the i-core must necessarily also be in the (i − 1)-core, but there can be vertices in the (i − 1)-core that are not in the i-core.

In your programming language of choice per Assignment 1, implement a greedy algorithm to compute the k-cores of a graph. Think carefully about what metric your algorithm will be greedy over[1] and what data structures it will use to keep track of that information. You should be able to produce all of the k-cores of a graph in linear O(|V | + |E|) time2.

Each input graph will be provided as an edge list: each edge in the graph will be represented by a commaseparated pair of vertex identifiers, indicating an edge between the first vertex and the second.

You may assume that vertex identifiers are contiguous natural numbers — they begin at 0, and there will be

no “gaps” in the identifiers used. You may also assume that the graph will be simple and will not contain any isolated vertices3.

1st
For example, the above graph could be represented as:

0, 1 0, [2]1, 2 1, 4 1, 5 1, 6 2, 3

Your program must accept as a command line argument the name of a file containing an edge list as described above, then print to stdout the k-cores according to the following format:

· Every non-empty k-core must be printed, starting with k = 1.

· For each value of k, all vertices in such k-core(s) must appear on a single comma-separated line.

· Each line’s vertices must be sorted in ascending order. Note that vertex identifiers are integers, not strings. The lines themselves must be sorted in ascending order by k. For example:

$ ./compile.sh $ ./run.sh in1.txt Vertices in 1-cores:

0, 1, 2, 3, 4, 5, 6

Vertices in 2-cores:

0, 1, 2

Your program will be tested using diff, so its printed output must match exactly.


 
[1] of 3
[2] of 3