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

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

External organisations

  • University of Bergen
  • Weizmann Institute of Science, Rehovot, Israel.
  • Russian Academy of Sciences, St. Pertersburg, Russia

Abstract

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.

Details

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

Keywords

  • Anchored k-core, Directed graphs, Parameterized complexity