Hardness of subgraph and supergraph problems in c-tournaments

Problems like the directed feedback vertex set problem have much better algorithms in tournaments when compared to general graphs. This motivates us to study a natural generalization of tournaments, named c-tournaments, and see if the structural properties of these graphs are helpful in obtaining similar algorithms. c-tournaments are simple digraphs which have directed paths of length at most c≥1 between all pairs of vertices. We study the complexity of feedback vertex set and r-dominating set in c-tournaments. We also present hardness results on some graph editing problems involving c-tournaments. © 2011 Elsevier B.V. All rights reserved.