Deterministically Counting $k$-Paths and Trees Parameterized by Treewidth in Single-Exponential Time

In line with Corollary 4, we define the collection of edge sets $𝒮$ as follows:

An edge set $S\subseteq E$ constitutes a simple path if and only if the graph $(V(S),S)$ is a tree where every vertex has a degree of at most two. Consequently, the set of trees in $𝒮$ is identical to the set of simple paths within the graph $G$. The condition that $|S|=|V(S)|-1$ for all $S\in 𝒮$ is inherently satisfied by all trees and thus does not alter the number of trees, but does ensure the compatibility of $𝒮$ with Corollary 4. The number of simple paths with length $k$ in graph $G$ is now given by

The condition that $|S|=|V(S)|-1$, while perhaps intuitive, complicates our Dynamic Programming design by requiring us to track both the number of edges and vertices within any edge set. A more computationally efficient strategy involves counting only the total number of vertices and the number of degree-one vertices. This is particularly advantageous because a simple path invariably has exactly two degree-one vertices. Consequently, we will employ the following proposition:

With the equivalence from Proposition 5, we can rewrite our definition of $𝒮$ (without changing $𝒮$ itself):

We can expand the determinant in Equation 3.1 to obtain

The bijection $f:S\stackrel{1-1}{\to }V(S)\setminus p$ maps each edge $e=(u,v)$ in $S$ to a unique vertex $f(e)$ in $V(S)\setminus p$. Observe that if $f(e)$ is distinct from both $u$ and $v$, the corresponding term in the sum becomes zero due to the zero entry $a_{f(e),e}$ in the incidence matrix. Utilizing the property that $|det(A_p[S])|\in 0,1$, we have $|det(A_p[S])|={(det(A_p[S]))}^2$.

To compute Equation 6, we will utilize Dynamic Programming on a given tree decomposition $𝕋$ of $G$. For this purpose, we define the following parameters:

• $\mathrm{■}$

  For every bag $y\in 𝕋$, $s_{\text{deg}}\in {\{0,1,2\}}^{|B_y|}$ denotes the degree of every vertex in $B_y$ in $G[S]$

• $\mathrm{■}$

  For every bag $y\in 𝕋$, $s_1\in {\{0,1\}}^{|B_y|}$ denotes for every vertex in $B_y$ whether it has been used as a value in the bijection $f_1$

• $\mathrm{■}$

  For every bag $y\in 𝕋$, $s_2\in {\{0,1\}}^{|B_y|}$ denotes for every vertex in $B_y$ whether it has been used as a value in the bijection $f_2$

• $\mathrm{■}$

  Let $t$ denote the number of forgotten vertices (in $V_y\setminus B_y$) that have degree one in $S$

• $\mathrm{■}$

  Let $l$ denote the number of edges in $S$

Furthermore, we define the following useful sets:

• $\mathrm{■}$

  Let ${𝒮}_y(s_{\text{deg}},t,l)$ be the collection of all edge sets $S\subseteq E_y$ with exactly $l$ edges, with $t$ vertices of degree one in $V(S)\setminus B_y$, and such that the degree of a vertex $v$ in $B_y$ is equal to $s_{\text{deg}}(v)$ and the degree of all vertices is at most two.

• $\mathrm{■}$

  Consider a set of edges $S\subseteq E_y$, and a set of vertices $P\subseteq V(S)\setminus B_y$. For $i\in 1,2$, we define ${ℱ}_y(S,P,s_i)$ as the set of all bijective functions $f$ that map each edge in $S$ to a unique vertex in $V(S)\setminus (s_i^{-1}(0)\cup P)$.

  Intuitively, ${ℱ}_y(S,P,s_i)$ represents the possible bijections between the edges in $S$ and a selection of vertices from $V(S)$. Since Proposition 5 states that $|V(S)|>|S|$, not all vertices in $V(S)$ can be part of this bijection. The sets $s_i^{-1}(0)$ and $P$ both identify the vertices that are excluded from this mapping. A key distinction is that $s_i^{-1}(0)$ contains vertices within the bag $B_y$, whereas $P$ contains vertices that are strictly outside of $B_y$.

  For a valid $k$-path we will have that $|P|=1$ as in Equation 6. However, during the construction of this $k$-path, we might encounter intermediate states with multiple connected components. In such cases, $|P|$ might need to be greater than one to ensure a valid bijection exists, as more vertices need to be excluded from $V(S)$. Ultimately, we are guaranteed that $|P|=1$. This is because if $|P|=0$, the resulting edge sets form cycles, leading to a determinant of zero. Conversely, if $|P|>1$, the resulting edge sets become disconnected, implying more than two vertices with degree one.

For every entry of the Dynamic Program in bag $y$ we will require that the following partial sum holds:

where we have labeled the $\mathrm{\Sigma }$’s and $\mathrm{\Pi }$ for later reference. Filling in variables, we see that in a root bag $z$ where $E_z=E$ and $B_z=\mathrm{\varnothing }$, we have that $\frac{1}{k}{A}_z(\mathrm{\varnothing },\mathrm{\varnothing },\mathrm{\varnothing },2,k-1)=P_k(G)$, the number of $k$-paths in $G$.

