Parameterized Complexity of Connected Even/Odd Subgraph Problems

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.