**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Publication# Fast and Space Efficient Spectral Sparsification in Dynamic Streams

Mikhail Kapralov, Aidasadat Mousavifar, Navid Nouri, Jakab Tardos

*ASSOC COMPUTING MACHINERY, *2020

Article de conférence

Article de conférence

Résumé

In this paper, we resolve the complexity problem of spectral graph sparcification in dynamic streams up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses (O) over tilde (n) space, and with high probability, recovers a spectral sparsifier from the sketch in (O) over tilde (n) time.(1) Prior results either achieved near optimal (O) over tilde (n) space, but Omega(n(2)) recovery time [Kapralov et al. '14], or ran in o(n(2)) time, but used polynomially suboptimal space [Ahn et al '13]. Our main technical contribution is a novel method for recovering graph edges with high effective resistance from a linear sketch. We show how to do so in nearly linear time by 'bucketing' vertices of the input graph into clusters using a coarse approximation to the graph's effective resistance metric. A second main contribution is a new pseudorandom generator (PRG) for linear sketching algorithms. Constructed from a locally computable randomness extractor, our PRG stretches a seed of (O) over tilde (n) random bits polynomially in length with just log(O(1)) n runtime cost per evaluation. This improves on Nisan's commonly used PRG, which in our setting would require (O) over tilde (n) time per evaluation. Our faster PRG is essential to simultaneously achieving near optimal space and time complexity.

Official source

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Concepts associés (12)

Complexité en temps

En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arrive

Théorie des graphes

vignette|Un tracé de graphe.
La théorie des graphes est la discipline mathématique et informatique qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des objets

Théorie de la complexité (informatique théorique)

vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterm

Publications associées (18)

Chargement

Chargement

Chargement

We deal with some generalizations of the graph coloring problem on classes of perfect graphs. Namely we consider the μ-coloring problem (upper bounds for the color on each vertex), the precoloring extension problem (a subset of vertices colored beforehand), and a problem generalizing both of them, the (γ,μ)-coloring problem (lower and upper bounds for the color on each vertex). We characterize the complexity of all those problems on clique-trees of different heights, providing polynomial-time algorithms for the cases that are easy. These results have interesting corollaries. First, one can observe on clique-trees of different heights the increasing complexity of the chain k-coloring, μ-coloring, (γ,μ)-coloring, and list-coloring. Second, clique-trees of height 2 are the first known example of a class of graphs where μ-coloring is polynomial-time solvable and precoloring extension is NP-complete, thus being at the same time the first example where μ-coloring is polynomially solvable and (γ,μ)-coloring is NP-complete. Last, we show that theμ-coloring problem on unit interval graphs is NP-complete. These results answer three questions from Bonomo et al. [F. Bonomo, G. Durán, J. Marenco, Exploring the complexity boundary between coloring and list-coloring, Annals of Operations Research 169 (1) (2009) 3–16].

