Giovanna Kobus

Conrado Amir

Kafshdar Goharshady

Pavel Hudec

Pingjiang Li

Harshit Jitendra Motwani

Faster Treewidth-based Approximations for Wiener Index

Keywords: 2012 ACM Subject Classification Applied computing → Chemistry, Theory of computation → Graph algorithms analysis, Theory of computation → Data structures Computational Chemistry, Treewidth, Wiener Index Digital Object Identifier 10.4230/LIPIcs.CVIT.2016.23

The Wiener index of a graph G is the sum of distances between all pairs of its vertices. It is a widely used graph property in chemistry, initially introduced to examine the link between boiling points and structural properties of alkanes, which later found notable applications in drug design.

Thus, computing or approximating the Wiener index of molecular graphs, i.e. graphs in which every vertex models an atom of a molecule and every edge models a bond, is of significant interest to the computational chemistry community.

In this work, we build upon the observation that molecular graphs are sparse and tree-like and focus on developing efficient algorithms parameterized by treewidth to approximate the Wiener index.

We present a new randomized approximation algorithm using a combination of tree decompositions and centroid decompositions. Our algorithm approximates the Wiener index within any desired multiplicative factor

where n is the number of vertices of the graph and k is the treewidth. This time bound is almost-linear in n.

Finally, we provide experimental results over standard benchmark molecules from PubChem and the Protein Data Bank, showcasing the applicability and scalability of our approach on real-world chemical graphs and comparing it with previous methods.

Introduction

Motivation. The Wiener index of a graph G is the sum of the distances between all pairs of vertices in G. Besides being a natural problem to compute, it is also a well-studied graph invariant with applications in computational chemistry and biology. Indeed, it is one of computational chemistry's oldest and most important topological indices [START_REF] Trinajstic | Chemical graph theory[END_REF].

History. In chemistry, the Wiener index was first considered by Harry Wiener in [START_REF] Wiener | Structural determination of paraffin boiling points[END_REF].

It was initially studied to establish connections between alkanes' boiling points and the underlying graphs' structural properties. This study later motivated the development of other topological indices in computational chemistry. Further development of QSAR (Quantitative Structure-Activity Relationship) and QSPR (Quantitative Structure-Property Relationship) models led to the discovery of positive correlations of even more chemical and physical properties to the Wiener index [START_REF] Leszczynski | Handbook of computational chemistry[END_REF][START_REF] Trinajstic | Chemical graph theory[END_REF][START_REF] Wagner | Introduction to chemical graph theory[END_REF][START_REF] Xue | Molecular descriptors in chemoinformatics, computational combinatorial chemistry, and virtual screening[END_REF]. Due to its simplicity and usefulness, the Wiener index was also studied by computer scientists and mathematicians [START_REF] Roger C Entringer | Distance in graphs[END_REF][START_REF] Šoltés | Transmission in graphs: a bound and vertex removing[END_REF]. The use

23:2

Faster Treewidth-based Approximations for Wiener Index of neural networks in chemical graph theory has led to a renewed interest in topological indices and their application in molecular mining, toxicity detection, and computer-aided drug discovery. Several studies have been conducted on this topic, such as [START_REF] Bonchev | Chemical graph theory: introduction and fundamentals[END_REF][START_REF] Alexander G Dossetter | Matched molecular pair analysis in drug discovery[END_REF][START_REF] Estrada | Recent advances on the role of topological indices in drug discovery research[END_REF][START_REF] Helma | Predictive toxicology[END_REF][START_REF] Xu | Chemoinformatics and drug discovery[END_REF].

Given the significance of the Wiener index for chemists and the abundance of large molecules, it is imperative to develop faster algorithms for computing it. Indeed, there are many previous works in this direction [START_REF] Cabello | Algorithms for graphs of bounded treewidth via orthogonal range searching[END_REF][START_REF] Chepoi | The wiener index and the szeged index of benzenoid systems in linear time[END_REF][START_REF] Dobrynin | Wiener index of hexagonal systems[END_REF][START_REF] Goldreich | Approximating average parameters of graphs[END_REF][START_REF] Mohar | How to compute the wiener index of a graph[END_REF].

Parameterized Algorithms. Parameterized algorithms aim to tackle computationally intractable problems and identify subsets of instances that can be solved efficiently [START_REF] Cygan | Parameterized algorithms[END_REF]. In parameterized complexity, we consider an additional parameter k along with the input size n for measuring the runtime. This is in contrast to classical complexity theory, which only considers the input size of the problem. Many parameterized algorithms focus on NP-hard problems and provide runtime bounds that depend polynomially on the size of the problem but have non-polynomial dependence on the parameter k. If we know that k is small in real-world instances, this leads to solutions that are effectively polynomial-time, i.e. they take polynomial time on all the real-world instances where this parameter is small. Fixed-Parameter Tractable (FPT). Given an input of size n and a parameter k, an algorithm with a running time of O(f (k) ⋅ n c ), for some constant c and computable function f , is called Fixed-Parameter Tractable (FPT) [START_REF] Cygan | Parameterized algorithms[END_REF]. The intuition is the same as above. If the parameter k is small in all real-world instances of the problem, then the algorithm would in practice have a polynomial runtime. Crucially, the degree c of this polynomial does not depend on either k or n.

