2026-07-29T10:45:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4363 2024-03-06T10:34:57Z ddc:004 open_access

Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs Chitnis, Rajesh Fomin, Fedor V. Golovach, Petr A. Parameterized complexity directed graphs anchored $k$-core 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[1]-hard for k>=2. - When the maximum degree of the graph is at most Delta, the problem is FPT parameterized by p+Delta if k>=Delta/2. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rajesh Chitnis and Fedor V. Fomin and Petr A. Golovach 2013 Is Part Of LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2013.79 urn:nbn:de:0030-drops-43636 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.79 eng https://creativecommons.org/licenses/by/3.0/legalcode