The notion of fixed parameter tractability involves relaxed polynomial-time complexity, which admits algorithms whose runtimes are exponential, but only in terms of some parameter that is expected to be small. More formally, a problem with input size n and a parameter k is said to be fixed-parameter tractable (FPT) if it can be solved in time f(k) · (n)^O(1) for some function f. A problem is in W[1] if and only if it is decidable by a nondeterministic FPT algorithm that does its nondeterministic steps, which are bounded by the parameter k, during the final steps of the computation. It is assumed that FPT ≠ W[1].

A graph is Eulerian if it is connected and has no vertex of odd degree. An even graph (or odd graph) is a graph with each vertex of an even (or odd) degree.

Given a graph G and a non-negative integer k, consider this problem: Does G contain a (connected) subgraph with k vertices (edges) with all vertices of even (odd) degrees?

In 2011, Cai and Yang [1] established the parameterized complexity of all cases except when the subgraph is a k-edge connected odd graph or a connected k-vertex induced even graph. In this paper, the authors settle these two cases. They show that the first case is FPT and the second is W[1]-hard.

I recommend this paper for graduate students and researchers interested in graph theory and complexity theory.