Anil Maheshwari

Anil Maheshwari, Karthik Murali, Michiel Smid

Spanning trees are fundamental for efficient communication in networks. For fault-tolerant communication, it is desirable to have multiple spanning trees to ensure resilience against failures of nodes and edges. To this end, various notions of disjoint or independent spanning trees have been studied, including edge-disjoint, node/edge-independent, and completely independent spanning trees. Alongside these, several Steiner variants have also been investigated, where the trees are required to span a designated subset of vertices called terminals. For instance, the study of edge-disjoint spanning trees has been extended to edge-disjoint Steiner trees; a stronger variant is the problem of internally disjoint Steiner trees, where any two Steiner trees intersect exactly in the terminals. In this paper, we investigate the Steiner analogue of completely independent spanning trees, which we call \emph{completely independent Steiner trees}. A set of Steiner trees is completely independent if, for every pair of terminals $u,v$, the $(u,v)$-paths in all the Steiner trees are internally vertex-disjoint and edge-disjoint. This notion generalizes both completely independent spanning trees and internally disjoint Steiner trees. We provide a systematic study of completely independent Steiner trees from structural, algorithmic, and complexity-theoretic perspectives. In particular, we present several characterisations, connectivity bounds, algorithms, hardness results, and applications to special graph classes such as planar graphs and graphs of bounded treewidth. Along the way, we also introduce a directed variant of completely independent spanning trees via an equivalence with completely independent Steiner trees.

Chaeyoon Chung, Anil Maheshwari, Michiel Smid

Given a set $S$ of $n$ points in the plane, we study the two-line-center problem: finding two lines that minimize the maximum distance from each point in $S$ to its closest line. We present a $(1+\varepsilon)$-approximation algorithm for the two-line-center problem that runs in $O((n/\varepsilon) \log (1/\varepsilon))$ time, which improves the previously best $O(n\log n + ({n}/{\varepsilon^2}) \log ({1}/{\varepsilon}) + (1/\varepsilon^3)\log ({1}/{\varepsilon}))$-time algorithm. We also consider three variants of this problem, in which the orientations of the two lines are restricted: (1) the orientation of one of the two lines is fixed, (2) the orientations of both lines are fixed, and (3) the two lines are required to be parallel. For each of these three variants, we give the first $(1+\varepsilon)$-approximation algorithm that runs in linear time. In particular, for the variant where the orientation of one of the two lines is fixed, we also give an improved exact algorithm that runs in $O(n \log n)$ time and show that it is optimal.

Pegah Kamousi, Sylvain Lazard, Anil Maheshwari et al.

A standard way to approximate the distance between any two vertices $p$ and $q$ on a mesh is to compute, in the associated graph, a shortest path from $p$ to $q$ that goes through one of $k$ sources, which are well-chosen vertices. Precomputing the distance between each of the $k$ sources to all vertices of the graph yields an efficient computation of approximate distances between any two vertices. One standard method for choosing $k$ sources, which has been used extensively and successfully for isometry-invariant surface processing, is the so-called Farthest Point Sampling (FPS), which starts with a random vertex as the first source, and iteratively selects the farthest vertex from the already selected sources. In this paper, we analyze the stretch factor $\mathcal{F}_{FPS}$ of approximate geodesics computed using FPS, which is the maximum, over all pairs of distinct vertices, of their approximated distance over their geodesic distance in the graph. We show that $\mathcal{F}_{FPS}$ can be bounded in terms of the minimal value $\mathcal{F}^*$ of the stretch factor obtained using an optimal placement of $k$ sources as $\mathcal{F}_{FPS}\leq 2 r_e^2 \mathcal{F}^*+ 2 r_e^2 + 8 r_e + 1$, where $r_e$ is the ratio of the lengths of the longest and the shortest edges of the graph. This provides some evidence explaining why farthest point sampling has been used successfully for isometry-invariant shape processing. Furthermore, we show that it is NP-complete to find $k$ sources that minimize the stretch factor.