<p>After polynomial time preprocessing, you may assume that every edge in <span class="math-container">$E$</span> lies on some simple <span class="math-container">$s$</span>-<span class="math-container">$t$</span>-path.</p>

<ul>
<li><p>If all simple paths between <span class="math-container">$s$</span> and <span class="math-container">$t$</span> are of the same length, then <span class="math-container">$G$</span> is series-parallel, with <span class="math-container">$s$</span> as left terminal and <span class="math-container">$t$</span> as right terminal vertex. This can be seen easily, since the forbidden subgraphs for series-parallel graphs (= subdivisions of diamonds) create two paths of different lengths between <span class="math-container">$s$</span> and <span class="math-container">$t$</span>.</p></li>
<li><p>In a series-parallel graph, the number of spanning subgraphs containing a simple <span class="math-container">$s$</span>-<span class="math-container">$t$</span>-path can be determined in polynomial time by dynamic programming. </p></li>
</ul>

<p>In the dynamic program, we build up the graph by series and parallel compositions. For every resulting subgraph <span class="math-container">$G'$</span>, we compute the number <span class="math-container">$p^+(G')$</span> of spanning subgraphs that do contain a simple path from its left terminal to its right terminal and the number <span class="math-container">$p^-(G')$</span> of spanning subgraphs that do not contain such a path. </p>

<ul>
<li>In a series composition on <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span>, we get <span class="math-container">$p^+(G)=p^+(G_1)\cdot p^+(G_2)$</span>.</li>
<li>In a parallel composition on <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span>, we get <span class="math-container">$p^-(G)=p^-(G_1)\cdot p^-(G_2)$</span>.</li>
<li>In both cases, the missing value <span class="math-container">$p^+(G)$</span> or <span class="math-container">$p^-(G)$</span> for <span class="math-container">$G=(V,E)$</span> can be computed from <span class="math-container">$p^+(G)+p^-(G)=2^{|E|}$</span>.</li>
</ul>

CC BY-SA 4.0
2019-01-20T14:50:07.187Z
Gamow, thanks for your reply. I would be grateful if could clarify how we go from the number of s-t simple paths to the number of spanning subgraphs having at least one s-t path.
Victor
CC BY-SA 4.0
2019-01-21T15:12:20.480Z
Sorry if that's basic, but I'm confused about the implication "all simple paths between $s$ and $t$ have same length" => "$G$ is series-parallel". Consider the N-shaped DAG $s\rightarrow a$, $s\rightarrow b$, $a \rightarrow c$, $a \rightarrow d$, $b \rightarrow d$, $c \rightarrow t$, $d \rightarrow t$: all paths from $s$ to $t$ have length $3$, but are you sure it's series-parallel?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-01-21T17:02:11.397Z
The problem deals with *undirected* graphs. In the directed case, already the preprocessing step would break down, since in digraphs it is NP-complete to decide whether a given arc lies on a simple s-t-dipath.
Gamow
CC BY-SA 4.0
2019-01-22T11:20:06.253Z
Gamow, agree, this is a very important distinction. Actually, your solution and the reduction of @a3nm demonstrates the difference between the two cases if we consider the GRAPH RELIABILITY problem (where we are given a graph in which every edge can fail independently with some individual probability, and two vertices s, t in G; the goal is to compute the probability that there exists an s-t path consisting of non-failed edges). In the undirected case, your approach would solve the problem in polynomial time, while the reduction of a3nm shows that the problem is #P-hard in the directed case.
Victor
CC BY-SA 4.0
2019-01-22T12:39:49.663Z
Ah OK I missed that this was about undirected graphs, sorry. And you are right @Victor, my answer assumes directed graphs, I'll edit it to reflect that.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-01-20T14:12:09.013Z
2019-01-20T17:31:39.980Z
2019-01-20T17:31:39.980Z
Gamow
<p>The following answer doesn't really answer the question given, because it's not about counting spanning subgraphs but about counting all subgraphs where some edges are <em>fixed</em> (i.e., cannot be removed). However, I'm posting it because it gives me the strong impression that having different path lengths is not crucial to achieving hardness for this kind of problems. Maybe a variant of the argument can be used to show #P-hardness for the actual problem asked in the question. <em>Edit: Another point is that this answer uses directed graphs, not undirected graphs.</em></p>

<p>If you can fix edges, then the problem in #P-hard. To see why, let's reduce from the problem #PP2DNF, of counting the number of satisfying assignments of a positive partitioned 2-DNF Boolean formula, i.e., a formula <span class="math-container">$\phi$</span> on variables <span class="math-container">$X_1, \ldots, X_n, Y_1, \ldots, Y_m$</span> of the form <span class="math-container">$\bigvee_{1 \leq j \leq k} X_{n_j} \land Y_{m_j}$</span>. This problem is #P-complete by <a href="https://epubs.siam.org/doi/abs/10.1137/0212053" rel="nofollow noreferrer">this paper</a> (sorry, couldn't find an open-access version).</p>

<p>Given <span class="math-container">$\phi$</span> let's build a DAG <span class="math-container">$G$</span> with the source <span class="math-container">$s$</span>, the sink <span class="math-container">$t$</span>, and vertices <span class="math-container">$x_1, \ldots, x_n$</span> and <span class="math-container">$y_1, \ldots, y_m$</span>. Put one edge from <span class="math-container">$s$</span> to <span class="math-container">$x_i$</span> for each <span class="math-container">$i$</span>, one edge from <span class="math-container">$y_i$</span> to <span class="math-container">$t$</span> for each <span class="math-container">$i$</span>, and for each clause <span class="math-container">$X_{n_j} \land Y_{m_j}$</span> add an edge from <span class="math-container">$x_{n_j}$</span> to <span class="math-container">$y_{m_j}$</span> which is <em>fixed</em>. This completes the definition of <span class="math-container">$G$</span>: note that all possible paths from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> have length 3.</p>

<p>Now, choosing a subgraph of <span class="math-container">$G$</span> while keeping the <em>fixed</em> edges amounts to keeping a subset of the edges incident to <span class="math-container">$s$</span>, and a subset of the edges incident to <span class="math-container">$t$</span>. It is clear that there is a bijection between such subgraphs and the valuations of the variables of <span class="math-container">$\phi$</span>, where we set a variable to true if we keep its one incident edge that is not fixed. Further, any path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span> in such a subgraph of <span class="math-container">$G$</span> witnesses the existence of a clause that satisfies <span class="math-container">$\phi$</span> in the corresponding valuation. Hence, the number of satisfying valuations of <span class="math-container">$\phi$</span> is exactly the number of subgraphs of <span class="math-container">$G$</span> that keep the fixed edges, concluding the proof.</p>

<p>(This proof is inspired by the proof of Theorem 3.2 in the book Probabilistic Databases by Suciu, Olteanu, Ré, and Koch; sorry again but I don't have an open-access link to this either.)</p>

CC BY-SA 4.0
2019-01-21T11:19:22.803Z
a3nm, thanks for your reply and the nice reduction! Regarding the original problem, I'm convinced now by the argument in the updated answer of Gamow that the problem is polynomial-time solvable.
Victor
CC BY-SA 4.0
2019-01-20T17:02:53.153Z
2019-01-22T12:40:28.353Z
2019-01-22T12:40:28.353Z
Antoine Amarilli 'a3nm'
<p>S-T CONNECTEDNESS</p>

<p><strong>Input:</strong> a (undirected) graph <span class="math-container">$G=(V,E)$</span>; <span class="math-container">$s,t \in V.$</span></p>

<p><strong>Output:</strong> number of spanning subgraphs of <span class="math-container">$G$</span> in which there is a path from <span class="math-container">$s$</span> to <span class="math-container">$t$</span>.</p>

<hr>

<p>S-T CONNECTEDNESS problem is known to be #P-complete (<em>[Valiant, L. G. (1979). The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3), 410-421.]</em>).</p>

<p>I'm interested in those instances of S-T CONNECTEDNESS in which all simple paths between <span class="math-container">$s$</span> and <span class="math-container">$t$</span> are of the same length. Is anything known about the complexity of the problem on these instances? In particular, does the problem remain #P-complete?</p>

<p><strong>Remark:</strong> In the Valiant's reduction, there are many simple paths between <span class="math-container">$s$</span> and <span class="math-container">$t$</span> of different lengths.</p>

<cc.complexity-theory><counting-complexity>
Is S-T CONNECTEDNESS #P-complete on instances when all s-t paths are of the same length?
Victor
# Is S-T CONNECTEDNESS #P-complete on instances when all s-t paths are of the same length?

(Asked by: username_0 on 2019-01-20)

S-T CONNECTEDNESS

**Input:** a (undirected) graph $G=(V,E)$; $s,t \in V.$

**Output:** number of spanning subgraphs of $G$ in which there is a path from $s$ to $t$.

---

S-T CONNECTEDNESS problem is known to be #P-complete (*[Valiant, L. G. (1979). The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3), 410-421.]*).

I'm interested in those instances of S-T CONNECTEDNESS in which all simple paths between $s$ and $t$ are of the same length. Is anything known about the complexity of the problem on these instances? In particular, does the problem remain #P-complete?

**Remark:** In the Valiant's reduction, there are many simple paths between $s$ and $t$ of different lengths.

**Tags:** cc.complexity-theory, counting-complexity

---

## 2 answers

### Answer by username_1 on 2019-01-20. Score: 3 | Accepted answer

After polynomial time preprocessing, you may assume that every edge in $E$ lies on some simple $s$-$t$-path.

* If all simple paths between $s$ and $t$ are of the same length, then $G$ is series-parallel, with $s$ as left terminal and $t$ as right terminal vertex. This can be seen easily, since the forbidden subgraphs for series-parallel graphs (= subdivisions of diamonds) create two paths of different lengths between $s$ and $t$.
* In a series-parallel graph, the number of spanning subgraphs containing a simple $s$-$t$-path can be determined in polynomial time by dynamic programming.

In the dynamic program, we build up the graph by series and parallel compositions. For every resulting subgraph $G'$, we compute the number $p^+(G')$ of spanning subgraphs that do contain a simple path from its left terminal to its right terminal and the number $p^-(G')$ of spanning subgraphs that do not contain such a path.

* In a series composition on $G\_1$ and $G\_2$, we get $p^+(G)=p^+(G\_1)\cdot p^+(G\_2)$.
* In a parallel composition on $G\_1$ and $G\_2$, we get $p^-(G)=p^-(G\_1)\cdot p^-(G\_2)$.
* In both cases, the missing value $p^+(G)$ or $p^-(G)$ for $G=(V,E)$ can be computed from $p^+(G)+p^-(G)=2^{|E|}$.

> **Comments:**
> **username_0**: Gamow, thanks for your reply. I would be grateful if could clarify how we go from the number of s-t simple paths to the number of spanning subgraphs having at least one s-t path.  
> **username_2**: Sorry if that's basic, but I'm confused about the implication "all simple paths between $s$ and $t$ have same length" => "$G$ is series-parallel". Consider the N-shaped DAG $s\rightarrow a$, $s\rightarrow b$, $a \rightarrow c$, $a \rightarrow d$, $b \rightarrow d$, $c \rightarrow t$, $d \rightarrow t$: all paths from $s$ to $t$ have length $3$, but are you sure it's series-parallel?  
> **username_1**: The problem deals with *undirected* graphs. In the directed case, already the preprocessing step would break down, since in digraphs it is NP-complete to decide whether a given arc lies on a simple s-t-dipath.  
> **username_0**: Gamow, agree, this is a very important distinction. Actually, your solution and the reduction of @a3nm demonstrates the difference between the two cases if we consider the GRAPH RELIABILITY problem (where we are given a graph in which every edge can fail independently with some individual probability, and two vertices s, t in G; the goal is to compute the probability that there exists an s-t path consisting of non-failed edges). In the undirected case, your approach would solve the problem in polynomial time, while the reduction of a3nm shows that the problem is #P-hard in the directed case.  
> **username_2**: Ah OK I missed that this was about undirected graphs, sorry. And you are right @Victor, my answer assumes directed graphs, I'll edit it to reflect that.  

---

### Answer by username_2 on 2019-01-20. Score: 2

The following answer doesn't really answer the question given, because it's not about counting spanning subgraphs but about counting all subgraphs where some edges are *fixed* (i.e., cannot be removed). However, I'm posting it because it gives me the strong impression that having different path lengths is not crucial to achieving hardness for this kind of problems. Maybe a variant of the argument can be used to show #P-hardness for the actual problem asked in the question. *Edit: Another point is that this answer uses directed graphs, not undirected graphs.*

If you can fix edges, then the problem in #P-hard. To see why, let's reduce from the problem #PP2DNF, of counting the number of satisfying assignments of a positive partitioned 2-DNF Boolean formula, i.e., a formula $\phi$ on variables $X\_1, \ldots, X\_n, Y\_1, \ldots, Y\_m$ of the form $\bigvee\_{1 \leq j \leq k} X\_{n\_j} \land Y\_{m\_j}$. This problem is #P-complete by [this paper](https://epubs.siam.org/doi/abs/10.1137/0212053) (sorry, couldn't find an open-access version).

Given $\phi$ let's build a DAG $G$ with the source $s$, the sink $t$, and vertices $x\_1, \ldots, x\_n$ and $y\_1, \ldots, y\_m$. Put one edge from $s$ to $x\_i$ for each $i$, one edge from $y\_i$ to $t$ for each $i$, and for each clause $X\_{n\_j} \land Y\_{m\_j}$ add an edge from $x\_{n\_j}$ to $y\_{m\_j}$ which is *fixed*. This completes the definition of $G$: note that all possible paths from $s$ to $t$ have length 3.

Now, choosing a subgraph of $G$ while keeping the *fixed* edges amounts to keeping a subset of the edges incident to $s$, and a subset of the edges incident to $t$. It is clear that there is a bijection between such subgraphs and the valuations of the variables of $\phi$, where we set a variable to true if we keep its one incident edge that is not fixed. Further, any path from $s$ to $t$ in such a subgraph of $G$ witnesses the existence of a clause that satisfies $\phi$ in the corresponding valuation. Hence, the number of satisfying valuations of $\phi$ is exactly the number of subgraphs of $G$ that keep the fixed edges, concluding the proof.

(This proof is inspired by the proof of Theorem 3.2 in the book Probabilistic Databases by Suciu, Olteanu, Ré, and Koch; sorry again but I don't have an open-access link to this either.)

> **Comments:**
> **username_0**: a3nm, thanks for your reply and the nice reduction! Regarding the original problem, I'm convinced now by the argument in the updated answer of Gamow that the problem is polynomial-time solvable.  

---

