Metric spaces $(X, d)$ are ubiquitous objects in mathematics and computer science that allow for capturing (pairwise) distance relationships $d(x, y)$ between points $x, y \in X$. Because of this, it is natural to ask what useful generalizations there are of metric spaces for capturing "$k$-wise distance relationships" $d(x_1, \ldots, x_k)$ among points $x_1, \ldots, x_k \in X$ for $k > 2$. To that end, Gähler (Math. Nachr., 1963) (and perhaps others even earlier) defined $k$-metric spaces, which generalize metric spaces, and most notably generalize the triangle inequality $d(x_1, x_2) \leq d(x_1, y) + d(y, x_2)$ to the "simplex inequality" $d(x_1, \ldots, x_k) \leq \sum_{i=1}^k d(x_1, \ldots, x_{i-1}, y, x_{i+1}, \ldots, x_k)$. (The definition holds for any fixed $k \geq 2$, and a $2$-metric space is just a (standard) metric space.) In this work, we introduce strong $k$-metric spaces, $k$-metric spaces that satisfy a topological condition stronger than the simplex inequality, which makes them "behave nicely." We also introduce coboundary $k$-metrics, which generalize $\ell_p$ metrics (and in fact all finite metric spaces induced by norms) and minimum bounding chain $k$-metrics, which generalize shortest path metrics (and capture all strong $k$-metrics). Using these definitions, we prove analogs of a number of fundamental results about embedding finite metric spaces including Fréchet embedding (isometric embedding into $\ell_{\infty}$) and isometric embedding of all tree metrics into $\ell_1$. We also study relationships between families of (strong) $k$-metrics, and show that natural quantities, like simplex volume, are strong $k$-metrics.

We define and investigate the Fréchet edit distance problem. Given two polygonal curves $π$ and $σ$ and a threshhold value $δ>0$, we seek the minimum number of edits to $σ$ such that the Fréchet distance between the edited $σ$ and $π$ is at most $δ$. For the edit operations we consider three cases, namely, deletion of vertices, insertion of vertices, or both. For this basic problem we consider a number of variants. Specifically, we provide polynomial time algorithms for both discrete and continuous Fréchet edit distance variants, as well as hardness results for weak Fréchet edit distance variants.

Effective resistance is a distance between vertices of a graph that is both theoretically interesting and useful in applications. We study a variant of effective resistance called the biharmonic distance. While the effective resistance measures how well-connected two vertices are, we prove several theoretical results supporting the idea that the biharmonic distance measures how important an edge is to the global topology of the graph. Our theoretical results connect the biharmonic distance to well-known measures of connectivity of a graph like its total resistance and sparsity. Based on these results, we introduce two clustering algorithms using the biharmonic distance. Finally, we introduce a further generalization of the biharmonic distance that we call the $k$-harmonic distance. We empirically study the utility of biharmonic and $k$-harmonic distance for edge centrality and graph clustering.

The distinguishing power of graph transformers is tied to the choice of positional encoding: features used to augment the base transformer with information about the graph. There are two primary types of positional encoding: absolute positional encodings (APEs) and relative positional encodings (RPEs). APEs assign features to each node and are given as input to the transformer. RPEs instead assign a feature to each pair of nodes, e.g., shortest-path distance, and are used to augment the attention block. A priori, it is unclear which method is better for maximizing the power of the resulting graph transformer. In this paper, we aim to understand the relationship between these different types of positional encodings. Interestingly, we show that graph transformers using APEs and RPEs are equivalent in their ability to distinguish non-isomorphic graphs. In particular, we demonstrate how to interchange APEs and RPEs while maintaining their distinguishing power in terms of graph transformers. However, in the case of graphs with node features, we show that RPEs may have an advantage over APEs. Based on our theoretical results, we provide a study of different APEs and RPEs—including the shortest-path and resistance distance and the recently introduced stable and expressive positional encoding (SPE)—and compare their distinguishing power in terms of transformers. We believe our work will help navigate the vast number of positional encoding choices and provide guidance on the future design of positional encodings for graph transformers.

Message passing graph neural networks (GNNs) are a popular learning architectures for graph-structured data. However, one problem GNNs experience is oversquashing, where a GNN has difficulty sending information between distant nodes. Understanding and mitigating oversquashing has recently received significant attention from the research community. In this paper, we continue this line of work by analyzing oversquashing through the lens of the *effective resistance* between nodes in the input graph. Effective resistance intuitively captures the ``strength'' of connection between two nodes by paths in the graph, and has a rich literature spanning many areas of graph theory. We propose to use *total effective resistance* as a bound of the total amount of oversquashing in a graph and provide theoretical justification for its use. We further develop an algorithm to identify edges to be added to an input graph to minimize the total effective resistance, thereby alleviating oversquashing. We provide empirical evidence of the effectiveness of our total effective resistance based rewiring strategies for improving the performance of GNNs.

