1
$\begingroup$

Given $n$ variables : $a_1,a_2...,a_n$ and $m$ inequalities of the form $a_i<a_j$, we want to know if there's a positioning that satisfies all the inequalities.

a. We want to modelize the problem to a directed graph $G=(V,E)$. $V=?,E=?$

$V=\{a_i|i\in[n]\}$ $E=\{a_ia_j|a_i<a_j\}$

b. Complete the sentence: There exists a valid positioning iff...

$G=(V,E)$ doesn't contain directed cicles and parallel edges (i.e. to prevent $a_1<a_2$ $a_2<a_3\space$ $a_3<a_1\space$ and $a_1<a_2\space$ $a_2<a_1$)

c. How do we determine if there exists a valid positioning? What would be the complexity of such action?

I guess check for directed cycles (which i don't know how) and parallel edges?

d. If there's a valid positioning, how do we find it?

By giving the vertex with maximum $d_{out}$ the lowest number and so on?

I'd appreciate help with c and d.

$\endgroup$
  • $\begingroup$ The question seems to already contain a complete answer. $\endgroup$ – Yuval Filmus Nov 4 '17 at 15:26
  • $\begingroup$ In the last section, you're supposed to use a topological ordering. $\endgroup$ – Yuval Filmus Nov 4 '17 at 15:26
  • 1
    $\begingroup$ @YuvalFilmus I'm not sure it's a complete answer. I'm happy to class this one as the asker showing what they've tried. $\endgroup$ – David Richerby Nov 4 '17 at 16:21
1
$\begingroup$

You’re on the right track with your response to $c$. There’s a bunch of algorithms that solve $c$ and $d$ simultaneously. If you’re familiar with depth-first search, you can use that to solve the problem.

Another approach is what’s called “topological sort.” The key idea here is that if a directed graph has no cycles, then you can put the vertices in a line such that there are only edges that go from start vertex to an end vertex such that the end vertex is to the right of the start vertex. This is actually really easy to write an algorithm to do, give it some thought and see if you can’t come up with a clever trick.

The best case time for solving this problem is $O(|V|+|E|)$, and off the top of my head I can think of four algorithms that achieve that timing.

$\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.