Let $G=(V,E)$ be a directed acyclic graph. Two vertices is transitive if there is a directed path between them. A Path Cover for a Set of Transitive Pairs (PCSTP) is a set of directed paths such that every pair of transitive vertices belongs to at least one path. The minimum PCSTP problem consists of finding a PCSTP for G having the least number of paths. Is this problem NP-hard?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.