Abstract. We describe algorithms to efficiently compute minimum [Formula: see text]-cuts and global minimum cuts of undirected surface-embedded graphs. Given an edge-weighted undirected graph [Formula: see text] with [Formula: see text] vertices embedded on an orientable surface of genus [Formula: see text], our algorithms can solve either problem in [Formula: see text] or [Formula: see text] time, whichever is better. When [Formula: see text] is a constant, our [Formula: see text] time algorithms match the best running times known for computing minimum cuts in planar graphs. Our algorithms for minimum cuts rely on reductions to the problem of finding a minimum-weight subgraph in a given [Formula: see text]-homology class, and we give efficient algorithms for this latter problem as well. If [Formula: see text] is embedded on a surface with genus [Formula: see text] and [Formula: see text] boundary components, these algorithms run in [Formula: see text] and [Formula: see text] time. We also prove that finding a minimum-weight subgraph homologous to a single input cycle is NP-hard, showing that it is likely impossible to improve upon the exponential dependencies on [Formula: see text] for this latter problem.

We consider the following surveillance problem: Given a set $P$ of $n$ sites in a metric space and a set of $k$ robots with the same maximum speed, compute a patrol schedule of minimum latency for the robots. Here a patrol schedule specifies for each robot an infinite sequence of sites to visit (in the given order) and the latency $L$ of a schedule is the maximum latency of any site, where the latency of a site $s$ is the supremum of the lengths of the time intervals between consecutive visits to $s$. When $k=1$ the problem is equivalent to the travelling salesman problem (TSP) and thus it is NP-hard. We have two main results. We consider cyclic solutions in which the set of sites must be partitioned into $\ell$ groups, for some~$\ell \leq k$, and each group is assigned a subset of the robots that move along the travelling salesman tour of the group at equal distance from each other. Our first main result is that approximating the optimal latency of the class of cyclic solutions can be reduced to approximating the optimal travelling salesman tour on some input, with only a $1+\varepsilon$ factor loss in the approximation factor and an $O\left(\left( k/\varepsilon \right)^k\right)$ factor loss in the runtime, for any $\varepsilon >0$. Our second main result shows that an optimal cyclic solution is a $2(1-1/k)$-approximation of the overall optimal solution. Note that for $k=2$ this implies that an optimal cyclic solution is optimal overall. The results have a number of consequences. For the Euclidean version of the problem, for instance, combining our results with known results on Euclidean TSP, yields a PTAS for approximating an optimal cyclic solution, and it yields a $(2(1-1/k)+\varepsilon)$-approximation of the optimal unrestricted solution. If the conjecture mentioned above is true, then our algorithm is actually a PTAS for the general problem in the Euclidean setting.

Given a simplicial complex with $n$ simplices, we consider the Connected Subsurface Recognition (c-SR) problem of finding a subcomplex that is homeomorphic to a given connected surface with a fixed boundary. We also study the related Sum-of-Genus Subsurface Recognition (SoG) problem, where we instead search for a surface whose boundary, number of connected components, and total genus are given. For both of these problems, we give parameterized algorithms with respect to the treewidth $k$ of the Hasse diagram that run in $2^{O(k \log k)}n^{O(1)}$ time. For the SoG problem, we also prove that our algorithm is optimal assuming the exponential-time hypothesis. In fact, we prove the stronger result that our algorithm is ETH-tight even without restriction on the total genus.

We describe a nearly-linear time algorithm to solve the linear system $L_1x = b$ parameterized by the first Betti number of the complex, where $L_1$ is the 1-Laplacian of a simplicial complex $K$ that is a subcomplex of a collapsible complex $X$ linearly embedded in $\mathbb{R}^{3}$. Our algorithm generalizes the work of Black et al.~[SODA2022] that solved the same problem but required that $K$ have trivial first homology. Our algorithm works for complexes $K$ with arbitrary first homology with running time that is nearly-linear with respect to the size of the complex and polynomial with respect to the first Betti number. The key to our solver is a new algorithm for computing the Hodge decomposition of 1-chains of $K$ in nearly-linear time. Additionally, our algorithm implies a nearly quadratic solver and nearly quadratic Hodge decomposition for the 1-Laplacian of any simplicial complex $K$ embedded in $\mathbb{R}^{3}$, as $K$ can always be expanded to a collapsible embedded complex of quadratic complexity.

