We study the problem of finding a maximal transitive relation contained in a given binary relation. Given a binary relation of size m defined on a set of size n, we present a polynomial time algorithm that finds a maximal transitive sub-relation in time O(n~2 + nm). We also study the problem of finding a maximum transitive relation contained in a binary relation. For the class of triangle-free relations (directed graphs), we present a 0.874-approximation via the problem of maximum directed cut.
展开▼
