CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Graph algorithms I
Président: Jakub Gajarský (TU Berlin)

HUNG LE, University of Victoria
Light greedy spanners  [PDF]

We present a framework for analyzing the greedy algorithm that constructs a $(1+\epsilon)$-spanner of graphs. We apply our analysis to show that:

$H$-minor-free graphs have (1+$\epsilon$)-spanners of weight $O_H(\frac{1}{\epsilon^3}\log \frac{1}{\epsilon})w(MST)$. This resolves an open problem of Grigni and Sissokho (SODA'02). A consequence of our result is that there exists an efficient polynomial time approximation scheme (EPTAS) for the Travelling Salesperson Problem (TSP) in $H$-minor-free graphs.

Graphs representing metrics of doubling dimension $d$ have $(1+\epsilon)$-spanners of weight $\epsilon^{-O(d)}w(MST)$, resolving an open problem posed by Gottlieb (FOCS'15). Our result generalizes the result by Narasimhan and Smid who showed that a point set in $d$-dimension Euclidean space has a $(1+\epsilon)$-spanner of weight at most $\epsilon^{-O(d)}w(MST)$. Our proof only uses the packing property of doubling metrics and thus implies a much simpler proof for the same result in Euclidean space.

JIAJIAN LEO LIANG, Simon Fraser University
Algorithmic Analysis for Ridesharing of Personal Vehicles  [PDF]

Given a set of trips in a road-network, where each trip has an individual, a vehicle and some requirements, the ridesharing problem is to select a subset of vehicles to deliver the individuals of all trips to their destinations satisfying the requirements. Minimizing total travel distance of the vehicles and minimizing the number of vehicles are major optimization goals. However, these minimization problems are complex and NP-hard. We study simplified minimization problems in which each trip’s requirements are specified by the source, destination, vehicle capacity, detour distance and preferred path parameters. We give an algorithmic analysis for the simplified minimization problems and explore a boundary between NP-hard and polynomial-time solvable cases. Both minimization problems are polynomial-time solvable if all the following conditions are satisfied: (1) all trips have same destination or same source; (2) no detour is allowed and (3) each trip has one preferred path. Otherwise, they are NP-hard.

KEIVAN HASSANI MONFARED, University of Victoria
Graph Clustering Problems Arising in Neuroscience  [PDF]

One of the common problems in neuroscience is to identify regions of the brain involved in specific tasks. This can be expressed in terms of graph clustering problems. In this talk, we concentrate on two spectral graph theory approaches (namely the hierarchical Fiedler method, and the spectral coordinates method) used in identifying and evaluating such clusterings in the event of brain disorders such as Alzheimer's Disease and Epilepsy.

KATHERINE MOORE, Wake Forest University
Parameter-free data clustering via partitioned local depths  [PDF]

In this talk, we give a combinatorial measure of what it means for a data point to be central to those nearby; and call this the point's local depth. This flexible measure of depth, defined as a discrete probability, gives a new perspective for understanding the relative proximity of points with respect to underlying data. As a result of our concise definition, we obtain a parameter-free clustering algorithm and method for classification. We suggest an answer for what it means to be a cluster and examine the consequences of this new perspective.

OMER WASIM, University of Victoria
Preserving Large Cuts in Fully Dynamic Graphs  [PDF]

Most graphs in the real world are dynamic in the sense that edges are constantly subject to additions and removals. In this work, we study the Maximum Cut problem in the fully dynamic setting which is defined as follows: for an undirected, unweighted graph $G=(V,E)$, maintain a $\frac{1}{2}$ approximate cut efficiently under edge insertions and deletions to $G$-i.e. in time better than that of the best static algorithm algorithm for the problem. We present the first sublinear time algorithms for the dynamic MAX-CUT problem: 1) a deterministic algorithm that takes $O(\Delta)$ worst case time per update to maintain a $\frac{1}{2}$ approximate cut (where $\Delta$ denotes the upper bound on maximum degree), 2) a sublinear in $m$ time algorithm which takes $O(m^{1/2})$ amortized update time. Our ideas rely on partitioning $V$ according to degree and aggregating smaller cuts. All our algorithms are deterministic and no restriction on the adversary is imposed.