# Is this a known problem, and is it #P-complete?

Let $$G=(V,E)$$ be an undirected graph. What I call a selection function of $$G$$ is a partial function $$f:V \to E$$ such that for every node $$v$$, if $$f(v)$$ is defined then it is one of the adjacent edges to $$v$$. In other words, every node can either select no edge or select an edge that is adjacent to it. The image of $$f$$ is simply $$\mathrm{Im}(f)= \{e \in E \mid \exists v \in V \text{ s.t. } e=f(v)\}$$ i.e., the set of edges that are selected.

I am interested in the following counting problem:

INPUT: a graph $$G$$

OUTPUT: $$|\{\mathrm{Im}(f) \mid f \text{ is a selection function of }G\}|$$

Question 1: does it have an established name? (It seems to be to be rather natural so maybe it has already been considered)

Question 2: is this problem #P-hard? (Ideally, I would like it to be hard on bipartite graphs)

Note that this problem is in #P, which is not entirely obvious at first glance. To show this, it is enough to show that for every $$S \subseteq E$$, we can determine in PTIME if $$S$$ is the image of some selection function. This can be done as follows. First, construct the bipartite graph $$G_S$$ with nodes in the left partition being the nodes of $$G$$ and nodes in the right partition being edges in $$S$$, and connect $$v$$ in the left partition to $$e$$ in $$S$$ if $$v$$ is an endpoint of $$e$$. Then, compute the size $$m$$ of a maximum cardinality matching of $$G_S$$. Accept if $$m=|S|$$, and reject otherwise (observe that $$m$$ is always $$\leq |S|)$$. It is easy to check that this accepts iff $$S$$ is the image of some selection function.

To Question 2: The problem is #P-hard on general graphs (not sure about bipartite graphs). The family of edge sets of a graph inducing pseudoforests forms the family of independent sets of a bicircular matroid. Counting the number of independent sets of a matroid $$M$$ is equivalent to computing the Tutte polynomial $$t(M;2,1)$$. It is shown by Giménez and Noy that computing $$t(M;2,1)$$ is #P-hard even if $$M$$ is a bicircular matroid given as a graph.