Fomin, Fedor V. ;
Golovach, Petr A.
Parameterized Complexity of Connected Even/Odd Subgraph Problems
Abstract
Cai and Yang initiated the systematic parameterized complexity study of the following set of problems around Eulerian graphs. For a given graph G and integer k, the task is to decide if G contains a (connected) subgraph with k vertices (edges) with all vertices of even (odd) degrees. They succeed to establish the parameterized complexity of all cases except two, when we ask about
 a connected kedge subgraph with all vertices of odd degrees, the problem known as kEdge Connected Odd Subgraph; and
 a connected k vertex induced subgraph with all vertices of even degrees, the problem known as kVertex Eulerian Subgraph.
We resolve both open problems and thus complete the characterization of even/odd subgraph problems from parameterized complexity perspective. We show that kEdge Connected Odd Subgraph is FPT and that kVertex Eulerian Subgraph is W[1]hard.
Our FPT algorithm is based on a novel combinatorial result on the treewidth of minimal connected odd graphs with even amount of edges.
BibTeX  Entry
@InProceedings{fomin_et_al:LIPIcs:2012:3398,
author = {Fedor V. Fomin and Petr A. Golovach},
title = {{Parameterized Complexity of Connected Even/Odd Subgraph Problems}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {432440},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897354},
ISSN = {18688969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3398},
URN = {urn:nbn:de:0030drops33986},
doi = {10.4230/LIPIcs.STACS.2012.432},
annote = {Keywords: Parameterized complexity, Euler graph, even graph, odd graph, treewidth}
}
2012
Keywords: 

Parameterized complexity, Euler graph, even graph, odd graph, treewidth 
Seminar: 

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Issue date: 

2012 
Date of publication: 

2012 