Parameterized complexity of DAG partitioning

René Van Bevern, Robert Bredereck, Morgan Chopin, Sepp Hartung, Falk Hüffner, André Nichterlein, Ondřej Suchý

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

3 Цитирования (Scopus)


The goal of tracking the origin of short, distinctive phrases (memes) that propagate through the web in reaction to current events has been formalized as DAG Partitioning: given a directed acyclic graph, delete edges of minimum weight such that each resulting connected component of the underlying undirected graph contains only one sink. Motivated by NP-hardness and hardness of approximation results, we consider the parameterized complexity of this problem. We show that it can be solved in O(2k·n2) time, where k is the number of edge deletions, proving fixed-parameter tractability for parameter k. We then show that unless the Exponential Time Hypothesis (ETH) fails, this cannot be improved to 2o(k)·nO(1); further, DAG Partitioning does not have a polynomial kernel unless NP ⊆ coNP/poly. Finally, given a tree decomposition of width w, we show how to solve DAG Partitioning in 2o(w2)·n time, improving a known algorithm for the parameter pathwidth.

Язык оригиналаанглийский
Название основной публикацииAlgorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings
Число страниц12
СостояниеОпубликовано - 9 сент. 2013
Опубликовано для внешнего пользованияДа
Событие8th International Conference on Algorithms and Complexity, CIAC 2013 - Barcelona, Испания
Продолжительность: 22 мая 201324 мая 2013

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том7878 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349


Конференция8th International Conference on Algorithms and Complexity, CIAC 2013


Подробные сведения о темах исследования «Parameterized complexity of DAG partitioning». Вместе они формируют уникальный семантический отпечаток (fingerprint).