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. For undirected graphs, this problem was introduced by Bhawalkar, Kleinberg, Lewi, Roughgarden, and Sharma [ICALP 2012]. We undertake a systematic analysis of the computational complexity of Directed Anchored k-CoRE and show that: The decision version of the problem is NP-complete for every k > 1 even if the input graph is restricted to be a planar directed acyclic graph of maximum degree at most k + 2. The problem is fixed parameter tractable (FPT) parameterized by the Size of the core p for k = 1, and W[l]-hard for k > 2. When the maximum degree of the graph is at most Δ, the problem is FPT parameterized by p + Δ if k > Δ/2.
展开▼