Treewidth. Treewidth is one of the most important structural parameters of graphs and has been extensively studied in combinatorics and graph theory. Intuitively speaking, it measures the tree-likeness of a graph [START_REF] Hans | A tourist guide through treewidth[END_REF]. Trees and forests have a treewidth of 1 and cliques on n vertices have treewidth n -1. The main advantage of treewidth in algorithm design arises when we are designing parameterized algorithms for NP-hard problems by considering it as the parameter of the problem. Many families of commonly-studied graphs, such as trees, cacti, series-parallel graphs, outer-planar graphs, and control-flow graphs of structured programs, have bounded treewidth [START_REF] Hans | Dynamic programming on graphs with bounded treewidth[END_REF][START_REF] Hans | A tourist guide through treewidth[END_REF][START_REF] Cygan | Parameterized algorithms[END_REF]. This allows efficient dynamic programming techniques using the tree decomposition of the graph [START_REF] Hans | Dynamic programming on graphs with bounded treewidth[END_REF]. See Section 2 for a formal definition.

Treewidth of Molecules. Extending this idea, computational chemists and biologists have also explored the treewidth of various important classes of molecules [START_REF] Yamaguchi | Graph complexity of chemical compounds in biological pathways[END_REF][START_REF] Yamaguchi | Chemical compound complexity in biological pathways[END_REF]. In our experimental results (Section 4), we observe that a significant majority of molecules in the PubChem repository [START_REF]Pubchem database[END_REF] have a treewidth of at most 10. Even large proteins from the Protein Data Bank [START_REF] Rcsb | Protein data bank[END_REF] are observed to have a treewidth of at most 5. Since a significant fraction of molecules have bounded treewidth, exploring and designing treewidth-based parameterized algorithms for computational problems in chemistry and biology is a natural step. In fact, the same has been done in several works in the literature [START_REF] Akutsu | Comparison and enumeration of chemical graphs[END_REF][START_REF] Cabello | Algorithms for graphs of bounded treewidth via orthogonal range searching[END_REF][START_REF] Conrado | Parameterized algorithms for topological indices in chemistry[END_REF][START_REF] Wan | Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth[END_REF][START_REF] Yamaguchi | Finding the maximum common subgraph of a partial k-tree and a graph with a polynomially bounded number of spanning trees[END_REF]. We extend this line of research by presenting significantly faster treewidth-based approaches for approximating the Wiener index.

Our Contribution. In this paper, we introduce a novel randomized algorithm that approximates the Wiener index of a graph using its tree decomposition. The unique aspect of our algorithm is the incorporation of tree and centroid decompositions. This idea significantly enhances efficiency in answering distance queries within the graph. This is then plugged directly into an established randomized algorithm to approximate the Wiener index, obtaining the same approximation guarantees by an asymptotically faster method. Both theoretical analysis and experimental results demonstrate that our algorithm ) Exact [START_REF] Robert | Algorithm 97: shortest path[END_REF] Orthogonal Range Searching

O(n ⋅ log k-1 n) Exact Parameterized [7] Treewidth-based Dynamic Programming O(n 2 ⋅ k 2 ) Exact Parameterized [8] BFS O(n 2 ⋅ k)
Exact Parameterized [START_REF] Edward | The shortest path through a maze[END_REF][START_REF] Zuse | Der plankalkül[END_REF] Classical Approximation O(n 5 2 2 )

Randomized Approximation [START_REF] Goldreich | Approximating average parameters of graphs[END_REF] Our Algorithm

O(n ⋅ log n ⋅ k 3 + √ n ⋅ k 2 ) Parameterized Randomized Approximation Sec. 3
outperforms current methods in calculating the Wiener index for molecular graphs, which are commonly encountered in computational chemistry and biology.

Comparison with Previous Results. Table 1 compares the runtime complexity of our algorithm with previous methods. Here, n is the number of vertices in the graph, k is the treewidth, and is the error in the approximation, i.e. we are reporting the runtime for a (1 + )-approximation of the Wiener index. We refer to Section 4 for a detailed experimental evaluation of our algorithm on datasets from PubChem [START_REF]Pubchem database[END_REF] and the Protein Data Bank [START_REF] Rcsb | Protein data bank[END_REF].

