We study the problem of computing a Maximum Transitive Subgraph (MTS) of a given directed graph. This problem is known to be NP-hard. We give an algorithm that runs in time O(4k2n2) to output an MTS for a graph with treewidth k.

Additional Metadata
Conference Cologne-Twente Workshop on Graphs and Combinatorial Optimization
Citation
Chakraborty, S, & Jha, N. (2020). Exact algorithms for maximum transitive subgraph problem. In Proceedings of 15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2017 (pp. 47–51).