5
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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 that computing $t(M;2,1)$ is #P-hard even if $M$ is a bicircular matroid given as a graph.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Excellent, thanks! I'll try to understand if their result applies to bicircular matroids obtained from bipartite graphs then :) $\endgroup$ – M.Monet Dec 17 '19 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.