Perfect forests in graphs and their extensions

Let (Formula presented.) be a graph on (Formula presented.) vertices. For (Formula presented.), a spanning forest (Formula presented.) of (Formula presented.) is called an (Formula presented.) -perfect forest if every tree in (Formula presented.) is an induced subgraph of (Formula presented.) and exactly (Formula presented.) vertices of (Formula presented.) have even degree (including zero). An (Formula presented.) -perfect forest of (Formula presented.) is proper if it has no vertices of degree zero. Scott showed that every connected graph with an even number of vertices contains a (proper) 0-perfect forest. We prove that one can find a 0-perfect forest with a minimum number of edges in polynomial time, but it is NP-hard to obtain a 0-perfect forest with a maximum number of edges. Moreover, we show that to decide whether (Formula presented.) has a 0-perfect forest with at least (Formula presented.) edges, where (Formula presented.) is the parameter, is W[1]-hard. We also prove that for a prescribed edge (Formula presented.) of (Formula presented.) it is NP-hard to obtain a 0-perfect forest containing (Formula presented.) but one can decide if there exists a 0-perfect forest not containing (Formula presented.) in polynomial time. It is easy to see that every connected graph with an odd number of vertices has a 1-perfect forest. It is not the case for proper 1-perfect forests. We give a characterization of when a connected graph has a proper 1-perfect forest.