The most classical approach to compute the Wiener index is simply performing an all-pairs shortest path computation using Floyd-Warshall and then summing up the distances. This will lead to a time complexity of O(n 3 ). In [START_REF] Cabello | Algorithms for graphs of bounded treewidth via orthogonal range searching[END_REF], the authors provided the first parameterized algorithm for the Wiener index based on treewidth. Their algorithm is a divide-and-conquer method based on orthogonal range searching and repeatedly finds small cuts using the tree decomposition. They achieve a runtime bound of O(n ⋅ log k-1 n). Note that this is not FPT. In [START_REF] Chaudhuri | Shortest paths in digraphs of small treewidth. part i: Sequential algorithms[END_REF], an FPT algorithm was provided based on dynamic programming on the tree decomposition. This algorithm has a quadratic dependence on n. For unweighted graphs, given that a graph with treewidth k has O(n ⋅ k) vertices, running a BFS from each vertex would lead to a total runtime of O(n 2 ⋅ k). Finally, [START_REF] Goldreich | Approximating average parameters of graphs[END_REF] provides an algorithm on general graphs, not using any parameters, that approximates the average pairwise distance within a factor of (1 + ) with a probability of at least 2 3 by taking a random sample of the distances between pairs of vertices. Note that the Wiener index is n 2 times the average distance. Thus, this algorithm is directly applicable to our setting, as well. Our algorithm builds upon the classical approximation of [START_REF] Goldreich | Approximating average parameters of graphs[END_REF] and uses a tree decomposition and a centroid decomposition to speed up the sampling.

Preliminaries

In this section, we introduce the Wiener index and define some basic concepts of parameterized complexity. We refer to [START_REF] Cygan | Parameterized algorithms[END_REF] for more details. This is followed by a short presentation of the classical approximation algorithm of [START_REF] Goldreich | Approximating average parameters of graphs[END_REF], which forms the basis of our approach.

Wiener Index [START_REF] Wiener | Structural determination of paraffin boiling points[END_REF]. The Wiener Index of an undirected graph G = (V, E) is defined as the all-pairs sum of distances among vertices of the graph. Formally, Remark 1. In this work we assume that our graphs are connected, unweighted, and undirected. In the context of molecular graphs, all types of covalent bonds-be they single, double, or triple-are represented as a single undirected edge in the corresponding graph.

W (G) ∶= ∑ u,v∈V d(u, v).
For a disconnected graph, the Wiener index is simply +∞. However, in some applications, the Wiener index of a disconnected graph is defined as the sum of the Wiener indices of its connected components. In such cases, each connected component can be processed separately.

Tree Decomposition (TD) [START_REF] Halin | S-functions for graphs[END_REF][START_REF] Robertson | Graph minors. iii. planar tree-width[END_REF][START_REF] Robertson | Graph minors. ii. algorithmic aspects of tree-width[END_REF]. A tree decomposition of a given graph

G = (V, E G )
is a tree T = (B, E T ) satisfying the following conditions:

Every node b ∈ B of T , which is called a bag, contains a subset of vertices V b ⊆ V .
The bags cover the entire vertex set V of G, i.e. ⋃ b∈B V b = V. In other words, every vertex appears in at least one bag.

For every edge in the original graph G, there exists a bag that contains both endpoints of the edge. More formally, for every e = {u,

v} ∈ E G , there is a bag b ∈ B, s.t. u, v ∈ V b .
Every vertex v ∈ V appears in a connected subtree of T , meaning that the set

B v = {b ∈ B v ∈ V b } forms a connected subgraph of T .
Remark 2. An equivalent statement of the last condition above is that for every three bags

b 1 , b 2 , b 3 ∈ B, if b 3 is on the unique path from b 1 to b 2 in T , then V b1 ∩ V b2 ⊆ V b3 .
Treewidth [START_REF] Robertson | Graph minors. iii. planar tree-width[END_REF]. The width of a tree decomposition T is defined as

w(T ) ∶= max b∈B V b -1,
i.e. the size of the largest bag minus one. Furthermore, the treewidth of the graph G, denoted as tw(G), is defined as the minimum width amongst all possible tree decompositions of G.

Intuitively speaking, treewidth measures the structural likeness of a graph to a tree.

Specifically, the smaller the treewidth of a graph, the more tree-like it appears, in the sense that a graph of treewidth k can be decomposed into small parts (bags), each of size at most k + 1, which are connected to each other in a tree-like manner T . Figure 1 showcases an illustration containing two distinct tree decompositions of a graph G, each having a different width. Since only forests have treewidth of 1, the tree decomposition on the right is optimal, and tw(G Treewidth is a parameter indicating graph sparsity, providing an upper bound on the number of edges. Specifically, in a graph with n vertices and treewidth k, the number of edges is O(n ⋅ k). More precisely, the number of edges is less than or equal to n ⋅ k -k ⋅ (k + 1 2) [START_REF] Nešetřil | Structural properties of sparse graphs[END_REF].

) = 2. A B C D E F G - A,B B,C,D,F C,E,F D,F,G A B C D E F G - A,B B,C,D C,D,F C,E,F D,F,G
Additionally, we have the following ubiquitous lemma:

