Search

The Cycle Packing problem asks whether a given undirected graph G = (V;E) con- tains k vertex-disjoint cycles. Since the publication of the classic Erd}os{Posa theorem in 1965, this problem received significant attention in the fields of graph theory and algorithm design. In particu- lar, this problem is one of the first problems studied in the framework of parameterized complexity. The nonuniform fixed-parameter tractability of Cycle Packing follows from the Robertson{Seymour theorem, a fact already observed by Fellows and Langston in the 1980s. In 1994, Bodlaender showed that Cycle Packing can be solved in time 2O(k2) jV j using exponential space. In the case a solu- tion exists, Bodlaender's algorithm also outputs a solution (in the same time). It has later become common knowledge that Cycle Packing admits a 2O(k log2 k) jV j-time (deterministic) algorithm using exponential space, which is a consequence of the Erd}os{Posa theorem. Nowadays, the design of this algorithm is given as an exercise in textbooks on parameterized complexity. Yet, no algorithm that runs in time 2o(k log2 k) jV jO(1), beating the bound 2O(k log2 k) jV jO(1), has been found. In light of this, it seems natural to ask whether the 2O(k log2 k) jV jO(1) bound is essentially optimal. In this paper, we answer this question negatively by developing a 2 O(k log2 k log log k) jV j-time (deterministic) algorithm for Cycle Packing. In the case a solution exists, our algorithm also outputs a solution (in the same time). Moreover, apart from beating the bound 2O(k log2 k) jV jO(1), our algorithm runs in time linear in jV j, and its space complexity is polynomial in the input size. [ABSTRACT FROM AUTHOR]

Given a multigraph G=(V, E) with a positive rational weight w(e) on each edge e, the weighted density problem (WDP) is to find a subset $U$ of V, with |U| ≥ 3 and odd, that maximizes 2w(U)/(|U|-1), where w(U) is the total weight of all edges with both ends in U, and the weighted fractional edge-coloring problem can be formulated as the following linear program: minimize 1Tx subject to Ax = w, x ≥ 0, where $A$ is the edge-matching incidence matrix of $G$. These two problems are closely related to the celebrated Goldberg-Seymour conjecture on edge-colorings of multigraphs, and are interesting in their own right. Even when w(e) = 1 for all edges e, determining whether WDP can be solved in polynomial time was posed by Jensen and Toft [Topics in Chromatic Graph Theory, Cambridge University Press, Cambridge, 2015, pp. 327-357] and by Stiebitz et al. [Graph Edge Colouring: Vizing's Theorem and Goldberg's Conjecture, John Wiley, New York, 2012] as an open problem. In this paper we present strongly polynomial-time algorithms for solving them exactly, and develop a novel matching removal technique for multigraph edge-coloring. [ABSTRACT FROM AUTHOR]

Given a multigraph G = (V;E) with a positive rational weight w(e) on each edge e, the weighted density problem (WDP) is to find a subset U of V , with |U|≥3 and odd, that maximizes 2w(U)=(|U| - 1), where w(U) is the total weight of all edges with both ends in U, and the weighted fractional edge-coloring problem can be formulated as the following linear program: minimize 1T x subject to Ax = w, x ≥ 0, where A is the edge-matching incidence matrix of G. These two problems are closely related to the celebrated Goldberg{Seymour conjecture on edge-colorings of multigraphs, and are interesting in their own right. Even when w(e) = 1 for all edges e, determining whether WDP can be solved in polynomial time was posed by Jensen and Toft [Topics in Chromatic Graph Theory, Cambridge University Press, Cambridge, 2015, pp. 327-357] and by Stiebitz et al. [Graph Edge Colouring: Vizing's Theorem and Goldberg's Conjecture, John Wiley, New York, 2012] as an open problem. In this paper we present strongly polynomial-time algorithms for solving them exactly, and develop a novel matching removal technique for multigraph edge-coloring. [ABSTRACT FROM AUTHOR]

In this paper we consider the well-studied problem of finding a perfect matching in a d-regular bipartite graph on 2n nodes with m = nd edges. The best known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes time O(m√n). In regular bipartite graphs, however, a matching is known to be computable in O(m) time (due to Cole, Ost, and Schirra). In a recent line of work by Goel, Kapralov, and Khanna the O(m) time bound was improved first to Õ(min{m, n2.5/d}) and then to Õ (min{m, n²/d}). In this paper, we give a randomized algorithm that finds a perfect matching in a d-regular graph and runs in O(n log n) time (both in expectation and with high probability). The algorithm performs an appropriately truncated alternating random walk to successively find augmenting paths. Our algorithm may be viewed as using adaptive uniform sampling, and is thus able to bypass the limitations of (nonadaptive) uniform sampling established in earlier work. Our techniques also give an algorithm that successively finds a matching in the support of a doubly stochastic matrix in expected time O(n log²n), with O(m) preprocessing time; this gives a simple O(m+mnlog²n) time algorithm for finding the Birkhoff-von Neumann decomposition of a doubly stochastic matrix. We show that randomization is crucial for obtaining o(nd) time algorithms by establishing an Ω(nd) lower bound for deterministic algorithms. We also show that there does not exist a randomized algorithm that finds a matching in a regular bipartite multigraph and takes o(n log n) time with high probability. [ABSTRACT FROM AUTHOR]

Following the spectral graph theory, a graph coloring technique, and algebraic methods in graph theory, we study the category UBigrn of loop-free edge-bipartite (signed) graphs Δ, with n ≥ 2 vertices, up to Z-congruences ~Z and ≈Z (defined in the paper), by means of the Gram matrix ĞΔ ∈ Mn(Z), the Coxeter-Gram matrix CoxΔ = -ĞΔ · ĞΔ-tr ∈ Mn(Z), the spectrum speccΔ of CoxΔ, the Coxeter polynomial coxΔ(t) ∈ Z[t], the Coxeter number cΔ ≥ 2, and the Z-bilinear Gram form bΔ : Zn x Zn → Z of Δ. Our main inspiration for the study comes from the representation theory of posets, groups and algebras, Lie theory, and Diophantine geometry problems. One of our aims is to compute the set CGpoln+ of all polynomials coxΔ(t), with positive connected graphs Δ in UBigrn, for all n ≥ 2, and to present a framework for a classification of graphs Δ in UBigrn, up to the congruence ≈Z, by means of their Coxeter polynomials coxΔ(t) ∈ Z[t] and Coxeter spectra. In particular, the Coxeter spectral analysis question, whether the congruence Δ ≈Z Δ' holds, for any pair of connected positive graphs Δ, Δ' ∈ UBigrn such that speccΔ = speccΔ', is studied in the paper. One of our main results contains an affirmative answer to the question and a description of the finite set CGpoln+ for n ≤ 8. One of the tools we apply is an inflation algorithm Δ → DΔ that associates with any connected positive graph Δ ∈ UBigrn a simply laced Dynkin diagram DΔ such that Δ ~Z DΔ, and coxΔ(t) and cΔ coincide with the Coxeter polynomial coxA(t) and the Coxeter number cA of a matrix morsification A ∈ MorDΔ ⊆ Mn(Z) for the diagram DΔ and, in case n ≤ 8, all pairs (coxΔ(t), cΔ) are listed. [ABSTRACT FROM AUTHOR]

We study the design of local algorithms for massive graphs. A local graph algorithm is one that finds a solution containing or near a given vertex without looking at the whole graph. We present a local clustering algorithm. Our algorithm finds a good cluster--a subset of vertices whose internal connections are significantly richer than its external connections--near a given vertex. The running time of our algorithm, when it finds a nonempty local cluster, is nearly linear in the size of the cluster it outputs. The running time of our algorithm also depends polylogarithmically on the size of the graph and polynomially on the conductance of the cluster it produces. Our clustering algorithm could be a useful primitive for handling massive graphs, such as social networks and web-graphs. As an application of this clustering algorithm, we present a partitioning algorithm that finds an approximate sparsest cut with nearly optimal balance. Our algorithm takes time nearly linear in the number edges of the graph. Using the partitioning algorithm of this paper, we have designed a nearly linear time algorithm for constructing spectral sparsifiers of graphs, which we in turn use in a nearly linear time algorithm for solving linear systems in symmetric, diagonally dominant matrices. The linear system solver also leads to a nearly linear time algorithm for approximating the second-smallest eigenvalue and corresponding eigenvector of the Laplacian matrix of a graph. These other results are presented in two companion papers. [ABSTRACT FROM AUTHOR]

In this paper, we show the Erdős-Pósa property for edge-disjoint packing of S-closed walks with parity constraints in 4-edge-connected graphs. More precisely, we prove that for any 4-edge-connected graph G and any vertex subset S, either G h as k edge-disjoint elementary closed odd walks, each of which has at least one vertex of S, or G has an edge set F with |F| < f (k) such that G - F has no such walks. The 4-edge-connectivity is the best possible in the sense that 3-edge-connected graphs do not satisfy the statement. Since the proof is constructive, we can design a fixed-parameter algorithm for finding k edge-disjoint walks satisfying the conditions in a 4-edge-connected graph for a parameter k. In addition, this gives a simple fixed-parameter algorithm for the parity edge-disjoint walks problem with k terminal pairs. [ABSTRACT FROM AUTHOR]

A total-weighting of a graph G = (V, E) is a mapping f which assigns to each element y ∈ V ∪ E a real number f (y) as the weight of y. A total-weighting f of G is proper if the coloring øf of the vertices of G defined as øf (v) = f (v) + Σe∈E(v) f (e) is a proper coloring of G, i.e., øf of (v) ≠ øf of (u) for any edge uv, where E(v) is the set of edges of G incident to v. For positive integers k and k', a graph G is called (k, k')-total-weight-choosable if whenever each vertex v is given k permissible weights and each edge e is given k' permissible weights, there is a proper total-weighting f of G which uses only permissible weights on each element y ∈ V ∪ E. It is known that every tree is (2, 2)-total-weight-choosable and every tree other than K2 is (1, 3)-total-weight-choosable. However, the problem of determining which trees are (1, 2)-total-weight-choosable remained open. This paper solves this problem and characterizes all (1, 2)-total-weight-choosable trees. Based on this characterization, we give an algorithm that determines in linear time whether a given tree is (1, 2)-total-weight-choosable. [ABSTRACT FROM AUTHOR]

We formalize the class of "sequential local algorithms" and show that these algorithms fail to find satisfying assignments on random instances of the "Not-All-Equal-K-SAT" (NAE-K-SAT) problem if the number of message passing iterations is bounded by a function moderately growing in the number of variables and if the clause-to-variable ratio is above (1 + oK(1)) 2K-1/K ln2 K for sufficiently large K. Sequential local algorithms are those that iteratively set variables based on some local information and/or local randomness and then recurse on the reduced instance. Our model captures some weak abstractions of natural algorithms such as Survey Propagation (SP)-guided as well as Belief Propagation (BP)-guided decimation algorithms-two widely studied message-passing-based algorithms-when the number of message-passing rounds in these algorithms is restricted to be growing only moderately with the number of variables. The approach underlying our paper is based on an intricate geometry of the solution space of a random NAE-K-SAT problem. We show that above the (1 +oK(1)) 2K-1 K ln2 K threshold, the overlap structure of m-tuples of nearly (in an appropriate sense) satisfying assignments exhibit a certain behavior expressed in the form of some constraints on pairwise distances between the m assignments for appropriately chosen positive integer m. We further show that if a sequential local algorithm succeeds in finding a satisfying assignment with probability bounded away from zero, then one can construct an m-tuple of solutions violating these constraints, thus leading to a contradiction. Along with [D. Gamarnik and M. Sudan, Ann. Probab., to appear], where a similar approach was used in a (somewhat simpler) setting of nonsequential local algorithms, this result is the first work that directly links the overlap property of random constraint satisfaction problems to the computational hardness of finding satisfying assignments. [ABSTRACT FROM AUTHOR]

Let G be an interval graph and take one of its vertices x. Can we find in linear time a minimum number of vertex disjoint paths of G which cover the vertex set of G and have x as one of their endpoints? This paper provides a positive answer to this problem. In the course of developing such an algorithm, we explore the possibility of getting insight on the path structure of interval graphs via greedy graph searches. [ABSTRACT FROM AUTHOR]

A seminal result of Reed et al. [Combinatorica, 16 (1996), pp. 535-554] says that a directed graph has either k vertex-disjoint directed circuits or a set of at most f(k) vertices meeting all directed circuits. This paper aims at generalizing their result to packing directed circuits through a prescribed set S of vertices. Such a circuit is called an S-circuit. Even et al. [Algorithmica, 20 (1998), pp. 151-174] showed a fractional version of packing S-circuits. In this paper, we show that the fractionality can be bounded by at most one-fifth: Given an integer k and a vertex subset S, whose size may not depend on k, we prove that either G has a 1/5-integral packing of k disjoint S-circuits, i.e., each vertex appears in at most five of these S-circuits, or G has a vertex set X of order at most f(k) (for some function f of k) such that G - X has no such circuit. We also give a fixed-parameter tractable approximation algorithm for finding a 1/5-integral packing of S-circuits. This algorithm finds a 1/5-integral packing of size approximately k in polynomial time if it has a 1/5-integral packing of size k for a given directed graph and an integer k. [ABSTRACT FROM AUTHOR]

This paper deals with cooperative games in which only certain coalitions are allowed to form. There have been previous models developed to confront the problem of nonfeasible coalitions. Games restricted by a communication graph are games in which the feasible coalitions are those that induce connected subgraphs. Another type of model is determined by the positions of the players in a so-called permission structure. In this paper, the restrictions to the cooperation are given by a combinatorial structure called an augmenting system which generalizes antimatroid structure and the system of Connected subgraphs of a graph. Furthermore, the class of augmenting systems includes the conjunctive and disjunctive systems derived from a permission structure. The value is a generalization of the Myerson value for games restricted by graphs and the Shapley value for gaines restricted by permission structures. The main results of the paper are the characterization of the value a for augmenting structures by using component efficiency, loop-null and balanced contributions, and another characterization by consistency of this value. Furthermore, we implement a direct algorithm to compute this value by using the outputs of the original game. [ABSTRACT FROM AUTHOR]

Given a graph G and a spanning tree T of G, we say that T is a tree t-spanner of G if the distance between every pair of vertices in T is at most t times their distance in G. The problem of finding a tree t-spanner minimizing t is referred to as the Minimum Max-Stretch spanning Tree (MMST) problem. This paper concerns the MMST problem on unweighted graphs. The problem is known to be NP-hard, and the paper presents an O(log n)-approximation algorithm for it. Furthermore, it is established that unless P = NP, the problem cannot be approximated additively by any o(n) term. [ABSTRACT FROM AUTHOR]

The problem of characterizing all the testable graph properties is considered by many to be the most important open problem in the area of property testing. Our main result in this paper is a solution of an important special case of this general problem: Call a property tester oblivious if its decisions are independent of the size of the input graph. We show that a graph property P has an oblivious one-sided error tester if and only if P is semihereditary. We stress that any "natural" property that can be tested (either with one-sided or with two-sided error) can be tested by an oblivious tester. In particular, all the testers studied thus far in the literature were oblivious. Our main result can thus be considered as a precise characterization of the natural graph properties, which are testable with one-sided error. One of the main technical contributions of this paper is in showing that any hereditary graph property can be tested with one-sided error. This general result contains as a special case all the previous results about testing graph properties with one-sided error. More importantly, as a special case of our main result, we infer that some of the most well-studied graph properties, both in graph theory and computer science, are testable with one-sided error. Some of these properties are the well-known graph properties of being perfect, chordal, interval, comparability, permutation, and more. None of these properties was previously known to be testable. [ABSTRACT FROM AUTHOR]

We investigate the approximability of several classes of real-valued functions by functions of a small number of variables (juntas). Our main results are tight bounds on the number of variables required to approximate a function f : {0, 1}n → [0,1] within l2-error ϵ over the uniform distribution: (a) If f is submodular, then it is ϵ-close to a function of Ω(1/→2log 1/ϵ) variables. This is an exponential improvement over previously known results [V. Feldman, P. Kothari, and J. Vondrak, JMLR Workshop Conf. Proc., 35 (2013), pp. 711-740]. We note that Ω(1/→2) variables are necessary even for linear functions. (b) If f is fractionally subadditive (XOS) it is e-close to a function of 2°(1/ϵ2 ) variables. This result holds for all functions with low total l1-influence and is a real-valued generalization of Friedgut's theorem for Boolean functions. We show that 2Ω(1/ϵ) variables are necessary even for XOS functions. As applications of these results, we provide learning algorithms over the uniform distribution. For XOS functions, we give a probably approximately correct learning algorithm that runs in time 21/poly(ϵ)poly(n). For submodular functions we give an algorithm in the more demanding probably mostly approximately correct (PMAC) learning model [M. F. Balcan and N. Harvey, preprint, arXiv:1008.2159, 2012] which requires a multiplicative (1+ γ) factor approximation with probability at least 1 - ϵ over the target distribution. Our uniform distribution algorithm runs in time 21/poly(γϵ)poly(n). This is the first algorithm in the PMAC model that can achieve a constant approximation factor arbitrarily close to 1 for all submodular functions (even over the uniform distribution). It relies crucially on our bounds for approximation by juntas. As follows from the lower bounds in the above paper by Feldman, Kothari, and Vondraak both of these algorithms are close to optimal. We also give applications for proper learning, testing, and agnostic learning of these classes. [ABSTRACT FROM AUTHOR]

In the PROPER INTERVAL COMPLETION problem we are given a graph G and an integer k, and the task is to turn G using at most k edge additions into a proper interval graph, i.e., a graph admitting an intersection model of equal-length intervals on a line. The study of PROPER INTERVAL COMPLETION from the viewpoint of parameterized complexity has been initiated by Kaplan, Shamir, and Tarjan [SIAM J. Comput., 28 (1999), pp. 1906-1922], who showed an algorithm for the problem working in O(16k (n+m)) time. In this paper we present an algorithm with running time kO(k2/3) + O(nm(kn + m)), which is the first subexponential parameterized algorithm for PROPER INTERVAL COMPLETION. [ABSTRACT FROM AUTHOR]

Let G = (V,E) be an undirected unweighted graph on n vertices. A subgraph H of G is called a purely additive spanner of G with stretch β if for each (u, v) ∈ V ×V , the u-v distance in H is at most δG(u, v) + β. We currently know sparse purely additive spanners with β = O(1) only for β = 2, 4, 6. When β = 2, the size of the spanner is O(n3/2); when β = 4, the size of the spanner is O(n1.4 log0.2 n); and when β = 6, the size of the spanner is O(n4/3). The following is a natural relaxation of the above problem: we care for only certain distances, these are captured by the set P ⊆ V × V , and the problem is to construct a sparse subgraph H (also called a P-spanner), where for every (u, v) ∈ P, the u-v distance in H is at most δG(u, v) + β. In this paper we show algorithms to construct the following for β = 2: a P-spanner of size Õ (n|P|1/3) for any P ⊆ V × V and a P-spanner of size Õ(n|P|1/4) when P = S × V , where S ⊆ V. Our P-spanner with additive stretch 2 leads to a simple deterministic construction of a purely additive spanner with stretch 4 and size O(n1.4 log0.2 n). We also consider a variant of the P-spanner problem where the set P is implicitly given via a distance threshold D. That is, P = {(u, v) : δG(u, v) ≥ D}. We refer to such a P-spanner as an approximate D-preserver. A D-preserver is a subgraph where distances ≥ D are exactly preserved and D-preservers of size O(n2 / D) are known. For a given D ∈ ℤ+ and any integer k ≥ 1, we construct an Õ(n3/2/Dk/(2k+2))-sized subgraph where distances ≥ D are approximated with an additive stretch of 4k. In particular, when k = [log D], this subgraph has size Õ(n.√n/D). [ABSTRACT FROM AUTHOR]

Let λ(N) denote the weight of a minimum cut in an edge-weighted undirected network N, and n and m denote the numbers of vertices and edges, respectively. It is known that O(n2k) is an upper bound on the number of cuts with weights less than kλ(N), where k ≥ 1 is a given constant. This paper first shows that all cuts of weights less than kλ(N) can be enumerated in O(m²n + n2km) time without using the maximum flow algorithm. The paper then proves for k < 4/3 that (n 2) is a tight upper bound on the number of cuts of weights less than kλ(N), and that all those cuts can be enumerated in O(m²n + mn² log n) time. [ABSTRACT FROM AUTHOR]

Many applications require efficient methods for solving continuous shortest path problems. Such paths can be viewed as characteristics of static Hamilton-Jacobi equations. Several fast numerical algorithms have been developed to solve such equations on the whole domain. In this paper, we consider a somewhat different problem, where the solution is needed at one specific point, so we restrict the computations to a neighborhood of the characteristic. We explain how heuristic under/over-estimate functions can be used to obtain a causal domain restriction, significantly decreasing the computational work without sacrificing convergence under mesh refinement. The discussed techniques are inspired by an alternative version of the classical A* algorithm on graphs. We illustrate the advantages of our approach on continuous isotropic examples in two and three dimensions. We compare its efficiency and accuracy to previous domain restriction techniques. We also analyze the behavior of errors under the grid refinement and show how Lagrangian (Pontryagin's maximum principle-based) computations can be used to enhance our method. [ABSTRACT FROM AUTHOR]

Graphs and networks are used to model interactions in a variety of contexts. There is a growing need to quickly assess the characteristics of a graph in order to understand its underlying structure. Some of the most useful metrics are triangle-based and give a measure of the connectedness of mutual friends. This is often summarized in terms of clustering coefficients, which measure the likelihood that two neighbors of a node are themselves connected. Computing these measures exactly for large-scale networks is prohibitively expensive in both memory and time. However, a recent wedge-sampling algorithm has proved successful in efficiently and accurately estimating clustering coefficients. In this paper, we describe how to implement this approach in MapReduce to deal with massive graphs. We show results on publicly available networks, the largest of which is 132M nodes and 4.7B edges, as well as artificially generated networks (using the Graph500 benchmark), the largest of which has 240M nodes and 8.5B edges. We can estimate the clustering coefficient by degree bin (e.g., we use exponential binning) and the number of triangles per bin, as well as the global clustering coefficient and total number of triangles, in an average of 0.33 seconds per million edges plus overhead (approximately 225 seconds total for our configuration). The technique can also be used to study triangle statistics such as the ratio of the highest and lowest degree, and we highlight differences between social and nonsocial networks. To the best of our knowledge, these are the largest triangle-based graph computations published to date. [ABSTRACT FROM AUTHOR]

The matching forest problem in mixed graphs is a common generalization of the matching problem in undirected graphs and the branching problem in directed graphs. Giles presented an O(n²m)-time algorithm for finding a maximum-weight matching forest, where n is the number of vertices and m is that of edges, and a linear system describing the matching forest polytope. Later, Schrijver proved total dual integrality of the linear system. In the present paper, we reveal another nice property of matching forests: the degree sequences of the matching forests in any mixed graph form a delta-matroid, and the weighted matching forests induce a valuated delta-matroid. We remark that the delta-matroid is not necessarily even, and the valuated delta-matroid induced by weighted matching forests slightly generalizes the well-known notion of Dress and Wenzel's valuated delta-matroids. By focusing on the delta-matroid structure and reviewing Giles' algorithm, we design a simpler O(n²m)-time algorithm for the weighted matching forest problem. By incorporating Gabow's method for the weighted matching problem into Giles' algorithm, we also present a faster algorithm for the weighted matching forest problem running in O(n³)-time, which improves upon the previous best complexity of O(n² m). [ABSTRACT FROM AUTHOR]

Let g(t) be the minimum number such that every graph G with average degree d(G) ≥ g(t)containsa Kt-minor. Such a function is known to exist, as originally shown by Mader. Kostochka and Thomason independently proved that g(t) ∈ Θ(t √log t). This paper shows that for all fixed ε > 0 and fixed sufficiently large t ≥ t(ε), if d(G) ≥ (2 + ε)g(t), then we can find this Kt-minor in linear time. This improves a previous result by Reed and Wood who gave a linear-time algorithm when d(G) ≥ 2t-2. [ABSTRACT FROM AUTHOR]

For a graph G and for each vertex v ∈ V (G), let Λ[sub G](v)= {EG(v, 1),E[sub G](v, 2),..., E[sub G](v, κ[sub v])} be a partition of the edges incident with v. Let ΛG = {ΛG(v) | v ∈ V (G)}. We call the pair (G, ΛG) a partitioned graph. Let κ = maxv κv and let g, f : V (G) x {1,..., κ} → ℕ and t, u : V (G) → ℕ be functions where, for all vertices v ∈ V (G), (i) g(v, i) ≤ f(v, i) ≤ dG(v, i) i = 1,..., κv, (ii) ... and ... . A subgraph H of the partitioned graph is said to be a (g, f, u, t)-factor if all vertices v ∈ V (G) satisfy(a) g(v, i) ≤ dH(v, i) ≤ f(v, i),i =1,..., κv and (b) u(v) ≤ dH (v) ≤ t(v), where dH(v, i)= |E(H) ∩ EG(v, i)|. In this paper, we shall show via a reduction to a matching problem, that there is a good algorithm for determining whether a partitioned graph has a (g, f, u, t)-factor. Second, we shall also prove a theorem which characterizes the existence of (0, f, t, u)-factors in a partitioned graph when u(v)

For graph G(V,E), a minimum path cover (MPC) is a minimum cardinality set of vertex disjoint paths that cover V (i.e., every vertex of G is in exactly one path in the cover). This problem is a natural generalization of the Hamiltonian path problem. Cocomparability graphs (the complements of graphs that have an acyclic transitive orientation of their edge sets) are a well studied subfamily of perfect graphs that includes many popular families of graphs such as interval, permutation, and cographs. Furthermore, for every cocomparability graph G and acyclic transitive orientation of the edges of G there is a corresponding poset PG; it is easy to see that an MPC of G is a linear extension of PG that minimizes the bump number of PG. Although there are directly graphtheoretical MPC algorithms (i.e., algorithms that do not rely on poset formulations) for various subfamilies of cocomparability graphs, notably interval graphs, until now all MPC algorithms for cocomparability graphs themselves have been based on the bump number algorithms for posets. In this paper we present the first directly graph-theoretical MPC algorithm for cocomparability graphs; this algorithm is based on two consecutive graph searches followed by a certifying algorithm. Surprisingly, except for a lexicographic depth first search (LDFS) preprocessing step, this algorithm is identical to the corresponding algorithm for interval graphs. The running time of the algorithm is O(min(n², n + mloglogn)), with the nonlinearity coming from LDFS. [ABSTRACT FROM AUTHOR]

The girth of a graph is the minimum weight of all simple cycles of the graph. We study the problem of determining the girth of an n-node unweighted undirected planar graph. The first nontrivial algorithm for the problem, given by Djidjev, runs in O(n5/4 log n) time. Chalermsook, Fakcharoenphol, and Nanongkai reduced the running time to O(n log² n). Weimann and Yuster further reduced the running time to O(n log n). In this paper, we solve the problem in O(n) time. [ABSTRACT FROM AUTHOR]

In this paper we are interested in algorithms for finding 2-factors that cover certain prescribed edge-cuts in bridgeless cubic graphs. Since a Hamilton cycle is a 2-factor covering all edge-cuts, imposing the constraint of covering those edge-cuts makes the obtained 2-factor closer to a Hamilton cycle. We present an algorithm for finding a minimum-weight 2-factor covering all the 3-edge cuts in weighted bridgeless cubic graphs, together with a polyhedral description of such 2-factors and that of perfect matchings intersecting all the 3-edge cuts in exactly one edge. We further give an algorithm for finding a 2-factor covering all the 3- and 4-edge cuts in bridgeless cubic graphs. Both of these algorithms run in O(n³) time, where n is the number of vertices. As an application of the latter algorithm, we design a 6/5-approximation algorithm for finding a minimum 2-edge-connected spanning subgraph in 3-edge-connected cubic graphs, which improves upon the previous best ratio of 5/4. The algorithm begins with finding a 2-factor covering all 3- and 4-edge cuts, which is the bottleneck in terms of complexity, and thus it has running time O(n³). We then improve this time complexity to O(n²log4n) by relaxing the condition of the initial 2-factor and elaborating on the subsequent processes. [ABSTRACT FROM AUTHOR]

In this paper we present a unifying geometric and compositional framework for modeling complex physical network dynamics as port-Hamiltonian systems on open graphs. The basic idea is to associate with the incidence matrix of any directed graph a Dirac structure relating the flow and effort variables associated to the edges and vertices of the graph, and to formulate energy-storing or energy-dissipating relations between the flow and effort variables of the edges and the internal vertices. This allows for state variables associated to the edges and formalizes the interconnection of networks. Examples from different origins, such as consensus algorithms, that share the same structure are shown. It is shown how the identified Hamiltonian structure offers systematic tools for the analysis and control of the resulting dynamics. [ABSTRACT FROM AUTHOR]

In this paper, we study the impact of edge weights on distances in sparse random graphs. We interpret these weights as delays and take them as independent and identically distributed exponential random variables. We analyze the weighted flooding time defined as the minimum time needed to reach all nodes from one uniformly chosen node and the weighted diameter corresponding to the largest distance between any pair of vertices. Under some standard regularity conditions on the degree sequence of the random graph, we show that these quantities grow as the logarithm of n when the size of the graph n tends to infinity. We also derive the exact value for the prefactor. These results allow us to analyze an asynchronous randomized broadcast algorithm for random regular graphs. Our results show that the asynchronous version of the algorithm performs better than its synchronized version: in the large size limit of the graph, it will reach the whole network faster even if the local dynamics are similar on average. [ABSTRACT FROM AUTHOR]

The classical Feedback Vertex Set problem asks, for a given undirected graph G and an integer k, to find a set of at most k vertices that hits all the cycles in the graph G. Feedback Vertex SET has attracted a large amount of research in the parameterized setting, and subsequent fixed-parameter and kernelization algorithms have been a rich source of ideas in the field. In this paper we consider a more general and difficult version of the problem, named Subset Feedback Vertex SET (Subset-FVS), where an instance comes additionally with a set S ⊆ V of vertices, and we ask for a set of at most k vertices that hits all simple cycles passing through S. Because of its applications in circuit testing and genetic linkage analysis, Subset-FVS was studied from the approximation algorithm perspective by Even et al. [SIAM J. Discrete Math., 13 (2000), pp. 225-267; SIAM J. Comput., 30 (2000), pp. 1231-1252]. The question of whether the Subset-FVS problem is fixed-parameter tractable was posed independently by Kawarabayashi and Saurabh in 2009. We answer this question affirmatively. We begin by showing that this problem is fixed-parameter tractable when parameterized by |S|. Next we present an algorithm which reduces the given instance to 2knO(1) instances with the size of S bounded by O(k³), using kernelization techniques such as the 2-expansion lemma, Menger's theorem, and Gallai's theorem. These two facts allow us to give a 2O(k log k)nO(1) time algorithm solving the Subset-FVS problem, proving that it is indeed fixed-parameter tractable. [ABSTRACT FROM AUTHOR]

Gathering data from nodes in a network is at the heart of many distributed applications, most notably while performing a global task. We consider information spreading among n nodes of a network, where each node v has a message m(v) which must be received by all other nodes. The time required for information spreading has been previously upper-bounded with an inverse relationship to the conductance of the underlying communication graph. This implies high running time bounds for graphs with small conductance. The main contribution of this paper is an information spreading algorithm which overcomes communication bottlenecks and thus achieves fast information spreading for a wide class of graphs, despite their small conductance. As a key tool in our study we use the recently defined concept of weak conductance, a generalization of classic graph conductance which measures how well-connected the components of a graph are. Our hybrid algorithm, which alternates between random and deterministic communication phases, exploits the connectivity within components by first applying partial information spreading, in which information is exchanged within well-connected components, and then sending messages across bottlenecks, thus spreading further throughout the network. This yields substantial improvements over the best known running times of algorithms for information spreading on any graph that has large weak conductance, from a polynomial to a polylogarithmic number of rounds. [ABSTRACT FROM AUTHOR]

We show that for a fixed r, the number of maximal r-regular induced subgraphs in any graph with n vertices is upper bounded by O(cn), where c is a positive constant strictly less than 2. This bound generalizes the well-known result of Moon and Moser, who showed an upper bound of 3n/3 on the number of maximal independent sets of a graph on n vertices. We complement this upper bound result by obtaining an almost tight lower bound on the number of (possible) maximal r-regular induced subgraphs possible in a graph on n vertices. Our upper bound results are algorithmic. That is, we can enumerate all the maximal r-regular induced subgraphs in time (cnnO(1)). A related question is that of finding a maximum-sized r-regular induced subgraph. Given a graph G =(V,E) on n vertices, the Maximum r-Regular Induced Subgraph (M-r-RIS) problem asks for a maximum-sized subset of vertices, R ⊆ V, such that the induced subgraph on R is r-regular. As a by-product of the enumeration algorithm, we get a O (cn) time algorithm for this problem for any fixed constant r, where c is a positive constant strictly less than 2. Furthermore, we use the techniques and results obtained in the paper to obtain improved exact algorithms for a special case of the Induced Subgraph Isomorphism problem, namely, the Induced r-Regular Subgraph Isomorphism problem, where r is a constant, the δ-Separating Maximum Matching problem and the Efficient Edge Dominating Set problem. [ABSTRACT FROM AUTHOR]

Given a graph G, the longest path problem asks to compute a simple path of G with the largest number of vertices. This problem is the most natural optimization version of the well-known and well-studied Hamiltonian path problem, and thus it is NP-hard on general graphs. However, in contrast to the Hamiltonian path problem, there are only a few restricted graph families, such as trees, and some small graph classes where polynomial algorithms for the longest path problem have been found. Recently it has been shown that this problem can be solved in polynomial time on interval graphs by applying dynamic programming to a characterizing ordering of the vertices of the given graph [K. Ioannidou, G. B. Mertzios, and S. D. Nikolopoulos, Algorithmica, 61 (2011), pp. 320-341], thus answering an open question. In the present paper, we provide the first polynomial algorithm for the longest path problem on a much greater class, namely on cocomparability graphs. Our algorithm uses a similar, but essentially simpler, dynamic programming approach, which is applied to a lexicographic depth first search (LDFS) characterizing ordering of the vertices of a cocomparability graph. Therefore, our results provide evidence that this general dynamic programming approach can be used in a more general setting, leading to efficient algorithms for the longest path problem on greater classes of graphs. LDFS has recently been introduced in [D. G. Corneil and R. M. Krueger, SIAM J. Discrete Math., 22 (2008), pp. 1259-1276]. Since then, a similar phenomenon of extending an existing interval graph algorithm to cocomparability graphs by using an LDFS preprocessing step has also been observed for the minimum path cover problem [D. G. Corneil, B. Dalton, and M. Habib, submitted]. Therefore, more interestingly, our results also provide evidence that cocomparability graphs present an interval graph structure when they are considered using an LDFS ordering of their vertices, which may lead to other new and more efficient combinatorial algorithms. [ABSTRACT FROM AUTHOR]

In this paper we consider a q-ary extension of the classical binary addressing problem of graphs which was originally posed by Graham and Pollak [Bell System Tech. J., 50 (1971), pp. 2495--2519]. A lower bound for the minimum length of addressings is presented in terms of eigenvalues of distance matrices. The bound is sharp for complete graphs and r-hypertrees but not for the Petersen graph. The determinant of the distance matrices of r-hypertrees is explicitly calculated, as a generalization of beautiful theorems by Graham and Pollak and Sivasubramanian [Linear Algegra Appl., 431 (2009), pp. 1234--1248] on trees and 3-hypertrees. The q-ary addressings are applied to the decomposition of the complete graphs. We give an alternative proof of the Liu-- Schwenk theorem [Congr. Numer., 81 (1991), pp. 129--142] on the decomposition of the complete graphs into edge-disjoint complete multipartite graphs. [ABSTRACT FROM AUTHOR]

A graph with at least 2k vertices is said to be k-linked if for any two ordered k-tuples (s1,…, sk) and (t1,…,tk) of 2k distinct vertices, there exist pairwise vertex-disjoint paths P1,…,Pk such that Pi connects si and ti for i = 1,…,k. For a given graph G, we consider the problem of finding a maximum induced subgraph of G that is not k-linked. This problem is a common generalization of computing vertex-connectivity and testing k-linkedness of G, and it is closely related to the concept of H-linkedness. In this paper, we give the first polynomial-time algorithm for the case of k = 2, whereas a similar problem to find a maximum induced subgraph without 2-vertex-disjoint paths connecting fixed terminal pairs is NP-hard. For the case of general k, we give an (8k -- 2)-additive approximation algorithm. We also investigate the computational complexity of the edge-disjoint case and the directed case. [ABSTRACT FROM AUTHOR]

A graph G is claw-free if no induced subgraph of it is isomorphic to the complete bipartite graph K1,3, and it is prime if |V(G)| ≥ 4 and there is no X „ V(G) with 1 < |X| < |V(G)| such that every vertex of V(G) \ X with a neighbor in X is adjacent to every vertex of X. In particular, if G is prime, then both G and Gc are connected. This paper has two main results. The first one is that if G is a prime graph that is not a member of a particular family of exceptions, and H is a prime induced subgraph of G, then (up to isomorphism) G can be grown from H, adding one vertex at a time, in such a way that all the graphs constructed along the way are prime induced subgraphs of G. A simplicial clique in G is a nonempty clique K such that for every k ∈ K the set of neighbors of k in V(G) \ K is a clique. Our second result is that a prime claw-free graph G has at most |V(G)| + 1 simplicial cliques, and we give an algorithm to find them all with running time O(|V(G)|4. In particular, this answers a question of Prasad Tetali [private communication] who asked if there is an efficient algorithm to test if a claw-free graph has a simplicial clique. Finally, we apply our results to claw-free graphs that are not prime. Such a graph may have exponentially many simplicial cliques, so we cannot list them all in polynomial time, but we can in a sense describe them. [ABSTRACT FROM AUTHOR]

Endo proved that every toroidal graph has a book embedding with at most seven pages. In this paper, we prove that every toroidal bipartite graph has a book embedding with at most five pages. In order to do so, we prove that every bipartite torus quadrangulation with Q n vertices admits two disjoint noncontractible simple closed curves cutting the torus into two annuli so that each of the two annuli contains a spanning connected subgraph of with exactly edges Q n satisfying a certain condition. [ABSTRACT FROM AUTHOR]

Amit, Linial, and Matoušek [Random Struct. Algorithms, 20 (2001), pp. 1-22] have raised the following question: Is the chromatic number of random h-lifts of K5 asymptotically (for h→∞) almost surely (a.a.s.) equal to a single number? In this paper, we offer the following partial result: The chromatic number of a random lift of K5\e is a.a.s. 3. [ABSTRACT FROM AUTHOR]

Let f : 2X→R+ be a monotone submodular set function, and let (X, L)be a matroid. We consider the problem maxSεIf(S). It is known that the greedy algorithm yields a 1/2-approximation [M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, Math. Programming Stud., no. 8 (1978), pp. 73-87] for this problem. For certain special cases, e.g., max|s|≤k f(S), the greedy algorithm yields a (1-1/e)-approximation. It is known that this is optimal both in the value oracle model (where the only access to f is through a black box returning f(S)f or a given set S) [G. L. Nemhauser and L. A. Wolsey, Math. Oper. Res., 3 (1978), pp. 177-188] and for explicitly posed instances assuming P ≠ NP [U. Feige, J. ACM, 45 (1998), pp. 634-652]. In this paper, we provide a randomized (1 - 1/e)-approximation for any monotone submodular function and an arbitrary matroid. The algorithm works in the value oracle model. Our main tools are a variant of the pipage rounding technique of Ageev and Sviridenko [J. Combin. Optim., 8 (2004), pp. 307-328], and a continuous greedy process that may be of independent interest. As a special case, our algorithm implies an optimal approximation for the submodular welfare problem in the value oracle model [J. Vondrák, Proceedings of the 38th ACM Symposium on Theory of Computing, 2008, pp. 67-74]. As a second application, we show that the generalized assignment problem (GAP) is also a special case; although the reduction requires |X| to be exponential in the original problem size, we are able to achieve a (1 -1/e - o(1))-approximation for GAP, simplifying previously known algorithms. Additionally, the reduction enables us to obtain approximation algorithms for variants of GAP with more general constraints. [ABSTRACT FROM AUTHOR]

In this paper, we conclude the calculation of the domination number of all (n, m) grid graphs. Indeed, we prove Chang's conjecture saying that for every 16 ≤ n ≤ m, γ(Gn, m) = [(n+2)(m+2)/5] - 4. [ABSTRACT FROM AUTHOR]

Detecting and counting the number of copies of certain subgraphs (also known as network motifs or graphlets) is motivated by applications in a variety of areas ranging from biology to the study of the World Wide Web. Several polynomial-time algorithms have been suggested for counting or detecting the number of occurrences of certain network motifs. However, a need for more efficient algorithms arises when the input graph is very large, as is indeed the case in many applications of motif counting. In this paper we design sublinear-time algorithms for approximating the number of copies of certain constant-size subgraphs in a graph G. That is, our algorithms do not read the whole graph, but rather query parts of the graph. Specifically, we consider algorithms that may query the degree of any vertex of their choice and may ask for any neighbor of any vertex of their choice. The main focus of this work is on the basic problem of counting the number of length-2 paths and more generally on counting the number of stars of a certain size. Specifically, we design an algorithm that, given an approximation parameter 0 < ε < 1 and query access to a graph G, outputs an estimate … such that with high constant probability, Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed., where v8(G) denotes the number of stars of size s + 1 in the graph. The expected query complexity and running time of the algorithm are Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed.. We also prove lower bounds showing that this algorithm is tight up to polylogarithmic factors in n and the dependence on ε. Our work extends the work of Feige [SIAM J. Comput., 35 (2006), pp. 964-984] and Goldreich and Ron [Random Structures Algorithms, 32 (2008), pp. 473-493] on approximating the number of edges (or average degree) in a graph. Combined with these results, our result can be used to obtain an estimate on the variance of the degrees in the graph and corresponding higher moments. In addition, we give some (negative) results on approximating the number of tri- angles and on approximating the number of length-3 paths in sublinear-time. [ABSTRACT FROM AUTHOR]

In this paper, we consider the half-integral disjoint paths packing. For a graph G and k pairs of vertices (s1, t1), (s2, t2), …, (sk, tk) in G, the objective is to find paths P1, …, Pk in G such that Pi joins si and ti for i = 1, 2, …, k, and in addition, each vertex is on at most two of these paths. We give a polynomial-time algorithm to decide the feasibility of this problem with k = O((log n/log log n)1/7). This improves a result by Kleinberg [Proceedings of the 30th ACM Symposium on Theory of Computing, 1998, pp 530-539] who proved the same conclusion when k = O((log log n)2/15). Our algorithm still works for several problems related to the bounded unsplittable flow. These results can all carry over to problems involving edge capacities. Our main technical contribution is to give a "crossbar" of a polynomial size of the tree width of the graph. [ABSTRACT FROM AUTHOR]

A graph is polar if its vertex set can be partitioned into A and B in such a way that A induces a complete multipartite graph and B induces a disjoint union of cliques (i.e., the complement of a complete multipartite graph). Polar graphs naturally generalize several classes of graphs such as bipartite, cobipartite, and split graphs. The problem of recognizing polar graphs is NP-complete in general. However, it has been shown to be polynomial for several classes of graphs, including cographs and chordal graphs. In this paper, we study the problem of recognizing graphs whose line graphs are polar. It turns out that the core part of this problem lies in determining whether the edge set of a graph admits a partition (A, B) so that A induces a P3-free subgraph (i.e., a matching) and B induces a P4-free subgraph. We give a structural characterization of such graphs. The characterization enables us to devise an O(n) time algorithm to solve the stated recognition problem. [ABSTRACT FROM AUTHOR]

In this paper we consider two basic questions regarding the query complexity of testing graph properties in the adjacency matrix model. The first question refers to the relation between adaptive and nonadaptive testers, whereas the second question refers to testability within complexity that is inversely proportional to the proximity parameter, denoted ∈. The study of these questions reveals the importance of algorithmic design in this model. The highlights of our study are as follows: (a) A gap between the complexity of adaptive and nonadaptive testers. Specifically, there exists a natural graph property that can be tested using Õ(∈-1) adaptive queries but cannot be tested using o(∈ -3/2) nonadaptive queries, (b) In contrast, there exist natural graph properties that can be tested using Õ(∈-1) nonadaptive queries, whereas Ω(∈-1) queries are required even in the adaptive case. We mention that the properties used in the foregoing conflicting results have a similar flavor, although they are of course different. [ABSTRACT FROM AUTHOR]

In this paper we discuss a hypergraph-based unsymmetric nested dissection (HUND) ordering for reducing the fill-in incurred during Gaussian elimination. It has several important properties. It takes a global perspective of the entire matrix, as opposed to local heuristics. It takes into account the asymmetry of the input matrix by using a hypergraph to represent its structure. It is suitable for performing Gaussian elimination in parallel, with partial pivoting. This is possible because the row permutations performed due to partial pivoting do not destroy the column separators identified by the nested dissection approach. The hypergraph nested dissection approach is essentially equivalent to graph nested dissection on the matrix AT A, but we need only the original matrix A and never form the usually denser matrix ATA. The usage of hypergraphs in our approach is fairly standard, and HUND can be implemented by calling an existing hypergraph partitioner that uses recursive bisection. Our implementation uses local reordering constrained column approximate minimum degree (CCOLAMD) to further improve the ordering. We also explain how weighted matching (HSL routine MC64) can be used in this context. Experimental results on 27 medium and large size matrices with highly unsymmetric structures compare our approach to four other well-known reordering algorithms. The results show that it provides a robust reordering algorithm, in the sense that it is the best or close to the best (often within 10%) of all the other methods, in particular on matrices with highly unsymmetric structures. [ABSTRACT FROM AUTHOR]

Parallel simulations at extreme scale require that the mesh is distributed across a large number of processors with equal work load and minimum interpart communications. A number of algorithms have been developed to meet these goals, e.g., graph/hypergraph and coordinate- based methods. However, the global implementation of current approaches Call fail oil very large core counts, which is resolved by combining global and local partitioning using multiple parts per processor. The other limitation of graph/hypergraph-based partitioning is that it uses one type of mesh entity as graph nodes; thus, the balance of other mesh entities may not be optimal. In the case of three-dimensional (3-D) linear finite element analysis, it is common to select mesh regions (elements) as partition objects. In current examples, the regions axe well balanced up to 163,840 parts for a 1.07 billion element mesh, while the vertices have an imbalance which is as high as 19.52%. Two methods are developed that work in conjunction with graph/hypergraph-based procedures to provide improved partitions. Example computations executed on an IBM Blue Gene/P system using up to 163,840 cores demonstrate the usefulness of the procedures, particularly for time-critical calculations where individual cores may be lightly loaded in terms of the number of mesh entities per core. The algorithms presented in this paper reduced the vertex imbalance from 17.8% to 4.97% for a partition with 131,072 parts and accelerated the equation solution phase of the finite element analysis by 10.4%. [ABSTRACT FROM AUTHOR]

In his seminal work, Kleinberg showed how to augment meshes using random edges, so that they become navigable; that is, greedy routing computes paths of polylogarithmic expected length between any pairs of nodes. This yields the crucial question of determining whether such an augmentation is possible for all graphs. In this paper, we answer this question negatively by exhibiting an infinite family of graphs that cannot be augmented to become navigable whatever the distribution of random edges is. Precisely, it was known that graphs of doubling dimension at most O(log log n) are navigable. We show that for doubling dimension ⪢ log log n, an infinite family of graphs cannot be augmented to become navigable. Finally, we present a positive navigability result by studying the special case of square meshes of arbitrary dimension that we prove to always be augmentable to become navigable. This latter result complements Kleinberg's original result and shows that adding extra links can sometimes break the navigability. [ABSTRACT FROM AUTHOR]

A digraph is upward planar if it admits a planar drawing where all edges are monotone in the upward direction. It is known that the problem of testing a digraph for upward planarity is NP-complete in general. This paper describes an O(n4)-time upward planarity testing algorithm for all digraphs that have a series-parallel structure, where n is the number of vertices of the input. This significantly enlarges the family of digraphs for which a polynomial-time testing algorithm is known. Furthermore, the study is extended to general digraphs, and a fixed parameter tractable algorithm for upward planarity testing is described, whose time complexity is O(dt · t · n3 + d · t2 · n + d2 · n2) where t is the number of triconnected components of the digraph and d is an upper bound on the diameter of any split component of the digraph. Our results use the new notion of upward spirality that, informally speaking, is a measure of the "level of winding" that a triconnected component of a digraph G can have in an upward planar drawing of G. [ABSTRACT FROM AUTHOR]

In this paper, we provide a detailed comparison between a fully randomized protocol for rumor spreading on a complete graph and a quasirandom protocol introduced by Doerr, Friedrich, and Sauerwald [Quasirandom rumor spreading, in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2008, pp. 773-781]. In the former, initially there is one vertex which holds a piece of information, and during each round every one of the informed vertices chooses uniformly at random and independently one of its neighbors and informs it. In the quasirandom version of this method (cf. Doerr, Friedrich, and Sauerwald) each vertex has a cyclic list of its neighbors. Once a vertex has been informed, it chooses uniformly at random only one neighbor. In the following round, it informs this neighbor, and at each subsequent round it picks the next neighbor from its list and informs it. We give a precise analysis of the evolution of the quasirandom protocol on the complete graph with n vertices and show that it evolves essentially in the same way as the randomized protocol. In particular, if S(n) denotes the number of rounds that are needed until all vertices are informed, we show that for any slowly growing function w(n), we have log2 n + ln n - 4 ln ln n ≤ S(n) = log2 n + ln n + w(n), with probability 1 - o(1). [ABSTRACT FROM AUTHOR]

A graph is an interval graph if it is the intersection graph of intervals on a line. Interval graphs are known to be the intersection of chordal graphs and asteroidal triple-free graphs, two families where the well-known lexicographic breadth first search (LBFS) plays an important algorithmic and structural role. In this paper we show that interval graphs have a very rich LBFS structure and that by exploiting this structure one can design a linear time, easily implementable, interval graph recognition algorithm. [ABSTRACT FROM AUTHOR]

We study the maximum edge-disjoint paths problem in undirected planar graphs: given a graph G and node pairs (demands) s1t1, s2t2, … , sktk, the goal is to maximize the number of demands that can be connected (routed) by edge-disjoint paths. The natural multicommodity flow relaxation has an Ω(√n) integrality gap, where n is the number of nodes in G. Motivated by this, we consider solutions with small constant congestion c > 1, that is, solutions in which up to c paths are allowed to use an edge (alternatively, each edge has a capacity of c). In previous work we obtained an O(log n) approximation with congestion 2 via the flow relaxation. This was based on a method of decomposing into well-linked subproblems. In this paper we obtain an O(1) approximation with congestion 4. To obtain this improvement we develop an alternative decomposition that is specific to planar graphs. The decomposition produces instances that we call Okamura-Seymour (OS) instances. These have the property that all terminals lie on a single face. Another ingredient we develop is a constant factor approximation for the all-or-nothing flow problem on OS instances via the flow relaxation. [ABSTRACT FROM AUTHOR]