Parameterized complexity of connected even/odd subgraph problems

•The k-Edge Connected Odd Subgraph problem is FPT when parameterized by k.•The k  -Vertex Eulerian Subgraph problem is W[1]W[1]-hard when parameterized by k.•The treewidth of minimal connected odd graphs with even number of edges is at most three.

In 2011, Cai an 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 show that k-Edge Connected Odd Subgraph is FPT and k-Vertex Eulerian Subgraph is W[1]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.