Parameterized complexity of the anchored k-core problem for directed graphs

We consider the Directed Anchored k -Core problem, where the task is for a given directed graph G and integers b, k and p, to find an induced subgraph H with at least p vertices (the core) such that all but at most b vertices (the anchors) of H have in-degree at least k. We undertake a systematic analysis of the computational complexity of the Directed Anchored k -Core problem.

Authors

• Rajesh Chitnis
• Fedor V. Fomin
• Petr A. Golovach

Keywords

• Parameterized complexity
• Directed graphs
• Anchored k-core