# Modeling an inequality problem to a graph

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.

• The question seems to already contain a complete answer. – Yuval Filmus Nov 4 '17 at 15:26
• In the last section, you're supposed to use a topological ordering. – Yuval Filmus Nov 4 '17 at 15:26
• @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. – David Richerby Nov 4 '17 at 16:21

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