2
$\begingroup$

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.

|cite|improve this question
$\endgroup$
2
$\begingroup$

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|}$.
|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Victor Jan 20 at 14:50
  • $\begingroup$ 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? $\endgroup$ – a3nm Jan 21 at 15:12
  • $\begingroup$ 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. $\endgroup$ – Gamow Jan 21 at 17:02
  • $\begingroup$ 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. $\endgroup$ – Victor Jan 22 at 11:20
  • $\begingroup$ 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. $\endgroup$ – a3nm Jan 22 at 12:39
2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Victor Jan 21 at 11:19

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.