We consider a variety of topology problems on a d-dimensional simplicial complex K given that K ∪ X for X a collapsible simplicial complex embedded in ℝd+1 with known collapsing sequence. Our first result is a solver for the linear system L1x = b, where L1 is the 1-Laplacian of a simplicial complex K with dimH1(K) = 0 and K ∪ X for X a collapsible simplicial complex embedded in ℝ3 with a known collapsing sequence. Our algorithm runs in O(n log2 (nκ/∊)) time, where n is the total number of vertices, edges, and triangles in X, κ is the largest condition number of the two parts of the Laplacian, and ∊ quantifies the approximation quality. This result is a generalization of Cohen et al. [SODA 2014]. The new technical piece of our Laplacian solver, in addition to the machinery described by Cohen et al., is an algorithm to compute a bounding chain of a 1-cycle within k. In addition, we describe faster algorithms for testing null-homology of (d–1)-cycles and null-cohomology of d-cocycles. Our algorithm runs in O(nd) time, where nd is the number of d-simplices in X. Finally, we describe an algorithm to compute a (d–1)-cohomology basis from a given (d–1)-homology basis for a d-simplicial complex K in O(βd–1nd) time; βd–1 is the rank of the (d–1)st homology group of k. In particular, we can obtain a cohomology basis for subcomplexes of a collapsible complex X embedded in ℝ3 in O(nd log nd + βd–1 n) time using a homology basis computed by the algorithm of Dey [SODA 2019]. For all of the problems above, if K ∪ ℝ3 and the collapsible supercomplex X is not provided, we can expand K into a convex ball of possibly quadratic complexity, which is known to be collapsible, resulting in nearly quadratic time algorithms.

We consider high dimensional variants of the maximum flow and minimum cut problems in the setting of simplicial complexes and provide both algorithmic and hardness results. By viewing flows and cuts topologically in terms of the simplicial (co)boundary operator we can state these problems as linear programs and show that they are dual to one another. Unlike graphs, complexes with integral capacity constraints may have fractional max-flows. We show that computing a maximum integral flow is NP-hard. Moreover, we give a combinatorial definition of a simplicial cut that seems more natural in the context of optimization problems and show that computing such a cut is NP-hard. However, we provide conditions on the simplicial complex for when the cut found by the linear program is a combinatorial cut. For $d$-dimensional simplicial complexes embedded into $\mathbb{R}^{d+1}$ we provide algorithms operating on the dual graph: computing a maximum flow is dual to computing a shortest path and computing a minimum cut is dual to computing a minimum cost circulation. Finally, we investigate the Ford-Fulkerson algorithm on simplicial complexes, prove its correctness, and provide a heuristic which guarantees it to halt.

We study two optimization problems on simplicial complexes with homology over ℤ₂, the minimum bounded chain problem: given a d-dimensional complex 𝒦 embedded in ℝ^(d+1) and a null-homologous (d-1)-cycle C in 𝒦, find the minimum d-chain with boundary C, and the minimum homologous chain problem: given a (d+1)-manifold ℳ and a d-chain D in ℳ, find the minimum d-chain homologous to D. We show strong hardness results for both problems even for small values of d; d = 2 for the former problem, and d=1 for the latter problem. We show that both problems are APX-hard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixed-parameter tractable with respect to the size of the optimal solution. Moreover, we provide an O(√{log β_d})-approximation algorithm for the minimum bounded chain problem where β_d is the dth Betti number of 𝒦. Finally, we provide an O(√{log n_{d+1}})-approximation algorithm for the minimum homologous chain problem where n_{d+1} is the number of (d+1)-simplices in ℳ.

We describe a (1 + ε) approximation algorithm for finding the minimum distortion embedding of an n-point metric space, (X, dX), into a tree with vertex set X. The running time of our algorithm is n2 · (Δ/ε)(O(δopt/ε))2λ+1 parameterized with respect to the spread of X, denoted by Δ, the minimum possible distortion for embedding X into any tree, denoted by δopt, and the doubling dimension of X, denoted by λ. Hence we obtain a PTAS, provided δopt is a constant and X is a finite doubling metric space with polynomially bounded spread, for example, a point set with polynomially bounded spread in constant dimensional Euclidean space. Our algorithm implies a constant factor approximation with the same running time when Steiner vertices are allowed. Moreover, we describe a similar (1 + ε) approximation algorithm for finding a tree spanner of (X, dX) that minimizes the maximum stretch. The running time of our algorithm stays the same, except that δopt must be interpreted as the minimum stretch of any spanning tree of X. Finally, we generalize our tree spanner algorithm to a (1 + ε) approximation algorithm for computing a minimum stretch tree spanner of a weighted graph, where the running time is parameterized with respect to the maximum degree, in addition to the other parameters above. In particular, we obtain a PTAS for computing minimum stretch tree spanners of weighted graphs, with polynomially bounded spread, constant doubling dimension, and constant maximum degree, when a tree spanner with constant stretch exists.

