3
$\begingroup$

I am trying to find a reduction for a problem that seems NP-hard:

Let me start from a toy example. Consider 3 elements, $a$, $b$, and $c$. You want to choose two pairs out of the three pairs and compare the two elements of each pair. There is a true underlying ordering of the elements, which we don't know. Our objective is to pick the comparisons that will maximize, in expectation, the number of elements that will "lose" at least one comparison.

For example, lets assume that we choose $(a,b)$ and $(b,c)$. There are four possibilities:

(1) $a>b$ and $c>b$ with probability $\frac{2}{6}$ ($2$ out of the $3!$ possible permutations respect $a>b$ and $c>b$)

(2) $a>b$ and $c<b$ with probability $\frac{1}{6}$

(3) $a<b$ and $c>b$ with probability $\frac{1}{6}$

(4) $a<b$ and $c<b$ with probability $\frac{2}{6}$

In the case of (1), only $b$ loses at least one comparison, in (2), $b$ and $c$ lose at least one comparison, and so on. The expected number of elements losing at least one comparison is:

$\frac{2}{6} * 1 + \frac{1}{6} * 2 + \frac{1}{6} * 2 + \frac{2}{6} * 2 = 1\frac{2}{3}$

Note that the outcome of each comparison is based on the true ordering, which we don't know..

In this toy example, any two pairs give the same expected number of "losers". In its general form, the problem states that we have $n$ elements, and we can ask for $b$ comparisons (the problem becomes interesting when $b>\frac{n}{2}$). Making it even more general, we can have the outcome of previous comparisons as input and try to maximize the "losers" out of those elements that still haven't lost any comparison. I am interested in the second, more general, case but I feel that even without the previous comparisons' outcome, the problem is still NP-hard.

The most helpful result I have found until now, is that counting linear extensions of a partially ordered set is #P-complete [1].

I would greatly appreciate any ideas about a reduction, or any obvious reduction that I can not see.

Thank you!

[1] Brightwell, Graham R.; Winkler, Peter (1991), "Counting linear extensions", Order 8 (3): 225–242, paper

|cite|improve this question|||||
$\endgroup$
  • 1
    $\begingroup$ First, this can't possibly be NP-hard. There's only a polynomial number of inputs — $n \choose 2$ — for each $n$, and sparse problems can't be NP-hard. If you start with a known partial order, and have $k$ more comparisons, maximizing the number of distinct losers might be NP-hard. $\endgroup$ – Peter Shor Dec 7 '13 at 13:53
6
$\begingroup$

Look at the graph that is formed by the comparisons. Each element corresponds to a vertex. If an element is a vertex of degree $d$, then the probability that it will be the lowest in at least one of these comparisons is the probability that it is not larger than all of its neighbors. This probability is $d/(d+1)$.

Now, expectation is linear. This means that the expected number of losers is $$ \sum_{v \in G} \frac{d_v}{d_v+1}.$$ To illustrate, with your example there is one vertex of degree 2 and two of degree 1, so the expected number of losers is $\frac{2}{3} + \frac{1}{2} + \frac{1}{2} = \frac{5}{3}.\ $

It is easy to prove that this quantity is maximized when the degrees of the vertices are all as close to equal as possible, so the vertex degrees all are either $d$ or $d+1$ for some $d$.

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ Thank you so much! Indeed, in the simple case the probability of a node winning all of the $d$ comparisons, it is involved in, is $\frac{1}{d+1}$. So the problem is trivial. Thank you for showing it to me. When you start with a known partial order, some of the $n!$ permutations are not possible. The straightforward way would be to count the linear extensions of the partial order to find the probability of a node winning all of the $d$ comparisons. Nevertheless, counting the linear extensions is #P-complete. Do you have any ideas about the hardness of the problem in this case? $\endgroup$ – bill Dec 7 '13 at 20:44
  • $\begingroup$ My guess is that it's NP-hard, but I don't know how to show it. $\endgroup$ – Peter Shor Dec 7 '13 at 21:00
  • $\begingroup$ Have you seen any problem similar to this one, where a reduction from it could be possible? Thanks again! $\endgroup$ – bill Dec 7 '13 at 21:10

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.