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

<blockquote>
  <p><strong>INPUT</strong>: a directed graph <span class="math-container">$G=(V,E)$</span>, and integer <span class="math-container">$k \in \mathbb{N}_{\geq 1}$</span>.</p>
  
  <p><strong>OUTPUT</strong>: <span class="math-container">$|\mathrm{Span}_k(G)|$</span>, where <span class="math-container">$\mathrm{Span}_k(G) = \{\nu(G) \mid \nu:V \to [k]\}$</span>.</p>
</blockquote>

<p>In other words, I want to count the number of distinct graphs that can be obtained from <span class="math-container">$G$</span> by a <span class="math-container">$k$</span>-valuation of <span class="math-container">$G$</span>.</p>

<p><strong>My question: has this problem already been studied? What is its complexity?</strong></p>

<p><strong>Small example</strong></p>

<p>Let <span class="math-container">$G=(V,E)$</span> be the triangle graph, i.e., <span class="math-container">$V=\{a,b,c\}$</span> and <span class="math-container">$E = \{(a,b),(b,c),(c,a)\}$</span>, and let <span class="math-container">$k=2$</span>. Then <span class="math-container">$\mathrm{Span}_k(G)$</span> contains <span class="math-container">$4$</span> graphs:</p>

<ul>
<li><span class="math-container">$G_1 = \{V_1,E_1\}$</span> where <span class="math-container">$V_1 = \{1\}$</span> and <span class="math-container">$E_1 = \{(1,1)\}$</span>;</li>
<li><span class="math-container">$G_2 = \{V_2,E_2\}$</span> where <span class="math-container">$V_2 = \{2\}$</span> and <span class="math-container">$E_2 = \{(2,2)\}$</span>;</li>
<li><span class="math-container">$G_3 = \{V_3,E_3\}$</span> where <span class="math-container">$V_3 = \{1,2\}$</span> and <span class="math-container">$E_3 = \{(1,2),(2,2),(2,1)\}$</span>;</li>
<li><span class="math-container">$G_4 = \{V_4,E_4\}$</span> where <span class="math-container">$V_4 = \{1,2\}$</span> and <span class="math-container">$E_4 = \{(2,1),(1,1),(1,2)\}$</span>.</li>
</ul>

<p>So the output should be <span class="math-container">$4$</span>. Note that, although <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> (and <span class="math-container">$G_3$</span> and <span class="math-container">$G_4$</span>) are isomorphic, they are still counted as different.</p>

<p><strong>Preliminary observations</strong></p>

<ul>
<li>It seems to be a variant of counting the number of <a href="https://en.wikipedia.org/wiki/Quotient_graph" rel="nofollow noreferrer">quotient graphs</a> of <span class="math-container">$G$</span>, but I don't see an obvious reduction. Also, I have not found any work on counting the quotient graphs.</li>
<li>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 <a href="https://www.researchgate.net/publication/226508658_On_counting_and_approximation" rel="nofollow noreferrer">Köbler, J., Schöning, U., &amp; Torán, J. (1989). On counting and approximation. Acta Informatica, 26(4), 363-379</a>. Indeed, a machine can just guess a <span class="math-container">$k$</span>-valuation <span class="math-container">$\nu$</span>, and then write the graph <span class="math-container">$\nu(G)$</span> (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.</li>
<li>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?</li>
<li>Is it in #P? It doesn't seem so, but I don't see a simple #P-harness proof either...</li>
<li>If we define <span class="math-container">$\mathrm{SurjSpan}_k(G)$</span> to be just like <span class="math-container">$\mathrm{Span}_k(G)$</span> but restricted to <span class="math-container">$k$</span>-valuations that are surjective, then clearly we have <span class="math-container">$|\mathrm{Span}_k(G)| = \sum_{i=1}^k \binom{k}{i} |\mathrm{SurjSpan}_i(G)|$</span>. So the problems of counting <span class="math-container">$|\mathrm{SurjSpan}_k(G)|$</span> and <span class="math-container">$|\mathrm{Span}_k(G)|$</span> are reducible to each other (using Turing reductions here).</li>
</ul>

CC BY-SA 4.0
2019-04-17T22:52:09.237Z
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?
Joshua Grochow
CC BY-SA 4.0
2019-04-18T13:16:53.563Z
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?
M.Monet
CC BY-SA 4.0
2019-04-19T02:17:38.940Z
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.
Joshua Grochow
CC BY-SA 4.0
2019-05-22T23:21:26.560Z
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$.
M.Monet
<cc.complexity-theory><reference-request><graph-theory>
Counting quotient graphs, but not exactly
M.Monet
# Counting quotient graphs, but not exactly

(Asked by: username_0 on 2019-04-17)

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](https://en.wikipedia.org/wiki/Quotient_graph) 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](https://www.researchgate.net/publication/226508658_On_counting_and_approximation). 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).

**Tags:** cc.complexity-theory, reference-request, graph-theory

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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?  
> **username_1**: 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.  
> **username_0**: 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$.  

---

## 0 answers

