Affordable Access

Publisher Website

Hardness of subgraph and supergraph problems in [formula omitted]-tournaments

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
412
Issue
35
Identifiers
DOI: 10.1016/j.tcs.2011.04.046
Keywords
  • Parameterized Complexity
  • Feedback Vertex Set
  • Dominating Set
  • Graph Modification
  • Tournaments
Disciplines
  • Computer Science
  • Engineering

Abstract

Abstract 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.

There are no comments yet on this publication. Be the first to share your thoughts.