On the Parameterized Complexity of Computing Graph Bisections

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="http://link.springer.com/chapter/10.1007/978-3-642-45043-3_8" target="_blank" >http://link.springer.com/chapter/10.1007/978-3-642-45043-3_8</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

On the Parameterized Complexity of Computing Graph Bisections

Popis výsledku v původním jazyce

The Bisection problem asks for a partition of the vertices of a graph into two equally sized sets, while minimizing the cut size. This is the number of edges connecting the two vertex sets. Bisection has been thoroughly studied in the past. However, onlyfew results have been published that consider the parameterized complexity of this problem. We show that Bisection is FPT w.r.t. the minimum cut size if there is an optimum bisection that cuts into a given constant number of connected components. Our algorithm applies to the more general Balanced Biseparator problem where vertices need to be removed instead of edges. We prove that this problem is W[1]-hard w.r.t. the minimum cut size and the number of cut out components. For Bisection we further show that no polynomial-size kernels exist for the cut size parameter. In fact, we show this for all parameters that are polynomial in the input size and that do not increase when taking disjoint unions of graphs. We prove fixed-parameter tract

Název v anglickém jazyce

On the Parameterized Complexity of Computing Graph Bisections

Popis výsledku anglicky

The Bisection problem asks for a partition of the vertices of a graph into two equally sized sets, while minimizing the cut size. This is the number of edges connecting the two vertex sets. Bisection has been thoroughly studied in the past. However, onlyfew results have been published that consider the parameterized complexity of this problem. We show that Bisection is FPT w.r.t. the minimum cut size if there is an optimum bisection that cuts into a given constant number of connected components. Our algorithm applies to the more general Balanced Biseparator problem where vertices need to be removed instead of edges. We prove that this problem is W[1]-hard w.r.t. the minimum cut size and the number of cut out components. For Bisection we further show that no polynomial-size kernels exist for the cut size parameter. In fact, we show this for all parameters that are polynomial in the input size and that do not increase when taking disjoint unions of graphs. We prove fixed-parameter tract

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-45042-6

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

76-87

Název nakladatele

Springer Science+Business Media

Místo vydání

Berlin

Místo konání akce

Lubeck

Datum konání akce

19. 6. 2013

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

WRD - Celosvětová akce

Kód UT WoS článku

—