Lemma 3 (Cut Lemma [START_REF] Cygan | Parameterized algorithms[END_REF]). Let T = (B, E T ) be a tree decomposition of G = (V, E G ).

u to v in G will intersect V b . Additionally, if e = {b 1 , b 2 } ∈ E T is an edge on the unique path from b u to b v in T, then any path from u to v in G will intersect V b1 ∩ V b2 .
Computing Tree Decompositions. It is well-known that the treewidth of a graph, as well as an optimal tree decomposition with O(n) bags, can be computed by a linear-time FPT algorithm (parameterized by the treewidth itself) [START_REF] Hans | A linear-time algorithm for finding tree-decompositions of small treewidth[END_REF]. Additionally, there are many well-optimized tools for this task. Thus, in the sequel, we assume without loss of generality that an optimal tree decomposition of our graph is given as a part of the input.

Centroid [START_REF] Jordan | Sur les assemblages de lignes[END_REF]. Consider a tree T = (V T , E T ) with n vertices. We define a centroid node of T as a node whose removal breaks the tree down into several subtrees such that no resulting subtree has a size greater than n 2. In other words, a centroid is a 1 2 separator of T . It is well-known that every tree has at least one centroid node, which can be obtained in linear time by dynamic programming.

Centroid Decomposition (CD) [START_REF] Gerth | The complexity of constructing evolutionary trees using experiments[END_REF][START_REF] Della Giustina | A new linear-time algorithm for centroid decomposition[END_REF]. A centroid decomposition of T is another tree T ′ on the same set of vertices as T , recursively defined as follows:

When V T = 1, we simply have T ′ = T .

For a more complex tree, we first identify a centroid node r of T , then position this node as the root of T ′ .

Once we have selected a centroid node r and removed it from T , we end up separating the original tree into several connected subtrees. Let us denote these as T 1 , T 2 , . . . , T m .

For each subtree T i , we find a centroid decomposition T ′ i with a root r i . We make each r i a child of r. Computing Centroid Decompositions. Given a tree T with n vertices, there are a variety of algorithms in the literature that compute a centroid decomposition

T ′ of T in O(n).
Examples include [START_REF] Gerth | The complexity of constructing evolutionary trees using experiments[END_REF][START_REF] Della Giustina | A new linear-time algorithm for centroid decomposition[END_REF].

Lowest Common Ancestor Queries. Consider a rooted tree T with n vertices. Suppose we have q offline queries, each providing two vertices u, v ∈ T and asking for their lowest common ancestor. The classical algorithm of Gabow and Tarjan [START_REF] Gabow | A linear-time algorithm for a special case of disjoint set union[END_REF] solves this problem and answers all queries in O(n + q). Approximation Algorithm of [START_REF] Goldreich | Approximating average parameters of graphs[END_REF]. The work [START_REF] Goldreich | Approximating average parameters of graphs[END_REF] provides an elegant and simple approximation algorithm for the average distance d(G) between pairs of vertices. Since the Wiener index is simply n 2 ⋅ d(G), the same algorithm can be reused for our problem. Given a graph G and an error bound as the input, the algorithm in [START_REF] Goldreich | Approximating average parameters of graphs[END_REF] works as follows:

1. Uniformly select Θ( √ n 2 ) pairs of vertices.

2.

Find the distance between each selected pair of vertices.

3.

Output the average of the computed distances.

Surprisingly, this algorithm provides a (1 + )-approximation of d(G) with probability 2 3.

Theorem 5 ([21], Theorem 5.1). Given G and as input, the algorithm above outputs a

(1 + )-approximation of d(G) with probability at least 2 3.

As a direct corollary, a (1 + )-approximation of the Wiener index can be computed in the same time complexity by simply multiplying the result of this algorithm by n 2 .

Complexity Analysis. For general graphs, each distance query can take O(n 2 ) time.

Thus, the total runtime of the algorithm above is O(n 5 2 2 ). However, if the underlying graph G is guaranteed to have small treewidth k, then it can have at most O(n ⋅ k) vertices.

Thus, each distance query can be answered in O(n ⋅ k) by a BFS. This reduces the runtime

to O(n 3 2 ⋅ k 2 ).
In this work, we build upon this simple randomized algorithm and use the treewidth to obtain a faster algorithm for distance queries. This allows us to reduce the runtime dependence on n to almost-linear.

