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

Research output: Contribution to journalArticlepeer-review


Colleges, School and Institutes

External organisations

  • University of Bergen
  • Weizmann Institute of Science
  • Russian Academy of Science (LPI RAS)


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.


Original languageEnglish
Pages (from-to)11-22
JournalInformation and Computation
Early online date1 Dec 2015
Publication statusPublished - 1 Apr 2016


  • Anchored k-core, Directed graphs, Parameterized complexity