Parameterized complexity of DAG partitioning

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationAlgorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings
Pages49-60
Number of pages12
DOIs
Publication statusPublished - 9 Sep 2013
Externally publishedYes
Event8th International Conference on Algorithms and Complexity, CIAC 2013 - Barcelona, Spain
Duration: 22 May 201324 May 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7878 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference8th International Conference on Algorithms and Complexity, CIAC 2013
CountrySpain
CityBarcelona
Period22.05.201324.05.2013

Fingerprint Dive into the research topics of 'Parameterized complexity of DAG partitioning'. Together they form a unique fingerprint.

Cite this