Let $G = ( V, E )$ be a graph. Let $k \leq |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 $\Delta_k = O_k - E_k$. The ODD EVEN DELTA problem consists in computing $\Delta_k$, given $G$ and $k$.Questions Is it possible to compute $\Delta_k$ in polynomial time? Which is the best known algorithm to compute it?What if $G$ is 3-regular?What if $G$ is 3-regular bipartite?What if $G$ is 3-regular bipartite planar?
The ODD EVEN DELTA problem
ds.algorithms;graph theory;graph algorithms;counting complexity
The ODD EVEN DELTA problem is #P-hard, even on 3-regular bipartite planar graphs.Let $\mathcal{C}$ be the set of vertex covers of a general graph $G$. Then, assuming $G$ has no isolated vertices, the following equation holds (refer to the above article for the proof):$$|\mathcal{C}| = 2^{|V|} - \sum_{k = 2}^{|V|} \Delta_k \cdot 2^{|V|-k}$$Counting vertex covers is #P-complete even on 3-regular bipartite planar graphs, and it can be done with a linear number of calls to an ODD EVEN DELTA oracle.