7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why do you think that it's a bipartite graph? $\endgroup$ – Joe Mar 5 '13 at 7:09
  • $\begingroup$ it is not , but it is possible to apply minimum path cover in a directed graph . $\endgroup$ – palatok Mar 5 '13 at 11:48
  • 2
    $\begingroup$ Cross-posted at: stackoverflow.com/questions/15211918/… . Please do not cross-post across multiple SE sites at the same time. If you do not receive a satisfactory answer on the original post for a few days, you can post at another site in the network. In such a case, add a link to the other post in each of your posts, so that people know where you stand, and avoid duplicate work. $\endgroup$ – Paresh Mar 5 '13 at 15:33
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.