1
$\begingroup$

Suppose we are given a finite binary relation $R$ and we are asked to find a largest subrelation of $P \subseteq R$ satisfying the properties of a (non-strict) partial order.

A brute force approach would be to generate all elements of the powerset of $R$, check for the properties of a partial order, and keep one of the largest you come across. But this approach would require exponential time in the cardinality of $R$.

Is there a more efficient algorithm than this brute-force approach to finding a largest subrelation satisfying a non-strict partial order?

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ There can be several, so you can't really say "the" (and there can also be none). Dealing with reflexivity is trivial. To deal with antisymmetry, you may be able to look at cliques or some sort of connected components. However, for transitivity, if $x\not Rz$, then either $x\not Ry$ or $y\not Rz$, and I'd expect these choice to be non-local enough to make your problem NP-hard. $\endgroup$
    – xavierm02
    Aug 26, 2022 at 11:39
  • $\begingroup$ Is finding such a largest subrelation different from finding a largest connected component in a bipartite graph? $\endgroup$
    – J..y B..y
    Aug 26, 2022 at 13:29
  • $\begingroup$ @J..yB..y I don't know of an equivalence relation between these problems. $\endgroup$
    – Galen
    Aug 26, 2022 at 13:58
  • $\begingroup$ @xavierm02 Good catch; uniqueness is not guaranteed. Is the empty set a sort of trivial partial order? $\endgroup$
    – Galen
    Aug 26, 2022 at 13:59
  • 3
    $\begingroup$ This appears to be some version of the feedback arc set problem. I think at least feedback arc set on tournaments is a special case of it, so no polynomial time algorithm should exist. $\endgroup$
    – Laakeri
    Aug 27, 2022 at 6:26

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.