Our Algorithm

In this section, we present our treewidth-based algorithm. Our algorithm follows the same steps as the approximation algorithm of [START_REF] Goldreich | Approximating average parameters of graphs[END_REF], except that we exploit the tree decomposition to perform distance queries faster. Our main novel idea is to look not only at a tree decomposition of the underlying graph but also at a centroid decomposition of this tree decomposition. Thus, our algorithm exploits the desirable properties of both types of decomposition, as formalized by the lemma below: Based on the lemma above, if we precompute the distances from each vertex appearing in a bag l of the centroid decomposition T ′ to the vertices appearing in descendants of l in T ′ , then we can answer distance queries in O(k). In other words, to find the distance from u to v, we first find two bags b u and b v containing them, then compute l = lca(b u , b v ). Now, we know that every path from u to v has to go through l, thus

d G (u, v) = min w∈V l (d G (u, w) + d G (w, v)) .
Here, d G denotes the distance in graph G.

Our Algorithm for Wiener Index. Based on the discussion above, given > 0, a graph Step 4 (Sampling). Uniformly select Θ( √ n 2 ) pairs of vertices of G as in the algorithm of [START_REF] Goldreich | Approximating average parameters of graphs[END_REF].

G = (V, E G )
Step 5 (Distance Queries). For each pair of vertices (u, v) ∈ V 2 selected in the previous step, compute d G (u, v).

Step 6 (Output). Output the average of all the distances obtained in the previous step.

For

Step 1, we can rely on previous algorithms that compute centroid decompositions, such as [START_REF] Gerth | The complexity of constructing evolutionary trees using experiments[END_REF][START_REF] Della Giustina | A new linear-time algorithm for centroid decomposition[END_REF]. Steps 4 and 6 are straightforward. We now provide details of Steps 2, 3, and 5, followed by correctness proofs and runtime analyses.

Details of

Step 2. This step is inspired by [START_REF] Chaudhuri | Shortest paths in digraphs of small treewidth. part i: Sequential algorithms[END_REF]. Given the graph G = (V, E G ) and its tree decomposition T = (B, E T ), our goal is to create shortcut edges between any pair of vertices that appear in the same bag. We provide a recursive procedure as follows:

i. Choose a leaf bag of the tree decomposition T.

ii. Perform an all-pairs shortest-path algorithm, such as Floyd-Warshall, in G[V ], i.e. only on the vertices and edges in . If a path of length d is found between u and v, add a direct {u, v} edge with weight d to G.

iii. Let T * = T -and

G * = G -{v ∈ V ∃ b ∈ B b ≠ ∧ v ∈ V b }.
In other words, we are removing the leaf bag from our tree decomposition and also removing any vertex that appeared only in this bag from the graph G.

iv. Run the algorithm recursively on (G * , T * ). This causes more shortcut edges to be added in G.

v. Repeat

Step ii, i.e. perform another all-pairs shortest-path in G[V ] and add the resulting shortcut edges to G.

G b = G ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ ⋃ b ′ ∈T ′ b V b ′ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ . 23:9 1,2,3 2,3,7 3,7,8 3,8,9 7,12 1,3,6 6, 10 3,5,6 3,4,5 4,11
(a) We choose the leaf bag = {3, 8, 9}.

(c) Bag is removed from T to form T * . For every vertex v ∈ V b that appears in the bag b, our algorithm runs a shortest-path computation, such as Dijkstra's algorithm [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF], from b in the graph G b and finds its distances to all other vertices of G b , adding the corresponding shortcut edges. See Figure 6 for an example.

1, Dijkstras * over this graph, one for each vertex in the bag b. Thus, our total runtime is

∑ b∈B O(δ b ⋅ k 3 ) = ∑ b∈B O(α b ⋅ k 3 ) = O(n ⋅ log n ⋅ k 3 ).
The latter equality is because every vertex has O(log n) ancestors. By Lemma 4, every path from u to v has to intersect V l . Thus, we compute

d G (u, v) = min w∈V l (d G (u, w) + d G (w, v)) .
Note that since l is an ancestor of both b u and b v , we have the distances needed on the RHS as weights of direct shortcut edges. This is illustrated in Figure 7 Proof. Correctness of the approximation ratio and success probability follows from Theorem 5 since our algorithm is the same as [START_REF] Goldreich | Approximating average parameters of graphs[END_REF] except for how we answer distance queries.

Step 1 takes O(n) using well-known algorithms such as [START_REF] Gerth | The complexity of constructing evolutionary trees using experiments[END_REF][START_REF] Della Giustina | A new linear-time algorithm for centroid decomposition[END_REF].

Step 2 takes O(n ⋅ k 3 ) based on Lemma 7.

