The ODD EVEN DELTA problem is #P-hard

2012/12/31 by Giorgio Camerani, Camerani, Giorgio
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #DNA and Biological Computing #F.1.3 #FOS: Computer and information sciences #Limits and Structures in Graph Theory #cs.CC

paper · pdf · doi:10.48550/arxiv.1212.6935

3 pages

arxiv created 2012/12/31 · openalex publication_date 2012/12/31 · arxiv updated 2013/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let G=(V,E) be a graph. Let k < |V| be an integer. Let O_k be the number of edge induced subgraphs of G having k vertices and an odd number of edges. Let E_k be the number of edge induced subgraphs of G having k vertices and an even number of edges. Let D_k = O_k - E_k. The ODD EVEN DELTA problem consists in computing D_k, given G and k. We show that such problem is #P-hard, even on 3-regular bipartite planar graphs.

Related

• The parameterised complexity of counting even and odd induced subgraphs
• On the complexity of finding a spanning even tree in a graph
• On the complexity of finding large odd induced subgraphs and odd colorings
• Large odd induced subgraphs via odd cuts
• Strengthening Hardness Results to 3-Connected Planar Graphs