Maximal and maximum transitive relation contained in a given binary relation

DOI10.1007/978-3-319-21398-9_46MaRDI QIDQ3196418zbMATH OpenOpenAlexFDO

Authors Sourav Chakraborty, Shamik Ghosh, Nitesh Jha, Sasanka Roy

Publication date 29 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.08953

Mathematics Subject Classification ID

Other classical set theory (including functions, relations, and set algebra) (03E20) Directed graphs (digraphs), tournaments (05C20) Combinatorics in computer science (68R05) Nonnumerical algorithms (68W05) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Abstract: We study the problem of finding a extit{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 extit{maximum} transitive relation contained in a binary relation. This is the problem of computing a maximum transitive subgraph in a given digraph. For the class of directed graphs with the underlying graph being triangle-free, we present a $0.874$-approximation algorithm. This is achieved via a simple connection to the problem of maximum directed cut. Further, we give an upper bound for the size of any maximum transitive relation to be $m/4+c{m}^{4/5}$, where $c>0$ and $m$ is the number of edges in the digraph.

Recommendations

• On transitive subrelations of binary relations
• A method for obtaining transitive approximations of a binary relation
• On the transitive closure of reciprocal \([0, 1]\)-valued relations
• Maximal elements of not necessarily acyclic binary relations
• Structure of transitive valued binary relations

Cites work

• A Theorem on Boolean Matrices
• A transitive closure algorithm
• An Algorithm for Finding a Minimum Equivalent Graph of a Digraph
• scientific article; zbMATH DE number 554768 (Why is no real title available?)
• scientific article; zbMATH DE number 2086914 (Why is no real title available?)
• scientific article; zbMATH DE number 813252 (Why is no real title available?)
• Matrix multiplication via arithmetic progressions
• Multiplying matrices faster than coppersmith-winograd
• Node-and edge-deletion NP-complete problems
• The Transitive Reduction of a Directed Graph

Cited in

(2)

• On transitive subrelations of binary relations
• Maximal elements for nontransitive binary relations

This page was built for publication: Maximal and maximum transitive relation contained in a given binary relation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196418)