Parameterized Complexity of DAG Partitioning

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F13%3A00209347" target="_blank" >RIV/68407700:21240/13:00209347 - isvavai.cz</a>

Výsledek na webu

<a href="http://link.springer.com/chapter/10.1007%2F978-3-642-38233-8_5" target="_blank" >http://link.springer.com/chapter/10.1007%2F978-3-642-38233-8_5</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-642-38233-8_5" target="_blank" >10.1007/978-3-642-38233-8_5</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Parameterized Complexity of DAG Partitioning

Popis výsledku v původním jazyce

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(2^k cdot n^2)$ 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 $2^{o(k)} cdot n^{O(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 $2^{O(w^2)} cdot n$ time, improving a known algorithm for the parameter pathwidth.

Název v anglickém jazyce

Parameterized Complexity of DAG Partitioning

Popis výsledku anglicky

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(2^k cdot n^2)$ 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 $2^{o(k)} cdot n^{O(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 $2^{O(w^2)} cdot n$ time, improving a known algorithm for the parameter pathwidth.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2013

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ISBN

978-3-642-38232-1

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

49-60

Název nakladatele

Springer Science+Business Media

Místo vydání

Berlin

Místo konání akce

Barcelona

Datum konání akce

22. 5. 2013

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—