2026-07-22T08:27:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22714 2026-04-17T05:32:41Z ddc:004 open_access

Eulerian Orientations and Hadamard Codes: A Novel Connection via Counting Shao, Shuai Tang, Zhuxiao Eulerian orientations Hadamard codes Counting problems Tractable classes We discover a novel connection between two classical mathematical notions, Eulerian orientations and Hadamard codes by studying the counting problem of Eulerian orientations (#EO) with local constraint functions imposed on vertices. We present two special classes of constraint functions and a chain reaction algorithm, and show that the #EO problem defined by each class alone is polynomial-time solvable by the algorithm. These tractable classes of functions are defined inductively, and quite remarkably the base level of these classes is characterized perfectly by the well-known Hadamard code. Thus, we establish a novel connection between counting Eulerian orientations and coding theory. We also prove a #P-hardness result for the #EO problem when constraint functions from the two tractable classes appear together. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shuai Shao and Zhuxiao Tang 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.86 urn:nbn:de:0030-drops-227146 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.86 eng https://creativecommons.org/licenses/by/4.0/legalcode