3
$\begingroup$

All graphs considered will be directed graphs $G=(V,E)$, with $E \subseteq V \times V$ (so possibly with self-loops). For $k \in \mathbb{N}_{\geq 1}$, I will write $[k]$ the set $\{1,\ldots,k\}$. A $k$-valuation of $G$ is a mapping $\nu: V \to [k]$. Given a $k$-valuation $\nu$ of $G=(V,E)$, I define the graph $\nu(G)=(V_\nu,E_\nu)$ by $V_\nu = \{\nu(v) \mid v \in V\}$ and $E_\nu = \{(\nu(v),\nu(v')) \mid (v,v') \in E\}$. I am interested in the following counting problem:

INPUT: a directed graph $G=(V,E)$, and integer $k \in \mathbb{N}_{\geq 1}$.

OUTPUT: $|\mathrm{Span}_k(G)|$, where $\mathrm{Span}_k(G) = \{\nu(G) \mid \nu:V \to [k]\}$.

In other words, I want to count the number of distinct graphs that can be obtained from $G$ by a $k$-valuation of $G$.

My question: has this problem already been studied? What is its complexity?

Small example

Let $G=(V,E)$ be the triangle graph, i.e., $V=\{a,b,c\}$ and $E = \{(a,b),(b,c),(c,a)\}$, and let $k=2$. Then $\mathrm{Span}_k(G)$ contains $4$ graphs:

  • $G_1 = \{V_1,E_1\}$ where $V_1 = \{1\}$ and $E_1 = \{(1,1)\}$;
  • $G_2 = \{V_2,E_2\}$ where $V_2 = \{2\}$ and $E_2 = \{(2,2)\}$;
  • $G_3 = \{V_3,E_3\}$ where $V_3 = \{1,2\}$ and $E_3 = \{(1,2),(2,2),(2,1)\}$;
  • $G_4 = \{V_4,E_4\}$ where $V_4 = \{1,2\}$ and $E_4 = \{(2,1),(1,1),(1,2)\}$.

So the output should be $4$. Note that, although $G_1$ and $G_2$ (and $G_3$ and $G_4$) are isomorphic, they are still counted as different.

Preliminary observations

  • It seems to be a variant of counting the number of quotient graphs of $G$, but I don't see an obvious reduction. Also, I have not found any work on counting the quotient graphs.
  • My problem is in the class Span-P, which is the class of counting problems that can be defined as the number of distinct outputs of a nondeterministic Turing machine running in polynomial time. This class was introduced in Köbler, J., Schöning, U., & Torán, J. (1989). On counting and approximation. Acta Informatica, 26(4), 363-379. Indeed, a machine can just guess a $k$-valuation $\nu$, and then write the graph $\nu(G)$ (in the right order). Ideally I would like to show that it is Span-P complete. For the hardness part, if it helps I don't mind considering the version of the problem where edges can be labeled with a fixed, finite alphabet.
  • Since it is in Span-P, according to this same paper (Theorem 7.2) this problem can be approximated in polynomial time, but using an oracle to NP. Can we get rid of the oracle to show that the problem has a FPRAS?
  • Is it in #P? It doesn't seem so, but I don't see a simple #P-harness proof either...
  • If we define $\mathrm{SurjSpan}_k(G)$ to be just like $\mathrm{Span}_k(G)$ but restricted to $k$-valuations that are surjective, then clearly we have $|\mathrm{Span}_k(G)| = \sum_{i=1}^k \binom{k}{i} |\mathrm{SurjSpan}_i(G)|$. So the problems of counting $|\mathrm{SurjSpan}_k(G)|$ and $|\mathrm{Span}_k(G)|$ are reducible to each other (using Turing reductions here).
$\endgroup$
  • 1
    $\begingroup$ How is this different from quotient graphs? It seems like you are simply asking to count all quotients of G with at most k vertices, but perhaps I am missing something? $\endgroup$ – Joshua Grochow Apr 17 at 22:52
  • $\begingroup$ If you do not count two isomorphic quotient graphs as different, then yes it is the same as my problem, but where you do not count isomorphic graphs as different (but this is not what I want). If you count different isomorphic quotient graphs as different, then they are actually all different (since they don't have the same set of vertices), so the number is just the number of partitions of $V$ (with at most $k$ classes), no? $\endgroup$ – M.Monet Apr 18 at 13:16
  • $\begingroup$ Ah, I see. No, even if you count labeled graphs as distinct, you could still get more than one that are identical. You in fact already gave an example of this. There are 8 ordered partitions of 3, but only 4 distinct graphs in your example. $\endgroup$ – Joshua Grochow Apr 19 at 2:17
  • $\begingroup$ I still don't understand. If you count different labeled graphs as distinct, then every partition gives a distinct graph (since the label of a node in the quotient graph is the class it represents), so it seems that you are just counting the number partitions of $V$. $\endgroup$ – M.Monet May 22 at 23:21

Your Answer

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

Browse other questions tagged or ask your own question.