CODEWITHSUNDEEP
algorithmgraphgraph-theorydirected-acyclic-graphsbipartite
Benson Lin
Benson Lin

Reputation: 1404

Size of Special Vertex Set on DAG

In Singapore, this year's (2016) NOI (National Olympiad in Informatics) included the following problem "ROCKCLIMBING" (I was unable to solve it during the contest.) :

Abridged Problem Statement

Given a DAG with N <= 500 vertices, find the maximum number of vertices in a subset of the original vertices such that there is no path from 1 vertex in the set to another vertex in the same set, directly or indirectly.

Solution

The solution was to use transitive closure algorithm, and then to form a bipartite graph by duplicating each vertex i to form i' such that if vertex j can be reached from vertex i directly or indirectly in the original graph, then there is a directed edge from i to j' in the new graph.

However, during the solution presentation, the presenters did not explain how or why N - MCBM (MCBM being the Maximum Cardinality Bipartite Matching) of the new bipartite graph is also the maximum size of the set of vertices that cannot reach each other directly or indirectly in the original DAG.

I looked up other problems related to DAGs and bipartite graphs, such as the Minimum Path Cover problem on DAGs, but I could not find anything that explains this.

Does anyone know a way in which to prove this equality?

The problem statement can be found here: ROCKCLIMBING

Thank you in advance.

Upvotes: 2

Views: 467

Answers (2)

Peter de Rivaz
Peter de Rivaz

Reputation: 33519

An alternative viewpoint is as follows:

  1. If we use A<B to mean we can climb from A to B, we have defined a partially ordered set

  2. There is a result called Dilworth's theorem that says the maximum number of incomparable elements is equal to the minimum number of chains

The proof shows how to construct the minimum number of chains by constructing a maximum matching in your bipartite graph.

Upvotes: 0

Peter de Rivaz
Peter de Rivaz

Reputation: 33519

There are two things going on here:

  1. A set is independent if and only if its complement is a vertex cover (see wikipedia). This means that the size of a max independent set is equal to the size of a minimum vertex cover.

  2. Konig's theorem proves that

In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.

Therefore to find the size of the max independent set we first compute the size MCBM of the max matching, and then compute its complement which equals N-MCBM.

Upvotes: 1

Related Questions