How to find the maximum independent set of a directed graph?

Problem Detail: 

I'm trying to solve this problem.

Problem: Given $n$ positive integers, your task is to select a maximum number of integers so that there are no two numbers $a, b$ in which $a$ is divisible by $b$.

I have to find the Maximum independent set and the size of this set. The size can be found by König's theorem. But how can I find the Maximum Independent Set (i.e. which vertex are part of the set).

I did some search also and found something here:

If removing a vertex does not change minimum path cover then I can get the desired result without that vertex.

But I don't understand the underlying theorem. Any help will be greatly helpful.

Asked By : palatok

Answered By : Joe

You are trying to find the width of the poset defined by the given subset of integers and the divisibility relation. The width is the maximum number of anti-chains, which is the same as the maximum set of incomparable elements in the poset.

This corresponds exactly to the maximum independent set in the Comparability Graph, where each integer is a vertex and there is an edge from $u$ to $v$ if and only if $u$ divides $v$.

Finding the maximum independent set in general is a hard problem, but comparability graphs are a special case for which efficient algorithms exist.

Dilworth's Theorem characterizes the width of any poset as a partition of the poset into chains (source to sink paths in the directed comparability graph). Dilworth's Theorem is equivalent toKönig's theorem on Bipartite Matching, which, as you suggested, leads to an algorithm. The bipartite graph you construct in order to use Konig's theorem and find the maximum independent set via a bipartite matching is described simply in the above Wikipedia link. For completeness, we include it here (in annotated form):

"Define a bipartite graph $G = (U,V,E)$ where $U = V = S$ [the set of integers] and where (u,v) is an edge in $G$ when $u < v \in S$ [integer $u$ divides integer $v$]. By König's theorem, there exists a matching $M$ in $G$, and a set of vertices $C$ in $G$, such that each edge in the graph contains at least one vertex in $C$ and such that $M$ and $C$ have the same cardinality $m$.

"Let $A$ be the set of elements of S that do not correspond to any vertex in $C$; then $A$ has at least $n - m$ elements (possibly more if $C$ contains vertices corresponding to the same element on both sides of the bipartition). Let $P$ be a family of chains formed by including $x$ and $y$ in the same chain whenever there is an edge $(x,y)$ in M$; then $P$ has $n - m$ chains. Therefore, we have constructed an antichain and a partition into chains with the same cardinality."

The set of distinct vertex labels (integers) in $A$ is the answer to your question.

Section 3 of the paper Online Algorithms for Dilworth's Chain Partition by Ikiz and Garg describes two different offline algorithms to compute the chain partition, and thus the independent set you are looking for. One of the algorithms is based on the Bipartite matching method.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10274