Parameterized complexity of connected even/odd subgraph problems

作者：

Highlights：

• The k-Edge Connected Odd Subgraph problem is FPT when parameterized by k.

• The k-Vertex Eulerian Subgraph problem is W[1]-hard when parameterized by k.

• The treewidth of minimal connected odd graphs with even number of edges is at most three.

摘要

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

论文关键词：Parameterized complexity,Euler graph,Even graph,Odd graph,Treewidth

论文评审过程：Received 2 August 2012, Revised 13 June 2013, Accepted 12 July 2013, Available online 22 July 2013.

论文官网地址：https://doi.org/10.1016/j.jcss.2013.07.002