The graph coloring problem is one of the most famous problems in graph theory and has a large range of applications. It consists in coloring the vertices of an undirected graph with a given number of colors such that two adjacent vertices get different colors. This thesis deals with some variations of this basic coloring problem which are related to scheduling and discrete tomography. These problems may also be considered as partitioning problems. In Chapter 1 basic definitions of computational complexity and graph theory are presented. An introduction to graph coloring and discrete tomography is given. In the next chapter we discuss two coloring problems in mixed graphs (i.e., graphs having edges and arcs) arising from scheduling. In the first one (strong mixed graph coloring problem) we have to cope with disjunctive constraints (some pairs of jobs cannot be processed simultaneously) as well as with precedence constraints (some pairs of jobs must be executed in a given order). It is known that this problem is NP-complete in mixed bipartite graphs. In this thesis we strengthen this result by proving that for k = 3 colors the strong mixed graph coloring problem is NP-complete even if the mixed graph is planar bipartite with maximum degree 4 and each vertex incident to at least one arc has maximum degree 2 or if the mixed graph is bipartite and has maximum degree 3. Furthermore we show that the problem is polynomially solvable in partial p-trees, for fixed p, as well as in general graphs with k = 2 colors. We also give upper bounds on the strong mixed chromatic number or even its exact value for some classes of graphs. In the second problem (weak mixed graph coloring problem), we allow jobs linked by precedence constraints to be executed at the same time. We show that for k = 3 colors this problem is NP-complete in mixed planar bipartite graphs of maximum degree 4 as well as in mixed bipartite graphs of maximum degree 3. Again, for partial p-trees, p fixed, and for general graphs with k = 2 colors, we prove that the weak mixed graph coloring problem is polynomially solvable. We consider in Chapter 3 the problem of characterizing in an undirected graph G = (V, E) a minimum set R of edges for which maximum matchings M can be found with specific values of p = |M ∩ R|. We obtain partial results for some classes of graphs and show in particular that for odd cacti with triangles only and for forests one can determine in polynomial time whether there exists a minimum set R for which there are maximum matchings M such that p= |R ∩ M|, for p= 0,1, ..., ν(G). The remaining chapters deal with some coloring (or partitioning) problems related to the basic image reconstruction problem in discrete tomography. In Chapter 4 we consider a generalization of the vertex coloring problem associated with the basic image reconstruction problem. We are given an undirected graph and a family of chains covering its vertices. For each chain the number of occurrences of each color is given. We then want to find a coloring respecting these occurrences. We are interested in both, arbitrary and proper colorings and give complexity results. In particular we show that for arbitrary colorings the problem is NP-complete with two colors even if the graph is a tree of maximum degree 3. We also consider the edge coloring version of both problems. Again we present some complexity results. We consider in Chapter 5 some generalized neighborhoods instead of chains. For each vertex x we are given the number of occurrences of each color in its open neighborhood Nd(x) (resp. closed neighborhood Nd+(x)), representing the set of vertices which are at distance d from x (resp. at distance at most d from x). We are interested in arbitrary colorings as well as proper colorings. We present some complexity results and we show in particular that for d = 1 the problems are polynomially solvable in trees using a dynamic programming approach. For the open neighborhood and d = 2 we obtain a polynomial time algorithm for quatrees (i.e. trees where all internal vertices have degree at least 4). We also examine the bounded version of these problems, i.e., instead of the exact number of occurrences of each color we are given upper bounds on these occurrences. In particular we show that the problem for proper colorings is NP-complete in bipartite graphs of maximum degree 3 with four colors and each color appearing at most once in the neighborhood N(x) of each vertex x. This result implies that the L(1,1)-labelling problem is NP-complete in this class of graphs for four colors. Finally in Chapter 6 we consider the edge partitioning version of the basic image reconstruction problem, i.e., we have to partition the edge set of a complete bipartite graph into k subsets such that for each vertex there must be a given number of edges of each set of the partition incident to this vertex. For k = 3 the complexity status is still open. Here we present a new solvable case for k = 3. Then we examine some variations where the union of two subsets E1, E2 has to satisfy some additional constraints as for example it must form a tree or a collection of disjoint chains. In both cases we give necessary and sufficient conditions for a solution to exist. We also consider the case where we have a complete graph instead of a complete bipartite graph. We show that the edge partitioning problem in a complete graph is at least as difficult as in a complete bipartite graph. We also give necessary and sufficient conditions for a solution to exist if E1 ∪ E2 form a tree or if they form a Hamiltonian cycle in the case of a complete graph. Finally we examine for both, complete and complete bipartite graphs, the case where each one of the sets E1 and E2 is structured (two disjoint Hamiltonian chains, two edge disjoint cycles) and present necessary and sufficient conditions.

We present an O(m^10/7) = O(m^1.43)-time algorithm for the maximum s-t flow and the minimum s-t cut problems in directed graphs with unit capacities. This is the first improvement over the sparse-graph case of the long-standing O(m min{m^1/2, n^2/3}) running time bound due to Even and Tarjan [16]. By well-known reductions, this also establishes an O(m^10/7)-time algorithm for the maximum-cardinality bipartite matching problem. That, in turn, gives an improvement over the celebrated O(mn^1/2) running time bound of Hopcroft and Karp [25] whenever the input graph is sufficiently sparse. At a very high level, our results stem from acquiring a deeper understanding of interior-point methods - a powerful tool in convex optimization - in the context of flow problems, as well as, utilizing certain interplay between maximum flows and bipartite matchings.