Step

Experimental Results

In this section, we present our experimental results, comparing the runtimes of our algorithm with previous approaches. We implemented the main algorithms in C++ and provided the same inputs, i.e. graph G, tree decomposition T and = 0.1 to all of them. To obtain this input, we first used pysmiles [START_REF] Peter C Kroon | pysmiles: A python library for parsing smiles strings[END_REF], RDKit [START_REF] Landrum | Rdkit: Open-source cheminformatics[END_REF] and NetworkX [START_REF] Hagberg | Exploring network structure, dynamics, and function using networkx[END_REF] for preprocessing molecular data and turning them into graphs. We also used FlowCutter [START_REF] Strasser | Flowcutter: Software for computing flow-based balanced graph cuts[END_REF] to compute tree decompositions. All our experiments were conducted on an Intel Core i5 (2.3 GHz, Quad-core) Machine with 8 GB of RAM running MacOS. We enforced a time limit of 1000 seconds per instance.

Benchmarks. We used the following datasets for our experiments: (i) PubChem [START_REF]Pubchem database[END_REF] and

(ii) Protein Data Bank (PDB). Specifically, we report results on 100 randomly-selected protein molecules from the PDB database and 1, 311, 229 molecules from PubChem.

PDB. The Protein Data Bank (PDB) [START_REF] Rcsb | Protein data bank[END_REF] is an extensive repository of three-dimensional structural data for large biological molecules, including proteins, DNA and RNA. We randomly selected 100 protein molecules from this database. Table 2 shows some statistics about these molecules. We observed that even the large molecules in this dataset have small treewidth. Treewidth of the Molecules. As mentioned in Tables 2 and3, we observed that the chemical compounds in both benchmark suites exhibit bounded treewidth. Results. Figure 9 compares the performance of our algorithm and previous methods over the PDB dataset, whereas Table 4 provides the same comparison for PubChem. Our approach's better asymptotic complexity leads to significant gains in efficiency when considering the large graphs in PDB. However, no benefit is observed over the PubChem molecules, since they are all small and every algorithm can handle them in under 1 ms.

Conclusion

In this work, we considered the problem of computing the Wiener index of a graph with n vertices and treewidth k. We provided a novel algorithm using a combination of tree decompositions and centroid decompositions, which achieves an almost-linear FPT runtime of O(n ⋅ log n ⋅ k 3 + √ n ⋅ k 2 ) and outputs a (1 + )-approximation of the Wiener index with probability at least 2 3. To the best of our knowledge, this is the first sub-quadratic time FPT algorithm for this problem. We also showed that many real-world molecular graphs have small treewidth and thus our algorithm is applicable in practice.

6

S E A 2 0 2 4 23: 4 Faster

 44 Treewidth-based Approximations for Wiener IndexAdditionally, we define the average distance between pairs of vertices in G as d(G) ∶= W (G) n 2 .

Figure 1 A

 1 Figure 1 A Graph G and Two Tree Decompositions of G of Width 3 (left) and 2 (right).

5 b

 5 Consider two vertices u, v ∈ V and two arbitrary bags b u , b v ∈ B such that u ∈ b u and v ∈ b v . If G.K. Conrado et al. 23:∈ B is a bag on the unique path from b u to b v in T, then any path from

Figure 2 A

 2 Figure 2 A Graph G and the Steps of Building its Centroid Decomposition. Each step highlights the centroid vertex of each of the current components of the graph.

