Is S-T CONNECTEDNESS #P-complete on instances when all s-t paths are of the same length?

Question

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.

Answer 1

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|}$.

Answer 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 (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.)