A novel exponential time algorithm is presented to compute the exact GED and a corresponding edit sequence in $O^*(4 + \varepsilon)^n$ time and polynomial space, provided one of the two graphs admits strictly sublinear balanced separators.
Abstract
The Graph Edit Distance (GED) is a widely used graph similarity measure asking for the minimum cost of a sequence of edits transforming one (labeled) graph into another. The considered edit operations are deletion, insertion, and relabeling of nodes and edges. Special cases include the Graph Isomorphism problem, as well as many other graph problems that ask for the existence or minimum cost of a certain substructure, like the Traveling Salesman or Maximum Clique problem. We present a novel exponential time algorithm to compute the exact GED and a corresponding edit sequence in $O^*(4 + \varepsilon)^n$ time and polynomial space, provided one of the two graphs admits strictly sublinear balanced separators. In particular, the claimed runtime holds if one of the graphs is $K_h$-minor free (e.g., planar), or has bounded treewidth, which is the case for many real-world applications (e.g., all instances in GEDLIB). This substantially improves the best known worst-case running time bounds of $O^*(n!)$ for these graph classes.
It is shown that bidirectional Dijkstra is still instance-optimal on simple undirected weighted graphs under the order-oblivious model, where incident edges are given in a random order, and under the order-dependent model, where bidirectional Dijkstra is not instance-optimal.
Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup et al.· 1 citation
This paper asks what structural properties of the graph itself make metric repair tractable, and gives pseudo-polynomial time algorithms for series-parallel graphs, and by generalization, graphs of bounded treewidth and a new algorithm for the length-bounded multicut problem.
Asaf Etgar, A. Gilbert, Jamie Tucker-Foltz· arXiv.org· 0 citations
The cost of a hierarchical clustering can be represented by an ultrametric whose lowest-common-ancestor labels are cluster cardinalities. We relate this known representation to the shortest-path geometry of a similarity graph. For a connected support graph $G$, let $d_G$ be its unit-length shortest-path metric and let the edge weights enter only the objective. We prove that the shifted Dasgupta optimum is exactly the minimum edge-weighted cost of a cardinality-realizable ultrametric that dominates $d_G$. Connectedification lemmas put this problem and its freely labeled dominating-ultrametric relaxation on the same class of connected binary hierarchies, labeled respectively by cardinality and graph diameter. As a sharp baseline, we determine the exact worst-case price of cardinality realizability: on every $n$-vertex instance the ratio of the two optima is at most $(2n-1)/3$, with equality on the unweighted complete graph; the sharp factor for the standard unshifted objective is $2(n+1)/3$. Our principal structural result bounds this gap by a hereditary weighted fragmentation profile defined through connected balanced cuts. Uniform local control gives an $O(\log n)$ gap, polynomial decay gives a constant gap, and the logarithmic order is tight even for unweighted trees of maximum degree $3$. On locally regular bounded-degree trees, the hierarchy can be constructed in $O(n\log n)$ time. An energy decomposition and a geometric density bound provide supporting instance-sensitive estimates. Thus the cardinality label has an unavoidable linear worst case but admits substantially smaller bounds on natural sparse graph classes.
In a weighted graph $G = (V, E)$, the maximum weight matching problem (MWM) asks for a matching (i.e. pairing) of its vertices, such that each vertex is paired with at most one other vertex and the total sum of weights of all edges connecting paired vertices is maximised. If the vertices of the graph correspond to points in the Euclidean plane and the weights to their pairwise Euclidean distances, we get the Euclidean maximum weight matching problem (Euclidean MWM). The best optimum-solution algorithm for this problem runs in $O(n^{2.5})$. Furthermore, there exists an FPTAS guaranteeing a $(1 - \epsilon)$-approximation ratio, which runs in $O(m \epsilon^{-1} \log \epsilon^{-1})$ time. Heuristics with a subquadratic running time (with respect to the number of vertices $|V|$) are known, but often yield solutions of a modest quality. In this paper, we present a novel algorithm for solving the Euclidean MWM running in $O(n \log n)$ time and providing excellent solution quality, especially for larger instances. In particular, in our computational tests, the algorithm yielded optimum or near-optimum solutions for all test instances; the worst observed optimality gap was less than $1.38\%$. This makes the algorithm highly attractive for practical applications, especially when exact methods become computationally prohibitive due to the size of the instance.
This paper provides the first truly linear-time approximation scheme for the Densest Subgraph Problem, and uses assignments arising from a flow-based formulation together with a structural carving lemma to progressively carve "sparse" parts of the graph while nearly preserving the densest subgraph.
Elena Grigorescu, Mehrshad Taziki· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
