Parameterized Algorithms and Complexity Results for Wiener Index and Liquid Democracy

PhD Thesis Proposal Defence


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

by

Mr. Pavel HUDEC


Abstract:

Decades of research have shown numerous natural problems in computer science 
to be intractable for general input instances. Naturally, people started to 
ask whether the worst-case behavior was actually realistic, or whether the 
real-world instances possess special properties captured in smallness of 
structural parameters.

This thesis follows this line of work for two problems. First, it studies the 
computation of the Wiener index of a chemical molecule. Wiener index was 
introduced by Harry Wiener 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 
approximation algorithm for computing the Wiener index of a molecule. We show 
that our algorithm achieves a significant speed-up.

For the second part, we study Liquid Democracy, with the most focus being on 
the problem of computing the success probability of the vote in a 
probabilistic setting. We define the problem and prove that it is #P-complete 
in general. Moreover, we provide an FPT algorithm for graphs of bounded 
vertex cover number and an XP algorithm for graphs of bounded treewidth. We 
also show that the maximization of success probability is an NP-complete 
problem.


Date:                   Tuesday, 25 November 2025

Time:                   10:00am - 12:00noon

Venue:                  Room 5501
                        Lifts 25/26

Committee Members:      Prof. Charles Zhang (Supervisor)
                        Dr. Amir Goharshady (Co-supervisor, Oxford)
                        Prof. Dimitris Papadias (Chairperson)
                        Dr. Sunil Arya