We show that the Fréchet distance between two piecewise linear surfaces can be decided in finite time, hence, the problem is decidable. For the special case that one of the surfaces is a triangle, we show that the problem is in PSPACE. In both cases, our computational model is a Turing Machine, and our algorithms rely on Canny's result [STOC 1988] that the existential theory of the real numbers is decidable in PSPACE.

We describe a (1 + ∊)-approximation algorithm for finding the minimum distortion embedding of an n-point metric space X into the shortest path metric space of a weighted graph G with m vertices. The running time of our algorithm is parametrized by the values of the minimum distortion, δopt, the spread, Δ, of the points of X, the treewidth, ω, of G, and the doubling dimension, λ, of G. In particular, our result implies a PTAS provided an X with polynomial spread, and the doubling dimension of G, the treewidth of G, and δopt, are all constant. For example, if X has a polynomial spread and δopt is a constant, we obtain PTAS's for embedding X into the following spaces: the line, a cycle, a tree of bounded doubling dimension, and a k-outer planar graph of bounded doubling dimension (for a constant k).

It is known that annotating entities in unstructured and semistructured datasets by their concepts improves the effectiveness of answering queries over these datasets. Ideally, one would like to annotate entities of all relevant concepts in a dataset. However, it takes substantial time and computational resources to annotate concepts in large datasets and an organization may have sufficient resources to annotate only a subset of relevant concepts. Clearly, it would like to annotate a subset of concepts that provides the most effective answers to queries over the dataset. We propose a formal framework that quantifies the amount by which annotating entities of concepts from a taxonomy in a dataset improves the effectiveness of answering queries over the dataset. Because the problem is NP-hard, we propose an efficient approximation for the problem. Our extensive empirical studies validate our framework and show the accuracy and efficiency of our algorithm.

We study the problems of finding a minimum cycle basis (a minimum weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum weight set of cycles that generates the 1-dimensional (Z_2)-homology classes) of an undirected graph embedded on an orientable surface of genus g. The problems are closely related, because the minimum cycle basis of a graph contains its minimum homology basis, and the minimum homology basis of the 1-skeleton of any graph is exactly its minimum cycle basis. For the minimum cycle basis problem, we give a deterministic O(n^omega + 2^2g n^2)-time algorithm. The best known existing algorithms for surface embedded graphs are those for general sparse graphs: an O(n^omega) time Monte Carlo algorithm [Amaldi et. al., ESA'09] and a deterministic O(n^3) time algorithm [Mehlhorn and Michail, TALG'09]. For the minimum homology basis problem, we give an O(g^3 n log n)-time algorithm, improving on existing algorithms for many values of g and n.

For an undirected $n$-vertex graph $G$ with non-negative edge-weights, we consider the following type of query: given two vertices $s$ and $t$ in $G$, what is the weight of a minimum $st$-cut in $G$? We solve this problem in preprocessing time $O(n\log^3 n)$ for graphs of bounded genus, giving the first sub-quadratic time algorithm for this class of graphs. Our result also improves by a logarithmic factor a previous algorithm by Borradaile, Sankowski and Wulff-Nilsen (FOCS 2010) that applied only to planar graphs. Our algorithm constructs a Gomory-Hu tree for the given graph, providing a data structure with space $O(n)$ that can answer minimum-cut queries in constant time. The dependence on the genus of the input graph in our preprocessing time is $2^{O(g^2)}$.