This section details the computation of tables for the functions $A_y$ (defined in Equation 7) for each node type in nice tree decompositions.

Given a host graph $G$ together with a nice path or tree decomposition, we can traverse the decomposition in post-ordering, calculating entries according to the Dynamic Program described above. This procedure gives rise to the following theorem:

To count occurrences of a specific tree $T$, we first need to establish a unique labeling for it. This labeling is derived by decomposing $T$ into path segments, a process that considers three cases based on the degree of each vertex $v$ in $T$:

• $\mathrm{■}$

  deg${}_T{}^{}(v)=1$; $v$ is a leaf.

• $\mathrm{■}$

  deg${}_T{}^{}(v)=2$; $v$ is a path node.

• $\mathrm{■}$

  deg${}_T{}^{}(v)>2$; $v$ is an internal junction.

We define the path segments as follows:

• $\mathrm{■}$

  Starting in every leaf node with an unlabeled edge, we follow the unique path along the (possibly empty) set of connected path nodes, until we encounter an internal junction $j_i$ or another leaf. The paths traced in this way are called the leaf paths of $T$. Note that if a leaf path terminates in two leaf nodes, $T$ is isomorphic to a simple path, and its occurrences can be counted using the method in Section 3. For the remainder of this paper, we assume all leaf paths end in one leaf and one internal junction.

• $\mathrm{■}$

  For each internal junction, trace the paths starting in its unlabeled edges along the (possibly empty) set of connected path nodes until we encounter another internal junction (note that we can not encounter a leaf node, as per the previous step). These path segments are called internal paths.

For an illustration of this procedure, see Figure 1. By design, all edges along paths originating from leaves or internal junctions are labeled. Consequently, since any path not starting at such a point must form a cycle, all edges in the (acyclic) tree $T$ are labeled.

Let $N={\{j_q\}}_q$ be the set of internal junctions in $T$, let $I=\{p_{q,r}=(j_q,v_1,v_2,\mathrm{\dots },j_r),\mathrm{\dots }\}$ the set of internal paths in $T$ denoted by their vertices, and $L=\{l_{q,i}=(j_q,v_1,v_2,\mathrm{\dots },v_k),\mathrm{\dots }\}$ the set of leaf paths in $T$ denoted by their vertices. We will call $(N,I,L)$ the labeling of $T$. Using this labeling, we can prove the following theorem, which will help us count the distinct graphs isomorphic to $T$:

Consider a graph $G=(V,E)$ and a subset of its edges $S\subseteq E$. Let $T$ be a tree with $k$ vertices, $l$ leaves, and labeling ${ℒ}_T=(N,I,L)$. Define ${ℱ}_{{ℒ}_T}(S)$ as the set of functions $f:V(S)\to N\cup I\cup L$ satisfying the conditions of Theorem 7. If $T(G)$ denotes the number of distinct labeled subgraphs of $G$ isomorphic to $T$, then Theorem 7 implies that

where the second step follows from Corollary 4. Consider any edge set $S$. If there exists a function $f\in {ℱ}_{{ℒ}_T}(S)$, then by its defining properties (1) and (2), we have:

• $\mathrm{■}$

  $|f^{-1}(N)|=|N|$

• $\mathrm{■}$

  $|f^{-1}(p_{q,r}\cup j_q\cup j_r)|=\text{len}(p_{q,r})$ for all internal paths $p_{q,r}$

• $\mathrm{■}$

  $|f^{-1}(l_{q,i}\cup j_q)|=\text{len}(l_{q,i})$ for all leaf paths $l_{q,i}$

Since every vertex in $V(T)$ is either an internal junction or belongs to an internal/leaf path, it follows that $|V(S)|=|f^{-1}(N\cup I\cup L)|=|V(T)|$. Consequently, the condition $|S|=|V(S)-1|$ in the first summation simplifies to $|S|=k-1$. This allows us to expand the determinant in Equation 4.2 analogously to Section 3, resulting in

We now construct the partial sum that defines each entry in our Dynamic Program. The definitions of $s_{\text{deg}},s_1,s_2$, and ${ℱ}_y(S,P,s_i)$ are retained from Section 3. Furthermore, we will define new parameters:

• $\mathrm{■}$

  For every bag $y\in 𝕋$, let $s_a\in {(N\cup I\cup L\cup \{0\})}^{|B_y|}$ denote the label assigned to every vertex in bag $y$. Relating to Theorem 7, $s_a(v)$ can be interpreted as $f(v)$ when restricted to the vertices $v$ in $B_y$.

• $\mathrm{■}$

  Let $\alpha \in {\{0,1\}}^{|N|}$ denote for every internal junction $j_q$ in $N$ whether some vertex $v\in V(S)\cup B_y$ should be labeled with $j_q$ in the construction of a function $f\in {ℱ}_{{ℒ}_T}(S)$. The vector $\alpha$ is indexed by the internal junctions in $N$, and we will denote by $\alpha (j_q)$ the value corresponding to internal junction $j_q$. Conversely, we will denote by ${\alpha }^{-1}(1)$ all internal junctions in $N$ for which $\alpha$ is equal to one.

