Parameterized Algorithms and Complexity Results for Wiener Index and Liquid Democracy

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Parameterized Algorithms and Complexity Results for Wiener Index and
Liquid Democracy"

By

Mr. Pavel HUDEC


Abstract:

Decades of algorithmic research have shown numerous natural problems in 
computer science to be intractable for general input instances. Naturally, the 
question was posed whether the worst-case behavior and hardness results were 
realistic, or whether the real-world instances possess exploitable structure 
for efficiency. In this thesis, we study graph sparsity parameters that 
capture such structure, e.g., the treewidth and vertex cover number of a 
graph.

This thesis follows this line of work in two settings: First, it studies 
computational chemistry, specifically the computation of the Wiener index of a 
chemical molecule. Wiener index is a classical topological index, initially 
defined to analyze the boiling point of alkanes and later found applications 
in drug synthesis. We experimentally show that molecules have a bounded 
treewidth and use this property in designing a faster parameterized 
approximation algorithm for computing the Wiener index of a molecule. We 
further show that our algorithm achieves a significant speed-up in practice. 
We also show treewidth is broadly applicable in computational chemistry, in 
particular in computation of classical topological indices, such as the number 
of Kekulé structures, the Merrifield-Simmons index, and the Hosoya index. 
We provide practical fixed-parameter tractable algorithms for these problems, 
and show that they outperform the state-of-the-art often by orders of 
magnitude. Finally, we design the fastest known algorithm for the Minimum 
Cycle Basis (MCB) problem in graphs of bounded treewidth.

For the second part, we study the problem of computing the success probability 
in Liquid Democracy, a classical and widely-studied form of voting with 
delegation. We prove that the problem is #P-complete in its most general case. 
Moreover, we provide a practical near-cubic algorithm for trees, and extend it 
to an XP algorithm for graphs of bounded treewidth. Independently, we design 
an FPT algorithm for graphs of bounded vertex cover number.


Date:                   Tuesday, 22 September 2026

Time:                   4:00pm - 6:00pm

Venue:                  Room 3494
                        Lifts 25/26

Chairman:               TBC

Committee Members:      Dr. Jiasi SHEN (Supervisor)
                        Dr. Amir GOHARSHADY (Co-supervisor, University of Oxford)
                        Dr. Sunil ARYA
                        Prof. Dimitrios PAPADIAS
                        Dr. Maximilian NITZSCHNER (MATH)
                        Prof. Sandi KLAVŽAR (University of Ljubljana)