Destroy the graph in minimum number of steps

0
votes

There is a directed acyclic graph with N vertices and M edges. The aim is to destroy the graph - by deleting all of its vertices in minimum number of steps.

Rules for deletion in one step:

  1. At most 2 vertices can be deleted.
  2. A vertex can only be deleted if there is no edge from it to any non deleted vertex.
  3. If two vertices are deleted in one step there must not be an edge between them.

Constraints : N,M <= 10^6, and graph has no self loops and cycles.

1
algorithmdata-structuresgraphgraph-theorydirected-graph

1 Answers

3
votes

"An Almost-Linear Algorithm for Two-Processor Scheduling" by HAROLD N. GABOW gives an algorithm for this. pdf here.

The basic idea is to order the vertices into the minimum number of levels (each level is all the vertices that could be deleted at the same time if we ignored constraint 1), and then delete the vertices from highest level first.

The paper gives more details and a proof of optimality.

EDIT

To see how scheduling relates to the given problem, consider scheduling a set of jobs. Each job corresponds to a vertex. Dependencies of a job correspond to directed edges.

Constraint 2/3 correspond to saying that a job can only be scheduled once all the dependencies have been scheduled.

Constraint 1 corresponds to saying that only two jobs can be scheduled at once (i.e. a two-processor scheduling system).