• $\mathrm{■}$

  Let $\lambda \in {\mathbb{N}}^{|I\cup L|}$ denote for every internal path in $I$ and leaf path in $L$ how many vertices in $V(S)$ should be labeled with this path in the construction of a function $f\in {ℱ}_{{ℒ}_T}(S)$. The vector $\lambda$ is indexed by the internal and leaf paths in $I\cup L$, and we will denote by $\lambda (p)$ the value corresponding to the path $p$. Conversely, we will denote by ${\lambda }^{-1}({\mathbb{N}}_{⩾1})$ all paths in $I\cup L$ for which $\lambda$ is at least one.

• $\mathrm{■}$

  Let $t_{leaf}\in {\{0,1\}}^{|L|}$ denote for every leaf path $l_{q,i}$ in $L$ the number of forgotten vertices $v$ with degree one for which $f(v)$ should map to $l_{q,i}$ in the construction of some $f\in {ℱ}_{{ℒ}_T}(S)$.

• $\mathrm{■}$

  Let ${𝒮}_y(s_{\text{deg}},s_a,\alpha ,\lambda ,t_{leaf})$ be the collection of all edge sets $S\subseteq E_y$ such that there exists a labeling function $f_{y,S}:V(S)\cup B_y\to {\alpha }^{-1}(1)\cup {\lambda }^{-1}({\mathbb{N}}_{⩾1})\cup \{0\}$ that obeys the following requirements:

  1. 0)

     The functions ${𝒇}_{𝒚,𝑺}$ and ${𝒔}_{𝒂}$ are identical when restricted to bag vertices

     • –

       i.e. for all bag vertices $v\in B_y$, we have that $f_{y,S}(v)=s_a(v)$

  2. 1)

     All internal junctions in ${𝜶}^{-1}(1)$ are the image of exactly one vertex in $𝑽(𝑺)\cup {𝑩}_{𝒚}$ under ${𝒇}_{𝒚,𝑺}$

     • –

       i.e. for all internal junctions $v\in {\alpha }^{-1}(1)$, we have that $|f_{y,S}^{-1}(v)|=1$

  3. 2)

     All paths $𝒑$ in $𝑰\cup 𝑳$ are the image of exactly ${𝝀}^{-1}(𝒑)$ vertices in $𝑽(𝑺)\cup {𝑩}_{𝒚}$ under ${𝒇}_{𝒚,𝑺}$

     • –

       i.e. for all paths $p\in {\lambda }^{-1}({\mathbb{N}}_{⩾1})$, we have that $|f_{y,S}^{-1}(p)|=\lambda (p)$

  4. 3)

     Vertex degrees are preserved in forgotten vertices and are equal to ${𝒔}_{\text{deg}}$ in bag vertices

     • –

       i.e. for all internal junctions $j_q\in {\alpha }^{-1}(1)$, if the vertex $v\in f_{y,S}^{-1}(j_q)$ (there is exactly one such vertex as per (1)) is a forgotten vertex, then deg${}_S{}^{}(v)={\text{deg}}_T(j_q)$. If $v$ is a bag vertex, then deg${}_S{}^{}(v)=s_{\text{deg}}(v)$.

     • –

       for all internal paths $p_{q,r}\in {\lambda }^{-1}({\mathbb{N}}_{⩾1})\cap I$, we have that all forgotten vertices $v\in f_{y,S}^{-1}(p_{q,r})\setminus B_y$ have degree two in $S$. All bag vertices $v\in f_{y,S}^{-1}(p_{q,r})\cap B_y$ have degree $s_{\text{deg}}(v)$ in $S$.

     • –

       and, for all leaf paths $l_{q,i}\in {\lambda }^{-1}({\mathbb{N}}_{⩾1})\cap L$, we have that exactly $t_{leaf}(l_{q,i})$ forgotten vertices in $f_{y,S}^{-1}(l_{q,i})\setminus B_y$ have degree one in $S$, and all other vertices in $f_{y,S}^{-1}(l_{q,i})\setminus B_y$ have degree two in $S$. All bag vertices $v\in f_{y,S}^{-1}(l_{q,i})\cap B_y$ have degree $s_{\text{deg}}(v)$ in $S$.

  5. 4)

     Neighborhoods are preserved

     • –

       i.e. for all internal paths $p_{q,r}\in {\lambda }^{-1}({\mathbb{N}}_{⩾1})\cap I$, and for all vertices $v\in f_{y,S}^{-1}(p_{q,r})$, let $N(v)$ denote the neighborhood of $v$ in $S$. We have that $f_{y,S}(N(v))\subseteq \{p_{q,r},j_q,j_r\}$.

     • –

       and, for all leaf paths $l_{q,i}\in {\lambda }^{-1}({\mathbb{N}}_{⩾1})\cap L$, and for all vertices $v\in f_{y,S}^{-1}(l_{q,i})$, we have that $f_{y,S}(N(v))\subseteq \{l_{q,i},j_q\}$.