6

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?

Saeid
  • 4,147
  • 7
  • 27
  • 43
user3674243
  • 61
  • 4
  • You forgot to (1) include the problem statement in the question to make it self-contained (2) Link to the source (the title is not the right place, the URL is not clickable) (3) present your own thoughts and solution ideas – Niklas B. May 25 '14 at 18:24
  • Well you have solved (2) so far, (1) and (3) to go. I don't know Dilworth's theorem by the way, so please describe shortly what it says and how it is applicable to the problem. Also how you apply bipartite matching to find a minimum chain. I would expect your question to at least mention that divisibility is a partial order relation, with a brief overview of what that means, how Dilworth's theorem is applicable, what your algorithm can do so far and what exactly you still need to know. Make it easier for us to help you. – Niklas B. May 25 '14 at 18:27
  • Have described it the best I can. Please tell if more information need to be put. Thanks. – user3674243 May 25 '14 at 18:40
  • The solution is described in detail [over at CS.stackexchange.com](http://cs.stackexchange.com/questions/10274/how-to-find-the-maximum-independent-set-of-a-directed-graph) – Niklas B. May 25 '14 at 19:13

1 Answers1

5

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.

Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75
  • Its not a question of finding the min. vertex cover. I need to find the elements of the antichain set of the given poset i.e. graph. How is vertex cover needed here. We need min. path cover. Didn't get you. Please help. – user3674243 May 25 '14 at 19:04
  • @Niklas I may delete this answer as it doesn't seem to be helping, but I think the point is that divisibility forms a partially ordered set, and so you can use bipartite matching to construct a minimum path cover. Once you have that, you then construct the min vertex cover on the bipartite graph and the remaining vertices are the antichain. Note that the bipartite graph is from the set of numbers to the same set of numbers, so is a different graph to the original divisibility graph. – Peter de Rivaz May 25 '14 at 19:15
  • @PeterdeRivaz I realized that now after reading the Wikipedia page on Dilworth's theorem. If you make it clearer what graph you are actually referring too, I think this makes for a good and valid answer – Niklas B. May 25 '14 at 19:16
  • @PeterdeRivaz I m unable to get u here-"Once you have that, you then construct the min vertex cover on the bipartite graph and the remaining vertices are the antichain". what you used minimum path cover for when you just used min. vertex cover to get the antichain. – user3674243 May 25 '14 at 19:23
  • As the number of elements is 200. Can't I backtrack and get the antichain elements from the chains derived from matching. – user3674243 May 25 '14 at 19:29
  • @user3674243 I haven't used the minimum path cover directly. Instead I have used the maximum matching to construct the min vertex cover. (If you actually want the chains, then you can use the same matching to construct the minimum path cover.) To address the second question, if you construct the min path cover and backtrack you will discover a chain - not an anti-chain. – Peter de Rivaz May 25 '14 at 19:32