The directed Physarum dynamics is known to solve positive linear programs: minimize @math subject to @math and @math for a positive cost vector @math . The directed Physarum dynamics evolves a positive vector @math according to the dynamics @math . Here @math is the solution to @math that minimizes the "energy" @math . In this paper, we study the non-uniform directed dynamics @math , where @math is a positive diagonal matrix. The non-uniform dynamics is more complex than the uniform dynamics (with @math being the identity matrix), as it allows each component of @math to react with different speed to the differences between @math and @math . Our contribution is to show that the non-uniform directed dynamics solves positive linear programs.
The paper @cite_11 proposes a mathematical model for the behavior of the slime and argues extensively that the model is adequate. Physarum is modeled as an electrical network with time varying resistors. We have a simple graph @math with two distinguished nodes modeling the food sources. Each edge @math has a positive length @math and a positive capacity @math ; @math is fixed, but @math is a function of time. The resistance @math of @math is @math . In the electrical network defined by these resistances, a current of value 1 is forced from one of the distinguished nodes to the other. For an (arbitrarily oriented) edge @math , let @math be the resulting current over @math . Then, the capacity of @math evolves according to the differential equation where @math is the derivative of @math with respect to time.
@cite_11
2003810228
We study undirected networks with edge costs that satisfy the triangle inequality. Let @math denote the number of nodes. We present an @math -approximation algorithm for a generalization of the metric-cost subset @math -node-connectivity problem. Our approximation guarantee is proved via lower bounds that apply to the simple edge-connectivity version of the problem, where the requirements are for edge-disjoint paths rather than for openly node-disjoint paths. A corollary is that, for metric costs and for each @math , there exists a @math -node connected graph whose cost is within a factor of @math of the cost of any simple @math -edge connected graph. Based on our @math -approximation algorithm, we present an @math -approximation algorithm for the metric-cost node-connectivity survivable network design problem, where @math denotes the maximum requirement over all pairs of nodes. Our results contrast with the case of edge costs of 0 or 1, where Kortsarz, Krauthgamer, and Lee. [SIAM J. Comput., 33 (2004), pp. 704-720] recently proved, assuming NP @math DTIME( @math ), a hardness-of-approximation lower bound of @math for the subset @math -node-connectivity problem, where @math denotes a small positive number. In the subgraph-freeness problem, we are given a constant-size graph @math , and wish to determine whether the network contains @math as a subgraph or not. The relaxation of the problem only requires us to distinguish graphs that are @math -free from graphs that are @math -far from @math -free, meaning an @math -fraction of their edges must be removed to obtain an @math -free graph. Recently, Censor-Hillel et. al. and showed that in the property-testing regime it is possible to test @math -freeness for any graph @math of size 4 in constant time, @math rounds, regardless of the network size. However, Fraigniaud et. al. also showed that their techniques for graphs @math of size 4 cannot test @math -cycle-freeness in constant time. In this paper we revisit the subgraph-freeness problem and show that @math -cycle-freeness, and indeed @math -freeness for many other graphs @math comprising more than 4 vertices, can be tested in constant time. We show that @math -freeness can be tested in @math rounds for any cycle @math , improving on the running time of @math of the previous algorithms for triangle-freeness and @math -freeness. In the special case of triangles, we show that triangle-freeness can be solved in @math rounds independently of @math , when @math is not too small with respect to the number of nodes and edges. We also show that @math -freeness for any constant-size tree @math can be tested in @math rounds, even without the property-testing relaxation. Building on these results, we define a general class of graphs for which we can test subgraph-freeness in @math rounds. This class includes all graphs over 5 vertices except the 5-clique, @math . For cliques @math over @math nodes, we show that @math -freeness can be tested in @math rounds, where @math is the number of edges. Given a Euclidean graph @math in @math with @math vertices and @math edges, we consider the problem of adding an edge to @math such that the stretch factor of the resulting graph is minimized. Currently, the fastest algorithm for computing the stretch factor of a graph with positive edge weights runs in @math @math time, resulting in a trivial @math @math -time algorithm for computing the optimal edge. First, we show that a simple modification yields the optimal solution in @math @math time using @math @math space. To reduce the running time we consider several approximation algorithms. Given an undirected graph @math , it is known that its edge-connectivity @math can be computed by solving @math max-flow problems. The best time bounds known for the problem are @math , due to Matula (28th IEEE Symposium on the Foundations of Computer Science, 1987, pp. 249–251) if G is simple, and @math , due to Even and Tarjan (SIAM J. Comput., 4 (1975), pp. 507–518) if G is multiple.An @math time algorithm for computing the edge-connectivity @math of a multigraph @math , where @math is the number of pairs of nodes between which G has an edge, is proposed. This algorithm does not use any max-flow algorithm but consists only of @math times of graph searches and edge contractions. This method is then extended to a capacitated network to compute its minimum cut capacity in @math time. A graph @math is called @math -full if @math contains a subgraph @math of @math edges such that, for any non-empty @math , @math holds. Here, @math denotes the set of vertices incident to @math . It is known that the family of edge sets of @math -full graphs forms a family of matroid, known as the sparsity matroid of @math . In this paper, we give a constant-time approximation algorithm for the rank of the sparsity matroid of a degree-bounded undirected graph. This leads to a constant-time tester for @math -fullness in the bounded-degree model, (i.e., we can decide with high probability whether an input graph satisfies a property @math or far from @math ). Depending on the values of @math and @math , it can test various properties of a graph such as connectivity, rigidity, and how many spanning trees can be packed. Based on this result, we also propose a constant-time tester for @math -edge-connected-orientability in the bounded-degree model, where an undirected graph @math is called @math -edge-connected-orientable if there exists an orientation @math of @math with a vertex @math such that @math contains @math arc-disjoint dipaths from @math to each vertex @math and @math arc-disjoint dipaths from each vertex @math to @math . A tester is called a one-sided error tester for @math if it always accepts a graph satisfying @math . We show, for @math and (proper) @math , any one-sided error tester for @math -fullness and @math -edge-connected-orientability requires @math queries. We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property @math is called a @math -graph . If @math satisfies certain properties, then an n-node m-edge @math -graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2) X has at most @math bits for any continuous superadditive function @math so that there are at most @math distinct @math -node @math -graphs. The methodology is applicable to general classes of graphs; this paper focuses on planar graphs. Examples of such @math include all conjunctions over the following groups of properties: (1) G is a planar graph or a plane graph; (2) @math is directed or undirected; (3) @math is triangulated, triconnected, biconnected, merely connected, or not required to be connected; (4) the nodes of G are labeled with labels from @math for @math ; (5) the edges of G are labeled with labels from @math for @math ; and (6) each node (respectively, edge) of G has at most @math self-loops (respectively, @math multiple edges). Moreover, @math and @math are not required to be O(1) for the cases of @math being a plane triangulation. These examples are novel applications of small cycle separators of planar graphs and are the only nontrivial classes of graphs, other than rooted trees, with known polynomial-time information-theoretically optimal coding schemes. We consider the @math -Center problem and some generalizations. For @math -Center a set of @math center vertices needs to be found in a graph @math with edge lengths, such that the distance from any vertex of @math to its nearest center is minimized. This problem naturally occurs in transportation networks, and therefore we model the inputs as graphs with bounded highway dimension, as proposed by [SODA 2010]. We show both approximation and fixed-parameter hardness results, and how to overcome them using fixed-parameter approximations, where the two paradigms are combined. In particular, we prove that for any @math computing a @math -approximation is W[2]-hard for parameter @math and NP-hard for graphs with highway dimension @math . The latter does not rule out fixed-parameter @math -approximations for the highway dimension parameter @math , but implies that such an algorithm must have at least doubly exponential running time in @math if it exists, unless the ETH fails. On the positive side, we show how to get below the approximation factor of @math by combining the parameters @math and @math : we develop a fixed-parameter @math -approximation with running time @math . Additionally we prove that, unless P=NP, our techniques cannot be used to compute fixed-parameter @math -approximations for only the parameter @math . We also provide similar fixed-parameter approximations for the weighted @math -Center and @math -Partition problems, which generalize @math -Center. For a pattern graph @math on @math nodes, we consider the problems of finding and counting the number of (not necessarily induced) copies of @math in a given large graph @math on @math nodes, as well as finding minimum weight copies in both node-weighted and edge-weighted graphs. Our results include the following: 1. The number of copies of an @math with an independent set of size @math can be computed exactly in @math time and @math space, or in @math time and @math space. (The @math notation omits @math factors.) To obtain these algorithms we provide fast algorithms for computing the permanent of a @math matrix over rings and semirings. 2. The number of copies of any @math having minimum (or maximum) node-weight (with arbitrary real weights on nodes) can be found in @math time, where @math is the matrix multiplication exponent and @math is divisible by @math . Similar results hold for other values of @math . Also, the number... Let @math denote the first passage time to 1 of a standard Brownian motion. It is well known that as @math goes to infinity, @math goes to zero at rate @math , where @math equals @math . The goal of this note is to establish a quantitative, infinite dimensional version of this result. Namely, we will prove the existence of positive and finite constants @math and @math , such that for all @math , @math where @math ' denotes the natural logarithm, and @math is the Fukushima-Malliavin capacity on the space of continuous functions. In this paper we consider the Stochastic Matching problem, which is motivated by applications in kidney exchange and online dating. We are given an undirected graph in which every edge is assigned a probability of existence and a positive profit, and each node is assigned a positive integer called timeout. We know whether an edge exists or not only after probing it. On this random graph we are executing a process, which one-by-one probes the edges and gradually constructs a matching. The process is constrained in two ways: once an edge is taken it cannot be removed from the matching, and the timeout of node @math upper-bounds the number of edges incident to @math that can be probed. The goal is to maximize the expected profit of the constructed matching. For this problem (Algorithmica 2012) provided a @math -approximation algorithm for bipartite graphs, and a @math -approximation for general graphs. In this work we improve the approximation factors to @math and @math , respectively. We also consider an online version of the bipartite case, where one side of the partition arrives node by node, and each time a node @math arrives we have to decide which edges incident to @math we want to probe, and in which order. Here we present a @math -approximation, improving on the @math -approximation of The main technical ingredient in our result is a novel way of probing edges according to a random but non-uniform permutation. Patching this method with an algorithm that works best for large probability edges (plus some additional ideas) leads to our improved approximation factors. This paper investigates a zero-sum game played on a weighted connected graph @math between two players, the tree player and the edge player. At each play, the tree player chooses a spanning tree @math and the edge player chooses an edge @math . The payoff to the edge player is @math , defined as follows: If @math lies in the tree @math then @math ; if @math does not lie in the tree then @math , where @math is the weight of edge @math and @math is the weight of the unique cycle formed when edge @math is added to the tree @math . The main result is that the value of the game on any @math -vertex graph is bounded above by @math . It is conjectured that the value of the game is @math . The game arises in connection with the @math -server problem on a road network; i.e., a metric space that can be represented as a multigraph @math in which each edge @math represents a road of length @math . It is shown that, if the value of the game on @math is @math , then there is a randomized strategy that achieves a competitive ratio of @math against any oblivious adversary. Thus, on any @math -vertex road network, there is a randomized algorithm for the @math -server problem that is @math competitive against oblivious adversaries. At the heart of the analysis of the game is an algorithm that provides an approximate solution for the simple network design problem. Specifically, for any @math -vertex weighted, connected multigraph, the algorithm constructs a spanning tree @math such that the average, over all edges @math , of @math is less than or equal to @math . This result has potential application to the design of communication networks. It also improves substantially known estimates concerning the existence of a sparse basis for the cycle space of a graph. Let @math be any undirected graph on @math vertices and @math edges. A path @math between any two vertices @math is said to be @math -approximate shortest path if its length is at most @math times the length of the shortest path between @math and @math . We consider the problem of building a compact data structure for a given graph @math which is capable of answering the following query for any @math and @math . report @math -approximate shortest path between @math and @math when vertex @math fails We present data structures for the single source as well all-pairs versions of this problem. Our data structures guarantee optimal query time. Most impressive feature of our data structures is that their size nearly match the size of their best static counterparts. For a positive parameter @math , the @math -bounded distance between a pair of vertices @math in a weighted undirected graph @math is the length of the shortest @math path in @math with at most @math edges, aka hops . For @math as above and @math , a @math -hopset of @math is a graph @math on the same vertex set, such that all distances in @math are @math -approximated by @math -bounded distances in @math . Hopsets are a fundamental graph-theoretic and graph-algorithmic construct, and they are widely used for distance-related problems in a variety of computational settings. Currently existing constructions of hopsets produce hopsets either with @math edges, or with a hopbound @math . In this paper we devise a construction of linear-size hopsets with hopbound @math . This improves the previous bound almost exponentially. We also devise efficient implementations of our construction in PRAM and distributed settings. The only existing PRAM algorithm EN16 for computing hopsets with a constant (i.e., independent of @math ) hopbound requires @math time. We devise a PRAM algorithm with polylogarithmic running time for computing hopsets with a constant hopbound, i.e., our running time is exponentially better than the previous one. Moreover, these hopsets are also significantly sparser than their counterparts from EN16 . We use our hopsets to devise a distributed routing scheme that exhibits near-optimal tradeoff between individual memory requirement @math of vertices throughout preprocessing and routing phases of the algorithm, and stretch @math , along with a near-optimal construction time @math , where @math is the hop-diameter of the input graph. Let @math be a compact Riemannian submanifold of @math of dimension @math and let @math be a sample of i.i.d. points in @math with uniform distribution. We study the random operators @math where @math is the Gaussian kernel and @math as @math Such operators can be viewed as graph laplacians (for a weighted graph with vertices at data points) and they have been used in the machine learning literature to approximate the Laplace-Beltrami operator of @math @math (divided by the Riemannian volume of the manifold). We prove several results on a.s. and distributional convergence of the deviations @math for smooth functions @math both pointwise and uniformly in @math and @math (here @math and @math is the Riemannian volume measure). In particular, we show that for any class @math of three times differentiable functions on @math with uniformly bounded derivatives @math as soon as @math and also prove asymptotic normality of @math (functional CLT) for a fixed @math and uniformly in @math The effective resistance between two nodes of a weighted graph is the electrical resistance seen between the nodes of a resistor network with branch conductances given by the edge weights. The effective resistance comes up in many applications and fields in addition to electrical network analysis, including, for example, Markov chains and continuous-time averaging networks. In this paper we study the problem of allocating edge weights on a given graph in order to minimize the total effective resistance, i.e., the sum of the resistances between all pairs of nodes. We show that this is a convex optimization problem and can be solved efficiently either numerically or, in some cases, analytically. We show that optimal allocation of the edge weights can reduce the total effective resistance of the graph (compared to uniform weights) by a factor that grows unboundedly with the size of the graph. We show that among all graphs with @math nodes, the path has the largest value of optimal total effective resistance and the complete graph has the least. Given a discrete random walk on a finite graph @math , the vacant set and vacant net are, respectively, the sets of vertices and edges which remain unvisited by the walk at a given step @math . These sets induce subgraphs of the underlying graph. Let @math be the subgraph of @math induced by the vacant set of the walk at step @math . Similarly, let @math be the subgraph of @math induced by the edges of the vacant net. For random @math -regular graphs @math , it was previously established that for a simple random walk, the graph @math of the vacant set undergoes a phase transition in the sense of the phase transition on Erd os -Renyi graphs @math . Thus, for @math there is an explicit value @math of the walk, such that for @math , @math has a unique giant component, plus components of size @math , whereas for @math all the components of @math are of size @math . We establish the threshold value @math for a phase transition in the graph @math of the vacant net of a simple random walk on a random @math -regular graph. We obtain the corresponding threshold results for the vacant set and vacant net of two modified random walks. These are a non-backtracking random walk, and, for @math even, a random walk which chooses unvisited edges whenever available. This allows a direct comparison of thresholds between simple and modified walks on random @math -regular graphs. The main findings are the following: As @math increases the threshold for the vacant set converges to @math in all three walks. For the vacant net, the threshold converges to @math for both the simple random walk and non-backtracking random walk. When @math is even, the threshold for the vacant net of the unvisited edge process converges to @math , which is also the vertex cover time of the process. Let @math be a simple polygon of @math vertices. We consider two-point @math shortest path queries in @math . We build a data structure of @math size in @math time such that given any two query points @math and @math , the length of an @math shortest path from @math to @math in @math can be computed in @math time, or in @math time if both @math and @math are vertices of @math , and an actual shortest path can be output in additional linear time in the number of edges of the path. To achieve the result, we propose a mountain decomposition of simple polygons, which may be interesting in its own right. Most importantly, our approach is much simpler than the previous work on this problem. We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d+1 fewer tokens, where d is the maximum degree of any node in the network. We show that within @math steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most @math , where @math is the global imbalance in tokens (i.e., the maximum difference between the number of tokens at any node initially and the average number of tokens), n is the number of nodes in the network, and @math is the edge expansion of the network. The time bound is tight in the sense that for any graph with edge expansion @math , and for any value @math , there exists an initial distribution of tokens with imbalance @math for which the time to reduce the imbalance to even @math is at least @math . The bound on the final imbalance is tight in the sense that there exists a class of networks that can be locally balanced everywhere (i.e., the maximum difference in tokens between any two neighbors is at most 2d), while the global imbalance remains @math . Furthermore, we show that upon reaching a state with a global imbalance of @math , the time for this algorithm to locally balance the network can be as large as @math . We extend our analysis to a variant of this algorithm for dynamic and asynchronous networks. We also present tight bounds for a randomized algorithm in which each node sends at most one token in each step. We present new and improved data structures that answer exact node-to-node distance queries in planar graphs. Such data structures are also known as distance oracles. For any directed planar graph on n nodes with non-negative lengths we obtain the following: * Given a desired space allocation @math , we show how to construct in @math time a data structure of size @math that answers distance queries in @math time per query. As a consequence, we obtain an improvement over the fastest algorithm for k-many distances in planar graphs whenever @math . * We provide a linear-space exact distance oracle for planar graphs with query time @math for any constant eps>0. This is the first such data structure with provable sublinear query time. * For edge lengths at least one, we provide an exact distance oracle of space @math such that for any pair of nodes at distance D the query time is @math . Comparable query performance had been observed experimentally but has never been explained theoretically. Our data structures are based on the following new tool: given a non-self-crossing cycle C with @math nodes, we can preprocess G in @math time to produce a data structure of size @math that can answer the following queries in @math time: for a query node u, output the distance from u to all the nodes of C. This data structure builds on and extends a related data structure of Klein (SODA'05), which reports distances to the boundary of a face, rather than a cycle. The best distance oracles for planar graphs until the current work are due to Cabello (SODA'06), Djidjev (WG'96), and Fakcharoenphol and Rao (FOCS'01). For @math and space @math , we essentially improve the query time from @math to @math .