2
$\begingroup$

Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph that is equal to the difference between the graph's degree matrix (a diagonal matrix with vertex degrees on the diagonals) and its adjacency matrix (a $(0,1)$-matrix with $1$'s at places corresponding to entries where the vertices are adjacent and $0$'s otherwise).

It is known that for a given connected graph $G$ with $n$ labeled vertices, let $λ_1,λ_2,...,λ_{n−1}$ be the non-zero eigenvalues of its Laplacian matrix. Then the number of spanning trees of $G$ is $t(G)=\frac{1}{n} \lambda_1\lambda_2\cdots\lambda_{n-1}\,$

Now I want to extend it to the steiner tree. A $T$-Steiner tree is a subgraph of $G$ that is a tree and that spans $T$. When $T=V(G)$, a $T$-Steiner tree is a spanning tree. My question is that what is the connection between general $T$-Steiner tree and the Laplacian matrix? So far I didn't find any known results about this extension. Your comments and discussion are welcome.

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ are you asking if anything is known about this ? Given the series of questions you've posted, one common pattern that you might consider addressing is that you should try to (a) provide some motivation for why you're asking the question and (b) give an indication of what you've already discovered thus far that's relevant. People here are happy to help, but there's an expectation of due diligence. $\endgroup$
    – Suresh Venkat
    Mar 13, 2014 at 17:59
  • 1
    $\begingroup$ @SureshVenkat, thank you very much for your suggestions. $\endgroup$
    – user17918
    Mar 13, 2014 at 18:09
  • 1
    $\begingroup$ This was a simultaneous cross-post to mathoverflow. Please avoid behavior in violation of our rules in the future. I will keep this question open because of the answer already given. $\endgroup$
    – Artem Kaznatcheev ♦
    Mar 16, 2014 at 18:08

1 Answer 1

Reset to default
3
$\begingroup$

Let me give a side answer to your question. Consider the variant where you only care about edge-minimal spanning trees: for 2 terminals $s$ and $t$, the problem is equivalent to counting simple $s,t$-paths, which is $\# P$-complete; also, the parameterized version where you ask for paths of length $k$ is $\# W[1]$-hard. If you care about arbitrary $T$-steiner trees (i.e. not necessarily minimal), I expect that it is also $\# P$-hard though I'm not aware of any reference. These hardness results suggest that it's unlikely to find some "nice formula" for the number of $T$-steiner trees.

The references are: "The complexity of enumeration and reliability problems" by L. G. Valiant, and "The parameterized complexity of counting problems" by J. Flum and M. Grohe.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Cheriyan and Salavatipour [1] proved that the problem of finding maximum number of edge-disjoint (or vertex-disjoint) Steiner trees is APX-hard even if there are only 4 terminals. Kaski [2] proved that it is NP-complete to decide whether a graph contains 2 edge-disjoint Steiner trees for $T$. references: [1]J. Cheriyan, M.R. Salavatipour, Hardness and Approximation Results for Packing Steiner Trees, Algorithmica 45 (2006), 21-43. [2]P. Kaski, Packing Steiner trees with identical terminal sets, Information Processing Letters 91 (2004), 1-5. $\endgroup$
    – user17918
    Mar 16, 2014 at 19:07
  • $\begingroup$ Alright, thanks for pointing out the proper references :) $\endgroup$
    – Super8
    Mar 17, 2014 at 1:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.