2024

A Faster FPT Algorithm for Vertex Cover on Subcubic Graphs: A Randomized Automated Approach
A Faster FPT Algorithm for Vertex Cover on Subcubic Graphs: A Randomized Automated Approach

Katie Clinch, Serge Gaspers, Zixu He, Simon Mackenzie, Tiankuang Zhang

Submitted to STACS 2025 Spotlight

In this paper, we present a novel algorithm for solving the Vertex Cover problem on subcubic graphs in \(O(1.1313^k)\), beating the previous best running time of \(O(1.1442^k)\) due to Harris and Narayanaswamy (2022). We achieve this by combining two contributions of independent interest: 1) developing a new framework for the automated design of branching algorithms based on the idea of case analysis of local structures, and 2) introducing an extension of Measure & Conquer to randomized branching algorithms.

A Faster FPT Algorithm for Vertex Cover on Subcubic Graphs: A Randomized Automated Approach
A Faster FPT Algorithm for Vertex Cover on Subcubic Graphs: A Randomized Automated Approach

Katie Clinch, Serge Gaspers, Zixu He, Simon Mackenzie, Tiankuang Zhang

Submitted to STACS 2025 Spotlight

In this paper, we present a novel algorithm for solving the Vertex Cover problem on subcubic graphs in \(O(1.1313^k)\), beating the previous best running time of \(O(1.1442^k)\) due to Harris and Narayanaswamy (2022). We achieve this by combining two contributions of independent interest: 1) developing a new framework for the automated design of branching algorithms based on the idea of case analysis of local structures, and 2) introducing an extension of Measure & Conquer to randomized branching algorithms.

Fair Railway Network Design
Fair Railway Network Design

Zixu He, Sirin Botan, Jérôme Lang, Abdallah Saffidine, Florian Sikora, Silas Workman

Submitted to AAAI 2025

When designing a public transportation network in a country, one may want to minimise the sum of travel duration of all inhabitants. This corresponds to a purely utilitarian view and does not involve any fairness consideration, as the resulting network will typically benefit the capital city and/or large central cities while leaving some peripheral cities behind. On the other hand, a more egalitarian view will allow some people to travel between peripheral cities without having to go through a central city. We define a model, propose algorithms for computing solution networks, and report on experiments based on real data.

[arXiv]

Fair Railway Network Design
Fair Railway Network Design

Zixu He, Sirin Botan, Jérôme Lang, Abdallah Saffidine, Florian Sikora, Silas Workman

Submitted to AAAI 2025

When designing a public transportation network in a country, one may want to minimise the sum of travel duration of all inhabitants. This corresponds to a purely utilitarian view and does not involve any fairness consideration, as the resulting network will typically benefit the capital city and/or large central cities while leaving some peripheral cities behind. On the other hand, a more egalitarian view will allow some people to travel between peripheral cities without having to go through a central city. We define a model, propose algorithms for computing solution networks, and report on experiments based on real data.

[arXiv]

A Piecewise Approach for the Analysis of Exact Algorithms
A Piecewise Approach for the Analysis of Exact Algorithms

Katie Clinch, Serge Gaspers, Zixu He, Abdallah Saffidine, Tiankuang Zhang

WALCOM 2025 Spotlight

This paper presents piecewise analysis, a new general method that analyzes the running time of branching algorithms. We reanalyze two 17-year-old algorithms from Fomin et al. (2007) that solve 4-Coloring and #3-Coloring and we improve their running time from \(O(1.7272^n)\) to \(O(1.7207^n)\) and from \(O(1.6262^n)\) to \(O(1.6225^n)\) respectively.

[arXiv] [Code]

A Piecewise Approach for the Analysis of Exact Algorithms
A Piecewise Approach for the Analysis of Exact Algorithms

Katie Clinch, Serge Gaspers, Zixu He, Abdallah Saffidine, Tiankuang Zhang

WALCOM 2025 Spotlight

This paper presents piecewise analysis, a new general method that analyzes the running time of branching algorithms. We reanalyze two 17-year-old algorithms from Fomin et al. (2007) that solve 4-Coloring and #3-Coloring and we improve their running time from \(O(1.7272^n)\) to \(O(1.7207^n)\) and from \(O(1.6262^n)\) to \(O(1.6225^n)\) respectively.

[arXiv] [Code]