<p>Suppose we are given a finite <a href="https://en.wikipedia.org/wiki/Binary_relation" rel="nofollow noreferrer">binary relation</a> <span class="math-container">$R$</span> and we are asked to find a largest subrelation of <span class="math-container">$P \subseteq R$</span> satisfying the properties of a (non-strict) <a href="https://en.wikipedia.org/wiki/Partially_ordered_set" rel="nofollow noreferrer">partial order</a>.</p>
<p>A <a href="https://en.wikipedia.org/wiki/Brute-force_search" rel="nofollow noreferrer">brute force</a> approach would be to generate all elements of the powerset of <span class="math-container">$R$</span>, check for the properties of a partial order, and keep one of the largest you come across. But this approach would require <a href="https://en.wikipedia.org/wiki/Time_complexity#Exponential_time" rel="nofollow noreferrer">exponential time</a> in the <a href="https://en.wikipedia.org/wiki/Cardinality" rel="nofollow noreferrer">cardinality</a> of <span class="math-container">$R$</span>.</p>
<p>Is there a more efficient algorithm than this brute-force approach to finding a largest subrelation satisfying a non-strict partial order?</p>

CC BY-SA 4.0
2022-08-26T11:39:59.060Z
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.
xavierm02
CC BY-SA 4.0
2022-08-26T13:29:14.710Z
Is finding such a largest subrelation different from finding a largest connected component in a bipartite graph?
J.y B.y
CC BY-SA 4.0
2022-08-26T13:58:40.670Z
@J..yB..y I don't know of an equivalence relation between these problems.
Galen
CC BY-SA 4.0
2022-08-26T13:59:21.193Z
@xavierm02 Good catch; uniqueness is not guaranteed. Is the empty set a sort of trivial partial order?
Galen
CC BY-SA 4.0
2022-08-27T06:26:07.863Z
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.
Laakeri
CC BY-SA 4.0
2022-09-13T15:10:26.380Z
Ah, I get the gist of how it might be related to the [minimum feedback arc set problem](https://en.wikipedia.org/wiki/Feedback_arc_set).
Galen
<ds.algorithms>
Is there a better-than-brute-force algorithm for finding a largest subrelation that is a non-strict partial order?
Galen
# Is there a better-than-brute-force algorithm for finding a largest subrelation that is a non-strict partial order?

(Asked by: username_0 on 2022-08-25)

Suppose we are given a finite [binary relation](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Partially_ordered_set).

A [brute force](https://en.wikipedia.org/wiki/Brute-force_search) 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](https://en.wikipedia.org/wiki/Time_complexity#Exponential_time) in the [cardinality](https://en.wikipedia.org/wiki/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?

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: 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.  
> **username_2**: Is finding such a largest subrelation different from finding a largest connected component in a bipartite graph?  
> **username_0**: @J..yB..y I don't know of an equivalence relation between these problems.  
> **username_0**: @xavierm02 Good catch; uniqueness is not guaranteed. Is the empty set a sort of trivial partial order?  
> **username_3**: 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.  
> **username_0**: Ah, I get the gist of how it might be related to the [minimum feedback arc set problem](https://en.wikipedia.org/wiki/Feedback_arc_set).  

---

## 0 answers

