1
$\begingroup$

Suppose that we are given three sequences $a1,a2$ and $a3$ each describing a total ordering on $N$ 'entities'. For example,

$$\langle a1\rangle=1<9<8<2<3<\cdots<N $$

means that entity #1 is worst and entity #N is the best according to $a1$.

I need to come up with a new total ordering, let us call it $\langle x \rangle$ that best approximates all given orderings.

One way I was thinking of doing this task with $N=4$:

$$<a1> = 1<3<4<2 $$ $$<a2> = 1<2<4<3 $$ $$<a3> = 4<2<3<1 $$

Look at each pair $x,y \in \lbrace 1,2,3,4 \rbrace, x\neq y $. For example let us look at the tuple $(1,4)$. Clearly the first two sequences claim $1<4$ while the third claims $4<1$. Pick out the majority winner. Here, $1<4$ wins.

Do this for each possible tuple. We then have $\binom{N}{2}$ such tuples. List them , for eg: $1<4$, $2<3$, ...

Use these now to combine them into a total ordering $<x>$.

ISSUE: This problem can be converted to the Hamilton Path problem. Let each number be a vertex. Put a directed edge between $x$ and $y$ iff $x<y$. Now find the directed path that convers each vertex exactly once, this is my $<x>$.

Is my argument that this problem is NP complete correct? (Since Ham path is NP complete). If so, in what other ways can I do this task?

$\endgroup$
  • $\begingroup$ What's your metric for how closely a new ordering approximates all the given orderings? $\endgroup$ – Brian Tung Jul 23 '18 at 22:04
  • $\begingroup$ I don't have one specifically, essentially I want the relative orders to be as consistent as possible .hence the idea I mentioned $\endgroup$ – Vinayak Suresh Jul 24 '18 at 0:32
2
$\begingroup$

Is my argument that this problem is NP complete correct? (Since Ham path is NP complete).

The argument is both incorrect and wrong.

It's incorrect because reduction arguments have to go the other way: by solving your problem you can solve any instance of a known NP-complete problem (and the reduction is polynomial).

It's wrong because the graph defined in your problem is a tournament (Wikipedia, MathWorld) and a Hamiltonian path in a tournament on $n$ vertices can be found in $O(n \lg n)$ time. See e.g. Bang-Jensen and Gutin, On the complexity of hamiltonian path and cycle problems in certain classes of digraphs, for a survey.


Although it's not directly what you ask, I should note a problem with the proposed algorithm:

Now find the directed path that convers each vertex exactly once, this is my $<x>$.

(my emphasis). There isn't necessarily a unique Hamiltonian path. Consider the minimal example where the three input orders are $$1 < 2 < 3 \\ 2 < 3 < 1 \\ 3 < 1 < 2$$ The graph is a cycle $1 \to 2 \to 3 \to 1$, so there are three Hamiltonian paths. Obviously in this case the three are equally good / bad approximations, but maybe a more complicated example which embeds them would have Hamiltonian paths which vary in how many of the original pairwise comparisons they contradict.

$\endgroup$
  • $\begingroup$ Thank you for the answer. I see the problem you mentioned. Do you have any other ideas for a different or similar algorithm? $\endgroup$ – Vinayak Suresh Jul 25 '18 at 14:03
  • $\begingroup$ @VinayakSuresh, you could weight the edges by the number of total orderings they contradict (so all the weights will be 0 or 1) and then treat it as an instance of the travelling salesman problem. That seems like a reasonable definition of the "best" total order(s), but I'm not sure whether it's known to be in P. You could try to adapt an algorithm for Hamiltonian path on tournaments to TSP on weighted tournaments; it might have enough structure for dynamic programming to be effective. $\endgroup$ – Peter Taylor Jul 25 '18 at 14:39
  • $\begingroup$ I do not quite understand what you mean. So we have these three sequences and they each result in a tournament graph that is transitive and contains no cycles. However, when we take the majority vote and construct the new tournament graph, cycles can be introduced. So are you saying to completely do away with 'taking majority vote'. Which graph should I add these wieghts on? $\endgroup$ – Vinayak Suresh Jul 25 '18 at 15:43
  • $\begingroup$ When you take the majority vote, it's either unanimous or it's 2 vs 1. If it's unanimous then give the edge weight 0; otherwise give it weight 1. $\endgroup$ – Peter Taylor Jul 25 '18 at 15:51
  • $\begingroup$ aah, good idea! I was wondering if there was a way to find all possible hamiltonian paths in the graph efficiently? And then I could just add the weights on the paths to select the best one. I haven't been able to find an algorithm to find ALL hamiltonian paths. $\endgroup$ – Vinayak Suresh Jul 25 '18 at 15:54

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.