2026-07-20T14:51:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3398 2024-03-06T10:34:12Z ddc:004 open_access

Parameterized Complexity of Connected Even/Odd Subgraph Problems Fomin, Fedor V. Golovach, Petr A. Parameterized complexity Euler graph even graph odd graph treewidth 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor V. Fomin and Petr A. Golovach 2012 Is Part Of LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2012.432 urn:nbn:de:0030-drops-33986 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.432 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode