TL;DR
This paper presents efficient algorithms for computing the Fréchet distance between trees and graphs with bounded tree width. They achieve polynomial time for trees and fixed-parameter tractable (FPT) time for graphs, significantly advancing the computational feasibility of this important shape similarity measure.
What Problem Does This Paper Address?
The Fréchet distance is a powerful metric for comparing the similarity of geometric shapes, often visualized as the minimum leash length required for a person and their dog to traverse two paths. While well-studied for polygonal curves, extending this to more complex structures like trees and graphs presents significant algorithmic challenges. Specifically, computing the Fréchet distance between embedded graphs requires them to be isomorphic, meaning there's a one-to-one correspondence between their vertices that preserves adjacency and embedding. This paper tackles the problem of efficiently computing this distance for trees and, more generally, for graphs with bounded tree width, a structural property that allows for efficient algorithms.
Methods
The authors develop distinct algorithmic approaches for trees and bounded tree width graphs.
For trees, they build upon existing ideas of comparing subtrees bottom-up. A key step involves contracting degree-2 vertices to simplify the tree structure. They then compute the Fréchet distance between these contracted paths and edges. For the core tree comparison, they construct a bipartite graph where nodes represent subtrees and edge weights are Fréchet distances between corresponding subtrees. A bottleneck matching algorithm is then employed to find the minimum maximum Fréchet distance across all possible isomorphisms.
For graphs with bounded tree width, the approach leverages existing algorithms for graph isomorphism on such structures. They adapt an algorithm by Grohe et al. that uses dynamic programming over tree decompositions. The core idea is to refine tree decompositions to capture isomorphism-invariant information. They then modify the isomorphism testing to specifically find isomorphisms that respect a given distance limit. This is achieved by adjusting the coloring and abstraction steps in the isomorphism algorithm to incorporate distance constraints. Finally, a binary search over possible distances is performed to find the minimum Fréchet distance.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Contraction of Degree-2 Vertices: Simplifying trees by contracting paths of degree-2 vertices is a crucial preprocessing step that reduces the problem's complexity without losing essential structural information for Fréchet distance computation.
- Bottleneck Matching for Trees: The application of bottleneck matching on a bipartite graph of subtree Fréchet distances provides an elegant way to find the optimal correspondence between subtrees for minimizing the maximum Fréchet distance.
- Leveraging Tree Decompositions for Graphs: The paper demonstrates that the structural properties captured by tree decompositions, which are known to be powerful for parameterized graph problems, can be effectively adapted to compute Fréchet distances by integrating distance constraints into isomorphism testing.
- FPT for Bounded Tree Width Graphs: The result that Fréchet distance for graphs of bounded tree width can be computed in fixed-parameter tractable time is significant, suggesting that this measure is computationally tractable for a broad class of structured graphs.
Key Results
- Trees:
- $O(n^2)$ time for trees of bounded degree.
- $O(n^2 \sqrt{n \log n})$ time for trees of arbitrary degree.
- An additional $O(n^2 \log n)$ preprocessing step is needed if both trees have "long" degree-2 paths.
- Graphs with Bounded Tree Width:
- The Fréchet distance can be computed in $2^{O(k \log^c k)} n^{O(1)} \log n$ time, where $n$ is the number of vertices and $k$ is the tree width. This is a fixed-parameter tractable result with respect to the tree width.
Limitations and Future Work
The paper acknowledges that their algorithms assume the metric space (where the graphs are embedded) allows for constant-time distance computation. If this is not the case, the running times would increase. The authors also note that a polynomial-time algorithm for general graphs is unlikely, as it would imply a polynomial-time algorithm for graph isomorphism. Future work could explore other parameters for which the Fréchet distance of graphs might be fixed-parameter tractable.
Summary updated