Search

A (β; ε)-hopset for a weighted undirected n-vertex graph G = (V,E) is a set of edges, whose addition to the graph guarantees that every pair of vertices has a path between them that contains at most β edges, whose length is within 1 + ε of the shortest path. In her seminal paper, Cohen [J. ACM, 47 (2000), pp. 132-166] introduced the notion of hopsets in the context of parallel computation of approximate shortest paths, and since then it has found numerous applications in various settings, such as dynamic graph algorithms, distributed computing, and the streaming model. Cohen [J. ACM, 47 (2000), pp. 132-166] devised efficient algorithms for constructing hopsets with polylogarithmic in n number of hops. Her constructions remain the state of the art since the publication of her paper in the proceedings of STOC'94, i.e., for more than two decades. In this paper we exhibit the first construction of sparse hopsets with a constant number of hops. We also find efficient algorithms for hopsets in various computational settings, improving the best-known constructions. Generally, our hopsets strictly outperform the hopsets of [J. ACM, 47 (2000), pp. 132-166] in terms of both their parameters and the resources required to construct them. We demonstrate the applicability of our results for the fundamental problem of computing approximate shortest paths from s sources. Our results improve the running time for this problem in the parallel, distributed, and streaming models for a vast range of s. [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]

Intersection graphs of geometric objects have been extensively studied, due to both their interesting structure and their numerous applications; prominent examples include interval graphs and permutation graphs. In this paper we study a natural graph class that generalizes both interval and permutation graphs, namely simple-triangle graphs. Simple-triangle graphs--also known as PI (point-interval) graphs--are the intersection graphs of triangles that are defined by a point on a line L1 and an interval on a parallel line L2. They lie naturally between permutation and trapezoid graphs, which are the intersection graphs of line segments between L1 and L2 and of trapezoids between L1 and L2, respectively. Although various efficient recognition algorithms for permutation and trapezoid graphs are well known to exist, the recognition of simple-triangle graphs has remained an open problem since their introduction by Corneil and Kamula three decades ago. In this paper we resolve this problem by proving that simple-triangle graphs can be recognized in polynomial time. Given a graph G with n vertices, such that its complement G has m edges, our algorithm runs in O(n²m) time. As a consequence, our algorithm also solves a longstanding open problem in the area of partial orders, namely, the recognition of linear-interval orders, i.e., of partial orders P = P1 ∩ P2, where P1 is a linear order and P2 is an interval order. This is one of the first results on recognizing partial orders P that are the intersection of orders from two different classes P1 and P2 . In complete contrast to this, partial orders P which are the intersection of orders from the same class P have been extensively investigated, and in most cases the complexity status of these recognition problems has been already established. [ABSTRACT FROM AUTHOR]

In the Subset Odd Cycle Transversal (Subset OCT) problem, the input is a graph G, a subset of vertices T and a positive integer k and the objective is to determine whether there exists a k-sized vertex subset that intersects every odd cycle containing a vertex from T. Clearly, Subset OCT is a generalization of the classic Odd Cycle Transversal problem where the objective is to determine whether there exists a k-sized vertex subset that intersects every odd cycle in the given graph. We remark that Subset OCT also generalizes the well known Multiway Cut problem, as well as a parity constrained variant, the Odd Multiway Cut problem. Recently, Kakimura, Kawarabayashi, and Kobayashi [Proceedings of SODA, 2012, pp. 1726{1736] proposed a fixed parameter tractable (FPT) algorithm for this problem that runs in time ƒ(k)mn³ using the theory of graph minors, where ƒ is some function, and n and m denote the number of vertices and edges in the graph. However, the dependence of this function on k is at least triple exponential. In this paper, we give the first FPT algorithm for this problem where the exponential dependence of the running time of the algorithm on k is polynomial. Our algorithm avoids the use of the theory of graph minors, is self contained, and runs in time 2O(k³ log k)mn² log² n, thus improving upon the algorithm of Kakimura and co-authors with respect to both the parameter as well as the input size. Our algorithm utilizes a recursive application of "generalized" important separators to reduce the subset version of this problem to the standard version of the problem. [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]

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]

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(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)