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 k-edge subgraph with all vertices of odd degrees, the problem known as k-Edge Connected Odd Subgraph; and 

- a connected k- vertex induced subgraph with all vertices of even degrees, the problem  known as  k-Vertex Eulerian Subgraph.

We resolve both open problems and thus complete the characterization  of even/odd subgraph problems from parameterized complexity perspective. We show that k-Edge Connected Odd Subgraph is FPT and that k-Vertex 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.