Is there a better-than-brute-force algorithm for finding a largest subrelation that is a non-strict partial order?

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?

• 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. Aug 26, 2022 at 11:39
• Is finding such a largest subrelation different from finding a largest connected component in a bipartite graph? Aug 26, 2022 at 13:29
• @J..yB..y I don't know of an equivalence relation between these problems. Aug 26, 2022 at 13:58
• @xavierm02 Good catch; uniqueness is not guaranteed. Is the empty set a sort of trivial partial order? Aug 26, 2022 at 13:59
• 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. Aug 27, 2022 at 6:26