Figure 3 Figure 2 3 .Lemma 4 (

 3234 Figure 3The Resulting Centroid Decomposition of G.

Lemma 6 .

 6 Let G = (V, E G ) be a graph, T = (B, E T ) a tree decomposition of G and T ′ = (B, E T ′ ) a centroid decomposition of T. Consider two vertices u, v ∈ V and arbitrary bags b u , b v ∈ B such that u ∈ b u and v ∈ b v . Let l be the lowest common ancestor of b u and b v in the centroid decomposition T ′ . Any path that goes from u to v in G intersects V l . Proof. Consider the path π T from b u to b v in the tree decomposition T. By Lemma 4, we have l ∈ π T . By Lemma 3, any bag in π T intersects every path from u to v in G. This is illustrated in Figure 4.

  A Graph G and Two Vertices u = 1 and v = 11. A Tree Decomposition T of G. We choose b u = {1, 3, 6} and b v = {4, 11}.

  A Centroid Decomposition T ′ of T. The lowest common ancestor of b u and b v in T ′ is l = {3, 5, 6}. The path from b u to b v in T goes through l.

  Every path from u to v in G must intersect V l . Every path from u to v in G must intersect V l .

Figure 4

 4 Figure 4 An Illustration of Lemma 6.

Step 1 (Step 2 (

 12 and a tree decomposition T = (B, E T ) of G with width k, our algorithm turns G into a weighted graph and takes the following steps: Centroid Decomposition). Compute a centroid decomposition T ′ of the tree decomposition T. Local Precomputation). For every two vertices u, v ∈ V, if there is a bag b ∈ B that contains both of them, i.e. u, v ∈ V b , then compute the distance d G (u, v) and add a direct edge with weight d G (u, v) between u and v. Step 3 (Ancestor-Descendant Precomputation). Let b 1 , b 2 ∈ B be two bags such that b 1 is an ancestor of b 2 in the centroid decomposition T ′ . For every u ∈ V b1 and v ∈ V b2 , compute the distance d G (u, v) and add a direct edge with weight d G (u, v) between u and v.

Figure 5 Lemma 7 (Remark 8 .

 578 Figure 5 provides an example of this step. Lemma 7 (Proof in Appendix B). The procedure above runs in time O(n ⋅ k 3 ). After its execution, T is still a valid tree decomposition of G, and for every pair of vertices u, v ∈ V, if there exists a bag b ∈ B containing both of them, then there is a direct (shortcut) edge from u to v with weight d G (u, v). Remark 8. Throughout our algorithm, we always keep at most one edge, i.e. the edge with minimum weight, between every pair {u, v} of vertices. Details of Step 3. In this step, we process our centroid decomposition T ′ in a bottom-up manner. For every bag b ∈ B, we consider the subtree T ′ b of the centroid decomposition T ′ , consisting of b and all of its descendants in T ′ . Let G b be the induced subgraph of G that contains all the vertices in T ′ b , i.e.

  Shortest paths are found within G[V ]. Dashed lines represent newly added edges.1,

  G * is formed by removing vertex 9 from G, since it only appears in bag in T . After recursively running the algorithm on (G * , T * ), new edges are added to G.

  Shortest paths are again found within G[V ] and any new edges found are added to G. In this example, no new edges were found.

Figure 5

 5 Figure 5 An Example of Step 2 on the Graph and Decomposition of Figure 4.

  Let b = {3, 7, 8}. The subtree T ′ b of T ′ is highlighted.

  The figure above shows G b . We now run Dijkstra's algorithm from vertices in {3, 7, 8}.

  After running Dijkstra's algorithm in G b , we add the new shortcut edges picutred above to G.

Figure 6 Lemma 9 .

 69 Figure 6 An Example of Step 3 on the Graph and Decompositions of Figure 4.

For

  the second part, consider a shortest path π from u to v in G. Let π T be the path from b 1 to b 2 in the tree decomposition T. By Lemma 3, π intersects the vertices of every bag b in π T . Without loss of generality, we can assume that π stays in these bags, i.e. it only visits vertices in ⋃ b∈π T V b . Note that if π leaves π T , then it has to reenter it, but the exit and entry vertices are in the same bag and, by Lemma 7, there is already a shortcut edge between them. Additionally, since b 1 is an ancestor of b 2 in the centroid decomposition T ′ , there was a point in the construction of T ′ when b 1 was chosen as the centroid of a connected component containing b 2 . Thus, all the bags in π T were also in the same connected component. Hence, every b is a descendant of b 1 . Therefore, the entire path π is included in G b and the Dijkstra from u finds the shortest path to v and adds the corresponding shortcut edge. Details of Step 5. Suppose our goal is to compute d G (u, v). We first pick two bags b u and b v such that u ∈ b u and v ∈ b v . We then find the lowest common ancestor l = lca(b u , b v ).

  Let u = 5 and v = 7. We select b u = {3, 4, 5} and b v = {3, 7, 8}. Their lowest common ancestor l in T ′ is {1, 2, 3}, thus any shortest path from 5 to 7 has to go through vertices 1, 2, or 3.

  Since l is an ancestor of b u and b v , the vertices u and v have shortcut edges to every vertex in l.

Figure 7 4 . 10 .√ n 2 )

 74102 Figure 7 An Example of Step 5 on the Graph and Decompositions of Figure 4. Lemma 10. The procedure above returns the correct distances in O(n + k ⋅ √ n 2 ). Proof. Correctness is already argued above. Since the centroid decomposition T ′ has O(n) bags, preprocessing and answering offline lowest common ancestor queries takes O(n + √ n 2 ) [20]. For each of the √ n 2 queries generated in Step 4, we should compute the minimum of O(k) values since V l ≤ k + 1.

Finally, the following is our main theorem in this work: Theorem 11 .

 11 Given an > 0, an undirected unweighted graph G = (V, E G ) with n vertices and a tree decomposition T = (B, E T ) of G with O(n) bags and width k, our algorithm runs in time O(n ⋅ log n ⋅ k 3 + √ n ⋅ k 2 ) and produces a (1 + )-approximation of the Wiener index W (G) with probability at least 2 3.

Figure 8

 8 Figure 8 Treewidth Distribution in Our Benchmarks

Table 1

 1 Comparison of Different Algorithms for Computing the Wiener Index. Here, n denotes the number of vertices, k denotes the treewidth, and represents the error of approximation.

	Algorithm	Time Complexity	Type	Ref.
	Floyd-Warshall	O(n 3

  3 takes O(n ⋅ log n ⋅ k 3 ) as shown in Lemma 9. Step 4 simply takes O(

	√ n 2 ) time as per Lemma 10. n 2 ) samples n 2 ) time. Summing these up leads to the desired asymptotic from the uniform distribution and Step 5 takes O(n + k ⋅ √ Finally, Step 6 takes O( √
	time complexity.

Table 2

 2 Statistics of the PDB Benchmarks

		Minimum Maximum Average
	Number of Vertices	682	80652	9027
	Number of Edges	743	82055	9240
	Treewidth	2	5	2.95
	PubChem. PubChem [19] is an open chemistry database of the National Institutes of Health
	(NIH). It includes information on chemical structures, identifiers, chemical and physical
	properties, and biological activities of small molecules. As benchmarks, we took the following
	datasets from PubChem: Common Chemistry CAS, Nature Catalysis, Wikipedia, Nature
	Communications, Wiley, Springer Nature, Nature Chemistry, Nature Portfolio Journals,
	Springer Materials, Drug and Medication, Nature Synthesis, Nature Chemical Biology,

KEGG, DrugBank. Collectively, these datasets contained 1, 311, 229 molecules at the time of writing. See Table

3

for the statistics over this set of benchmarks.

S E A 2

0 2 4 23:12 Faster Treewidth-based Approximations for Wiener Index

Table 3

 3 Statistics of the PubChem Benchmarks

	Metric	Minimum Maximum Average
	Number of Vertices	2	568	21
	Number of Edges	1	643	22
	Treewidth	1	16	1.8

Table 4

 4 Runtime Comparison of the Algorithms of Table 1 over PubChem Benchmarks. All times are in milliseconds. Runtime Comparison of the Algorithms of Table 1 over PDB Benchmarks. Each dot corresponds to one benchmark molecule.

	Algorithm	Maximum Minimum Average
	Our Algorithm	1.425	0.187	0.296454
	Approximation Algorithm	1.283	0.203	0.297342
	DP on Tree Decomposition	1.256	0.192	0.296152
	Floyd-Warshall	2.261	0.199	0.288638
	Orthogonal Range Searching	1.121	0.199	0.292404
	BFS	1.097	0.205	0.290523

TO

Figure 9

Acknowledgments

The research was partially supported by the Hong Kong Research Grants Council ECS Project Number 26208122.

A

Proof of Lemma 4

Proof. We prove this lemma through induction on the size n of the tree. If n is at most 3, the lemma holds trivially. Now assume that the lemma holds for all trees with a size less than n. Let us consider a general tree of size n. In the first step, we identify a centroid node of T , denoted as c. The node c fragments T into several connected components. If any arbitrary vertices u, v ∈ V T exist in the same connected component T i , then in the corresponding centroid decomposition T ′ , they will appear in T ′ i as per the definition of centroid decomposition. According to the inductive hypothesis, their path must cross their lowest common ancestor in T ′ i . In case they belong to different connected components, say T ′ i and T ′ j , any path originating from T ′ i and terminating at T ′ j must traverse the node c. This is because c separates T i and T j . In this scenario, their lowest common ancestor would be the root c, as the remaining nodes on the path from u to v are either in T i or T j and, hence, cannot serve as the common ancestor.

B Proof of Lemma 7

(a) When u and v appear in G * , a shortcut edge will be calculated during the recursive call on G * .

, its path to u must contain a vertex w that is in the same bag as u and v and that also appears in G * . A shortcut edge from u to w will be added during the processing of G * and thus the path from u to v can be calculated in Step v. Proof. We run the Floyd-Warshall algorithm twice on each bag of the tree decomposition, once in Step ii and once in v. Since each bag has k + 1 vertices and the tree decomposition has O(n) bags, the total runtime is O(n ⋅ k 3 ). The procedure above adds new shortcut edges only between pairs of vertices that were already in the same bag, thus the tree decomposition remains valid.

We prove the last property by induction on B . If B = 1, then the first Floyd-Warshall in

Step ii adds all the necessary shortcut edges. Otherwise, let u, v ∈ V be two vertices that appear in the leaf bag and let p ∈ B be the parent of in T. If there is a path between u and v that is entirely within V , then Step ii adds a shortcut edge summarizing this path.