We describe two (1+epsilon)-approximation algorithms for computing the Fréchet distance between two homeomorphic piecewise linear surfaces R and S of genus zero and total complexity n, with Frechet distance delta. (1) A 2^{O((n + ( (Area(R)+Area(S))/(epsilon.delta)^2 )^2 )} time algorithm if R and S are composed of fat triangles (triangles with angles larger than a constant). (2) An O(D/(epsilon.delta)^2) n + 2^{O(D^4/(epsilon^4.delta^2))} time algorithm if R and S are polyhedral terrains over [0,1]^2 with slope at most D. Although, the Fréchet distance between curves has been studied extensively, very little is known for surfaces. Our results are the first algorithms (both for surfaces and terrains) that are guaranteed to terminate in finite time. Our latter result, in particular, implies a linear time algorithm for terrains of constant maximum slope and constant Frechet distance.

We describe algorithms for the problem of minimum distortion embeddings of finite metric spaces into the real line (or a finite subset of the line). The time complexities of our algorithms are parametrized by the values of the minimum distortion, δ, and the spread, Δ, of the point set we are embedding. We consider the problem of finding the minimum distortion bijection between two finite subsets of IR. This problem was known to have an exact polynomial time solution when δ is below a specific small constant, and hard to approximate within a factor of δ1-E, when δ is polynomially large. Let D be the largest adjacent pair distance, a value potentially much smaller than Δ. Then we provide a δO(δ2log2D)nO(1)time exact algorithm for this problem, which in particular yields a quasipolynomial running time for constant δ, and polynomial D. For the more general problem of embedding any finite metric space (X, dX) into a finite subset of the line, Y , we provide a ΔO(δ2)(mn)O(1)time O(1)-approximation algorithm (where X = n and Y = m), which runs in polynomial time provided δ is a constant and Δ is polynomial. This in turn allows us to get a ΔO(δ2)(n)O(1)time O(1)-approximation algorithm for embedding (X, dX) into the continuous real line.

BACKGROUND: Tumorigenesis is an evolutionary process by which tumor cells acquire mutations through successive diversification and differentiation. There is much interest in reconstructing this process of evolution due to its relevance to identifying drivers of mutation and predicting future prognosis and drug response. Efforts are challenged by high tumor heterogeneity, though, both within and among patients. In prior work, we showed that this heterogeneity could be turned into an advantage by computationally reconstructing models of cell populations mixed to different degrees in distinct tumors. Such mixed membership model approaches, however, are still limited in their ability to dissect more than a few well-conserved cell populations across a tumor data set. RESULTS: We present a method to improve on current mixed membership model approaches by better accounting for conserved progression pathways between subsets of cancers, which imply a structure to the data that has not previously been exploited. We extend our prior methods, which use an interpretation of the mixture problem as that of reconstructing simple geometric objects called simplices, to instead search for structured unions of simplices called simplicial complexes that one would expect to emerge from mixture processes describing branches along an evolutionary tree. We further improve on the prior work with a novel objective function to better identify mixtures corresponding to parsimonious evolutionary tree models. We demonstrate that this approach improves on our ability to accurately resolve mixtures on simulated data sets and demonstrate its practical applicability on a large RNASeq tumor data set. CONCLUSIONS: Better exploiting the expected geometric structure for mixed membership models produced from common evolutionary trees allows us to quickly and accurately reconstruct models of cell populations sampled from those trees. In the process, we hope to develop a better understanding of tumor evolution as well as other biological problems that involve interpreting genomic data gathered from heterogeneous populations of cells.

We present an efficient algorithm for solving a linear system arising from the 1-Laplacian corresponding to a collapsible simplicial complex with a known collapsing sequence. When combined with a result of Chillingworth, our algorithm is applicable to convex simplicial complexes embedded in ℝ3. The running time of our algorithm is nearly-linear in the size of the complex and is logarithmic on its numerical properties. Our algorithm is based on projection operators and combinatorial steps for transferring between them. The former relies on decomposing flows into circulations and potential flows using fast solvers for graph Laplacians, and the latter relates Gaussian elimination to topological properties of simplicial complexes.

We consider the problem of estimating the surface area of an unknown n-dimensional set F given membership oracle access. In contrast to previous work, we do not assume that F is convex, and in fact make no assumptions at all about F. By necessity this means that we work in the property testing model; we seek an algorithm which, given parameters A and ∊, satisfies: if surf(F) ≤ A then the algorithm accepts (whp); if F is not ∊-close to some set G with surf (G) ≤ κA, then the algorithm rejects (whp). We call κ ≥ 1 the “approximation factor” of the testing algorithm. The n = 1 case (in which “surf(F) = 2m” means F is a disjoint union of m intervals) was introduced by Kearns and Ron [KR98], who solved the problem with κ = 1/∊ and O(1/∊) oracle queries. Later, Balcan et al. [BBBY12] solved it with with κ = 1 and O(1/∊4) queries. We give the first result for higher dimensions n. Perhaps surprisingly, our algorithm completely evades the “curse of dimensionality”: for any n and any κ > we give a test that uses O(1/∊) queries. For small n we have improved bounds. For n = 1 we can achieve κ = 1 with O(1/∊3.5) queries (slightly improving [BBBY12]), or any κ > 1 with O(1/∊) queries (improving [KR98]). For n = 2,3 we obtain κ ≈ 1.08,1.125 respectively, with O(1/∊) queries. Getting an arbitrary κ > 1 for n > 1 remains an open problem.

Let $G$ be a directed graph with n vertices embedded on an orientable surface of genus g with two designated vertices s and t. We show that counting the minimum (s,t)-cuts in G is fixed parameter tractable in g. Specially, we give a 2O(g) n2 time algorithm for this problem. Our algorithm requires counting sets of cycles in a particular integer homology class. That we can count these cycles is an interesting result in itself as there are few prior results that are fixed parameter tractable and deal directly with integer homology. We also describe an algorithm which, after running our algorithm to count minimum cuts once, can sample a minimum cut uniformly at random in O(gn) time per sample.

A simple path or cycle in a triangulated surface is normal if it intersects any triangle in a finite set of arcs, each crossing from one edge of the triangle to another. We describe an algorithm to "trace" a normal curve in O(min set{X, n2log X}) time, where n is the complexity of the surface triangulation and X is the number of times the curve crosses edges of the triangulation. In particular, our algorithm runs in polynomial time even when the number of crossings is exponential in n. Our tracing algorithm computes a new cellular decomposition of the surface with complexity O(n); the traced curve appears as a simple path or cycle in the 1-skeleton of the new decomposition. We apply our abstract tracing strategy to two different classes of normal curves: abstract curves represented by normal coordinates, which record the number of intersections with each edge of the surface triangulation, and simple geodesics, represented by a starting point and direction in the local coordinate system of some triangle. Our normal-coordinate algorithms are competitive with and conceptually simpler than earlier algorithms by Schaefer, Sedgwick, and 'tefankovic [COCOON 2002, CCCG 2008] and by Agol, Hass, and Thurston [Trans. AMS 2005].

We describe a O(log n)-approximation algorithm for computing the homotopic Frechet distance between two polygonal curves that lie on the boundary of a triangulated topological disk. Prior to this work, algorithms where known only for curves on the Euclidean plane with polygonal obstacles.

We give a deterministic algorithm to find the minimum cut in a surface-embedded graph in near-linear time. Given an undirected graph embedded on an orientable surface of genus g, our algorithm computes the minimum cut in gO(g)n log log n time, matching the running time of the fastest algorithm known for planar graphs, due to Łącki and Sankowski, for any constant g. Indeed, our algorithm calls Łącki and Sankowski's recent O(n log log n) time planar algorithm as a subroutine. Previously, the best time bounds known for this problem followed from two algorithms for general sparse graphs: a randomized algorithm of Karger that runs in O(n log3 n) time and succeeds with high probability, and a deterministic algorithm of Nagamochi and Ibaraki that runs in O(n2 log n) time. We can also achieve a deterministic gO(g)n2 log log n time bound by repeatedly applying the best known algorithm for minimum (s, t)-cuts in surface graphs. The bulk of our work focuses on the case where the dual of the minimum cut splits the underlying surface into multiple components with positive genus.

We describe the first algorithm to compute maximum flows in surface-embedded graphs in near-linear time. Specifically, given a graph embedded on a surface of genus $g$, with two specified vertices $s$ and $t$ and integer edge capacities that sum to $C$, our algorithm computes a maximum $(s,t)$-flow in $O(g^8 n\log^2 n\log^2 C)$ time. We also present a combinatorial algorithm that takes $g^{O(g)} n^{3/2}$ arithmetic operations. Except for the special case of planar graphs, for which an $O(n\log n)$-time algorithm has been known for 20 years, the best previous time bounds for maximum flows in surface-embedded graphs follow from algorithms for general sparse graphs. For graphs of any fixed genus, our algorithms improve these time bounds by roughly a factor of $\sqrt{n}$. Our key insight is to optimize the homology class of the flow, rather than directly optimizing the flow itself; two flows are in the same homology class if their difference is a weighted sum of directed facial cycles. A dual formulation of our algorithm computes the minimum-cost circulation in a given (real or integer) homology class.

Let G be an n-vertex plane graph with non-negative edge weights, and let k terminal pairs be specified on h face boundaries. We present an algorithm to find k non-crossing walks in G of minimum total length that connect all terminal pairs, if any such walks exist, in 2O(h2)n log k time. The computed walks may overlap but may not cross each other or themselves. Our algorithm generalizes a result of Takahashi, Suzuki, and Nishizeki [Algorithmica 1996] for the special case h ≤ 2. We also describe an algorithm for the corresponding geometric problem, where the terminal points lie on the boundary of h polygonal obstacles of total complexity n, again in 2O(h2)n time, generalizing an algorithm of Papadopoulou [Int. J. Comput. Geom. Appl. 1999] for the special case h ≤ 2. In both settings, shortest non-crossing walks can have complexity exponential in h. We also describe algorithms to determine in O(n) time whether the terminal pairs can be connected by any non-crossing walks.

Let G be a directed graph with weighted edges, embedded on a surface of genus g. We describe an algorithm to compute a shortest directed cycle in G in any given ℤ2-homology class in 2O(g) n log n time; this problem is NP-hard even for undirected graphs. We also present two applications of our algorithm. The first is an algorithm to compute a shortest non-separating directed cycle in G in 2O (g) n log n time, improving the recent algorithm of Cabello et al. [SOCG 2010] for all g = o(log n). The second is a combinatorial algorithm to compute minimum (s, t)-cuts in undirected surface graphs in 2O(g)n log n time, improving on previous combinatorial algorithms, and in particular the recent of Chambers et al. [SOCG 2009], for all g = o(log n). Unlike earlier algorithms for surface graphs that construct and search finite portions of the universal cover, our algorithms use another canonical covering space, called the ℤ2-homology cover.

Let s and t be vertices in a directed graph G with non-negative edge weights. The replacement paths problem asks us to compute, for each edge e in G, the length of the shortest path from s to t that does not traverse e. We describe an algorithm that solves the replacement paths problem for directed graphs embedded on a surface of any genus g in O(gn log n) time, generalizing a recent O(n log n)-time algorithm of Wulff-Nilsen for planar graphs [SODA 2010].

We describe the first algorithms to compute minimum cuts in surface-embedded graphs in near-linear time. Given an undirected graph embedded on an orientable surface of genus g, with two specified vertices s and t, our algorithm computes a minimum (s,t)-cut in gO(g) n log n time. Except for the special case of planar graphs, for which O(n log n)-time algorithms have been known for more than 20 years, the best previous time bounds for finding minimum cuts in embedded graphs follow from algorithms for general sparse graphs. A slight generalization of our minimum-cut algorithm computes a minimum-cost subgraph in every Z2-homology class. We also prove that finding a minimum-cost subgraph homologous to a single input cycle is {NP}-hard.

Multihoming has been broadly employed by large enterprises, and stub networks to augment the availability and reliability of their Internet access. In this technique, the edge network is connected to the Internet through multiple upstream Internet Service Providers (ISPs) rather than one. Thus far, different aspects of multihomed networks have received intensive attention in the research community. However, there have been quite a few works on the selection methodologies of upstream ISPs for a multihomed network which is definitely a primary prerequisite for other challenges in this area. In this paper, we try to address the ISP selection problem for provisioning of survivable end-to-end connections in multihomed networks. We first argue about different design decisions that the network operator has to make for support of resiliency against single-link network failures. Then, the minimum ISP selection problem is defined in which the goal is to pick the minimum number of upstream ISPs such that by multihoming to them, the major connections of the network would achieve a satisfactory level of resiliency against link failures. Then, we propose a brute-force method to optimally unravel this problem. Despite the NP-hardness of our problem, we show that the proposed method can be used in practice to solve the problem in tolerable manner.

We describe the first algorithms to compute maximum flows in surface-embedded graphs in near-linear time. Specifically, given an undirected graph embedded on an orientable surface of genus g, with two specified vertices s and t, we can compute a maximum (s,t)-flow in O(g7 n log2 n log2 C) time for integer capacities that sum to C, or in (g log n)O(g) n time for real capacities. Except for the special case of planar graphs, for which an O(n log n)-time algorithm has been known for 20 years, the best previous time bounds for maximum flows in surface-embedded graphs follow from algorithms for general sparse graphs. Our key insight is to optimize the relative homology class of the flow, rather than directly optimizing the flow itself. A dual formulation of our algorithm computes the minimum-cost cycle or circulation in a given (real or integer) homology class.

Sensor networks are usually deployed in hostile environments for different purposes like monitoring and target tracking in an ad hoc manner. Due to the processing and storage limitations of tiny nodes codes (procedures) that provide different functionalities can be distributed in the network and make the entire network as a single system. Therefore, nodes have to communicate with each other to demand services which are implemented in another nodes using remote procedure call. Since in the sensor networks, energy consumption is mainly dominated by message passing, keeping highly related codes close to each other can extremely degrade the total energy utilization. In this paper we propose a code migration method, named ANTMIG, inspired from the ant clustering algorithm, to move the codes towards the source of request, considering the dynamic behavior of the network. Observing the local rate and direction of requests, procedures migrate to appropriate nodes that converges to the network minimum energy conservation state. Simulation results show the convergence and flexibility of the algorithm. Moreover, it shows more than fifty percent improvement in power conservation in comparison with the case there is no migration in the network. Although we have proposed our algorithm as a technique for code migration, it can be applied on other problems like data centric routing and data storage in wireless sensor networks, while the source of request changes time to time.

The privacy of users of mobile devices has been at stake, with emerging systems based on the mobile ad hoc networking technology raising additional concerns. The establishment of a connection between two nodes could readily reveal information to an eavesdropper. One approach to prevent this is to provide receiver anonymity, i.e., conceal the identity of the receiver, during the establishment of a communication path. In this paper, we introduce such a scheme that improves the efficiency of anonymous discovery, balances its cost among network nodes, and can be adaptive, trading off the degree of anonymity for the receiver.

The term multipath routing means using multiple paths concurrently to transport data over network. The main problem of this routing scheme is the difference among the delays of selected paths, which causes reordering of a single flow's packets. In this paper, this problem is analyzed through a sociological perspective. We show that reordering problem is not inherently related to multipath routing, rather caused by the dominant capitalist view of the problem. then, the problem is addressed through a Marxism perspective. We theoretically prove that by this perspective, there exists a routing scheme that minimizes latency and also the requirement of buffering at receiver.

Persian (Farsi) is one of the languages of Middle East. There are significant amount of Persian documents available in digital form and even more are created every day. Therefore, there is a necessity to implement Information Retrieval System with high precision for this language. This paper discusses the design, implementation and testing of a Fuzzy retrieval system for Persian called FuFaIR. This system also supports Fuzzy quantifiers in its query language. Tests have been conducted using a standard Persian test corpus called Hamshari. The performance results obtained from FuFaIR are positive and they indicate that the FuFaIR could notably outperform well known industry systems such as the vector space model.

Hierarchical routing strategy as a scalable solution to the QoS routing problem defines a particular kind of network state information; each domain advertises only its aggregated state to the outside. Unfortunately, topology aggregation (TA) which is the process of summarizing the topological information of domains introduces some inaccuracy due to the compaction of exact network state. To reduce inaccuracy, both the TA method and the routing algorithm must be carefully selected. In this paper, we propose a novel aggregation model which intelligently adapts the aggregated states of domains according to the needs and topological locations of consumer nodes. Based on this model, we modify one of the current TA methods to enhance its performance. Through extensive simulations, we show that appropriate adjustment of compact state based on its relevance to sources, results in a lower miss-admission ratio and longer update intervals for the hierarchical QoS routing protocols.

Sensor networks are usually composed of tiny and resource constraint devices, which make energy conservation a vital concern of their design. Reducing energy consumption has been addressed through different aspects till now. Topology control (TC), as the process of determining the transmission ranges of nodes to optimize energy utilization while keeping some network properties like connectivity, is a well-known approach. However, current TC schemes mostly account the transmission range of each node as the exclusive estimator for its energy consumption, while ignoring the amount of data it sends or relays. In this paper, we redefine the problem of topology control regarding both network load and transmission range parameters. Our approach is particularly formulated for sensor networks with one or more base stations. Then, under a certain modeling of environment, proper mathematical relations are provided to find the optimum solution. Finally, we show the advantages of our proposal through presenting analytical and experimental results.

Wireless ad hoc networks are usually composed of tiny and resource constraint devices, which make energy conservation a vital concern of their design. Reducing energy consumption has been addressed through different aspects till now. Topology control (TC) is a well-known approach which tries to assign the transmission ranges of nodes to optimize energy utilization while keeping some network properties like connectivity. However, in current TC schemes, the transmission range of each node is mostly accounted as the exclusive estimator for its energy consumption, while ignoring the amount of data it sends or relays. In this paper, we redefine the problem of topology control regarding both traffic load and transmission range parameters. After proving the NP-hardness of the new problem, we mathematically formulate it as a mixed integer linear programming problem to find the optimal solutions. Then, we introduce two polynomial-time heuristic algorithms to practically solve the problem. Finally, we show the advantages of our proposals through simulations