How can I get the antichain elements in SPOJ-DIVREL?

Question

Problem: http://www.spoj.com/problems/DIVREL

In question, we just need to find the maximum number of elements which are not multiples (a divisible by b form) from a set of elements given. If we just make an edge from an element to its multiple and construct a graph it will be a DAG.

Now the question just changes to finding the minimum number of chains which contain all the vertices which equals the antichain cardinality using Dilworth's theorem as it is a partially ordered set.

Minimum chains can be found using bipartite matching (How: It is minimum path cover) but now I am unable to find the antichain elements themselves?

Answer 1

To compute the antichain you can:

1. Compute the maximum bipartite matching (e.g. with a maximum flow algorithm) on a new bipartite graph D which has an edge from LHS a to RHS b if and only if a divides b.
2. Use the matching to compute a minimal vertex cover (e.g. with the algorithm described in the proof of Konig's theorem
3. The antichain is given by all vertices not in the vertex cover

There cannot be an edge between two such elements as otherwise we would have discovered an edge that is not covered by a vertex cover resulting in a contradiction.

The algorithm to find the min vertex cover is (from the link above):

1. Let S0 consist of all vertices unmatched by M.
2. For integer j ≥ 0, let S(2j+1) be the set of all vertices v such that v is adjacent via some edge in E \ M to a vertex in S(2j) and v has not been included in any previously-defined set Sk, where k < 2j+1. If there is no such vertex, but there remain vertices not included in any previously-defined set Sk, arbitrarily choose one of these and let S(2j+1) consist of that single vertex.
3. For integer j ≥ 1, let S(2j) be the set of all vertices u such that u is adjacent via some edge in M to a vertex in S(2j−1). Note that for each v in S(2j−1) there is a vertex u to which it is matched since otherwise v would have been in S0. Therefore M sets up a one-to-one correspondence between the vertices of S(2j−1) and the vertices of S(2j).

The union of the odd indexed subsets is the vertex cover.