Dynamic Programming Algorithms on Directed Cographs
Frank Gurski · Statistics Optimization & Information Computing · 2017
In this paper we consider directed cographs, which are defined by Bechet et al. by the disjoint union, series, and order composition, from an algorithmic point of view. Using their recursive structure we give dynamic programming algorithms to show that for every directed cograph the size of a largest edgeless subdigraph, the size of a largest subdigraph which is a tournament, the size of a largest semicomplete subdigraph, and the size of a largest complete subdigraph can be computed in linear time. Our main results show that the hamiltonian path, hamiltonian cycle, regular subdigraph, and directed cut problem are polynomial on directed cographs.