Parameterized complexity of the induced subgraph problem in directed graphs |
| |
Authors: | Venkatesh Raman |
| |
Affiliation: | The Institute of Mathematical Sciences, C.I.T Campus, Taramani, Chennai 600113, India |
| |
Abstract: | In this Letter, we consider the parameterized complexity of the following problem: Given a hereditary property P on digraphs, an input digraph D and a positive integer k, does D have an induced subdigraph on k vertices with property P? We completely characterize hereditary properties for which this induced subgraph problem is W[1]-complete for two classes of directed graphs: general directed graphs and oriented graphs. We also characterize those properties for which the induced subgraph problem is W[1]-complete for general directed graphs but fixed parameter tractable for oriented graphs. These results are among the very few parameterized complexity results on directed graphs. |
| |
Keywords: | Computational complexity Combinatorial problems Parameterized complexity Directed graphs Induced subgraph Hereditary properties |
本文献已被 ScienceDirect 等数据库收录! |
|