<p><strong>To Question 1</strong>: The graphs induced by such edge sets are known as <em>pseudoforests</em>. As your proof of the membership to #P implies, an edge set is the image of a selection function if and only if the graph induced by the edge set allows an edge orientation in which each vertex has out-degree at most 1. A graph is a pseudoforest if each connected component is a tree or a tree + one edge. It is known (and easy to see) that a graph is a pseudoforest if and only if it admits an outdegree-at-most-1 orientation.</p>

<p><strong>To Question 2</strong>: 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 <em>bicircular matroid</em>. Counting the number of independent sets of a matroid <span class="math-container">$M$</span> is equivalent to computing the Tutte polynomial <span class="math-container">$t(M;2,1)$</span>. It is shown by <a href="https://doi.org/10.1017/S0963548305007327" rel="noreferrer">Giménez and Noy</a> that computing <span class="math-container">$t(M;2,1)$</span> is #P-hard even if <span class="math-container">$M$</span> is a bicircular matroid given as a graph.</p>

CC BY-SA 4.0
2019-12-17T19:28:11.923Z
Excellent, thanks! I'll try to understand if their result applies to bicircular matroids obtained from bipartite graphs then :)
M.Monet
CC BY-SA 4.0
2019-12-17T13:53:04.220Z
2019-12-17T13:53:04.220Z
Yota Otachi
<p>Let <span class="math-container">$G=(V,E)$</span> be an undirected graph. What I call a <em>selection function</em> of <span class="math-container">$G$</span> is a partial function <span class="math-container">$f:V \to E$</span> such that for every node <span class="math-container">$v$</span>, if <span class="math-container">$f(v)$</span> is defined then it is one of the adjacent edges to <span class="math-container">$v$</span>. In other words, every node can either select no edge or select an edge that is adjacent to it. The image of <span class="math-container">$f$</span> is simply <span class="math-container">$\mathrm{Im}(f)= \{e \in E \mid \exists v \in V \text{ s.t. } e=f(v)\}$</span> i.e., the set of edges that are selected.</p>

<p>I am interested in the following counting problem:</p>

<p><strong>INPUT</strong>: a graph <span class="math-container">$G$</span></p>

<p><strong>OUTPUT</strong>: <span class="math-container">$|\{\mathrm{Im}(f) \mid f \text{ is a selection function of }G\}|$</span></p>

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

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

<p>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 <span class="math-container">$S \subseteq E$</span>, we can determine in PTIME if <span class="math-container">$S$</span> is the image of some selection function. This can be done as follows. First, construct the bipartite graph <span class="math-container">$G_S$</span> with nodes in the left partition being the nodes of <span class="math-container">$G$</span> and nodes in the right partition being edges in <span class="math-container">$S$</span>, and connect <span class="math-container">$v$</span> in the left partition to <span class="math-container">$e$</span> in <span class="math-container">$S$</span> if <span class="math-container">$v$</span> is an endpoint of <span class="math-container">$e$</span>. Then, compute the size <span class="math-container">$m$</span> of a <a href="https://en.wikipedia.org/wiki/Maximum_cardinality_matching" rel="noreferrer">maximum cardinality matching</a> of <span class="math-container">$G_S$</span>. Accept if <span class="math-container">$m=|S|$</span>, and reject otherwise (observe that <span class="math-container">$m$</span> is always <span class="math-container">$\leq |S|)$</span>. It is easy to check that this accepts iff <span class="math-container">$S$</span> is the image of some selection function.</p>

<reference-request><graph-theory><counting-complexity>
Is this a known problem, and is it #P-complete?
M.Monet
# Is this a known problem, and is it #P-complete?

(Asked by: username_0 on 2019-12-16)

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](https://en.wikipedia.org/wiki/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.

**Tags:** reference-request, graph-theory, counting-complexity

---

## 1 answers

### Answer by username_1 on 2019-12-17. Score: 9 | Accepted answer

**To Question 1**: The graphs induced by such edge sets are known as *pseudoforests*. As your proof of the membership to #P implies, an edge set is the image of a selection function if and only if the graph induced by the edge set allows an edge orientation in which each vertex has out-degree at most 1. A graph is a pseudoforest if each connected component is a tree or a tree + one edge. It is known (and easy to see) that a graph is a pseudoforest if and only if it admits an outdegree-at-most-1 orientation.

**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](https://doi.org/10.1017/S0963548305007327) that computing $t(M;2,1)$ is #P-hard even if $M$ is a bicircular matroid given as a graph.

> **Comments:**
> **username_0**: Excellent, thanks! I'll try to understand if their result applies to bicircular matroids obtained from bipartite graphs then :)  

---

