Search

Self-stabilization in distributed systems is a technique to guarantee convergence to a set of legitimate states without external intervention when a transient fault or bad initialization occurs. Recently, there has been a surge of efforts in designing techniques for automated synthesis of self-stabilizing algorithms that are correct by construction. Most of these techniques, however, are not parameterized, meaning that they can only synthesize a solution for a fixed and predetermined number of processes. In this paper, we report a breakthrough in parameterized synthesis of self-stabilizing algorithms in symmetric networks, including ring, line, mesh, and torus. First, we develop cutoffs that guarantee (1) closure in legitimate states, and (2) deadlock-freedom outside the legitimate states. We also develop a sufficient condition for convergence in self-stabilizing systems. Since some of our cutoffs grow with the size of the local state space of processes, scalability of the synthesis procedure is still a problem. We address this problem by introducing a novel SMT-based technique for counterexample-guided synthesis of self-stabilizing algorithms in symmetric networks. We have fully implemented our technique and successfully synthesized solutions to maximal matching, three coloring, and maximal independent set problems for ring and line topologies.

We provide a tight analysis that settles the round complexity of the well-studied parallel randomized greedy MIS algorithm, thus answering the main open question of Blelloch, Fineman, and Shun [SPAA’12]. The parallel/distributed randomized greedy Maximal Independent Set (MIS) algorithm works as follows. An order of the vertices is chosen uniformly at random. Then, in each round, all vertices that appear before their neighbors in the order are added to the independent set and removed from the graph along with their neighbors. The main question of interest is the number of rounds it takes until the graph is empty. This algorithm has been studied since 1987, initiated by Coppersmith, Raghavan, and Tompa [FOCS’87], and the previously best known bounds were O (log n ) rounds in expectation for Erdős-Rényi random graphs by Calkin and Frieze [Random Struc. Alg.’90] and O (log 2 n ) rounds with high probability for general graphs by Blelloch, Fineman, and Shun [SPAA’12]. We prove a high probability upper bound of O (log n ) on the round complexity of this algorithm in general graphs and that this bound is tight. This also shows that parallel randomized greedy MIS is as fast as the celebrated algorithm of Luby [STOC’85, JALG’86].

Finding a maximal independent set ( MIS ) in a graph is one of the fundamental problems in distributed computing. Researchers in this community are trying to close the time complexity gap of computing a MIS in a graph, way back from Luby’s [STOC’85] O ( log n ) time (randomized) algorithm and Linial’s [SICOMP’92] Ω ( log ∗ n ) lower bound result ( n is the number of nodes of the graph). Since then, an extensive research has been done on this problem, however, most of the results are randomized and we are lack of efficient deterministic solution. In fact, no polylogarithmic (in n ) time deterministic algorithm is known so far in general graphs — an open question raised by Linial in 1993 [Comb. Probab. Comput.’93]. In this paper, we study the MIS problem in geometric graphs, a class of graphs which has both theoretical and practical importance. We present O ( 1 ) -time deterministic algorithms (hence, optimal) for computing MIS in unit interval graphs, unit square graphs and unit disk graphs. The same idea applies to develop optimal MIS algorithm for higher dimensional unit balls and unit hypercubes. We further extend the MIS algorithms to compute approximate maximum independent set ( MaxIS ) in the above geometric graph classes. The theoretical results are corroborated through extensive experiments to show the effectiveness and efficiency of our algorithms. Our algorithms are fully decentralized, scalable, and robust. In general, nodes exchange only O ( log n ) bits message through an edge per communication. Moreover, being local, our algorithms are also suitable in failure model, self-stabilizing and appropriate for dynamic environment.

Graph coloring problem is a famous NP-complete problem and there exist several methods which have been projected to resolve this issue. For a graph colouring algorithm to be efficient, it ought to paint the input graph by minimum colours and must also find the solution in the minimum possible time. Here, we have proposed a different method to solve the graph coloring problem using maximal independent set. In our method, we used the concept of maximal independent sets using trees. In the first part, it converts a massive graph into a sequence of step by step smaller graphs by eliminating big independent sets from the initial graph. The second part starts by assigning a proper colour to each maximal independent set within the sequence. The proposed method is estimated on the DIMACS standards and presented reasonable outcomes concerning to other latest methods.

This paper presents a model of public good provision in networks where the level of public good that an agent has access to depends on the maximum of contributions by the agents in her neighbourhood. Our analysis shows that the game always has an equilibrium in pure strategies and all equilibria are specialised and stable. Welfare analysis shows that formation of new links in a prevailing network may not always be useful.

We investigate the terminal-pairability problem in the case when the base graph is a complete bipartite graph, and the demand graph is a (not necessarily bipartite) multigraph on the same vertex set. In computer science, this problem is known as the edge-disjoint paths problem. We improve the lower bound on the maximum value of $\Delta(D)$ which still guarantees that the demand graph $D$ has a realization in $K_{n,n}$. We also solve the extremal problem on the number of edges, i.e., we determine the maximum number of edges which guarantees that a demand graph is realizable in $K_{n,n}$., Comment: 15 pages, draws from arXiv:1702.04313

Recently, Balliu, Brandt, and Olivetti [FOCS '20] showed the first $\omega(\log^* n)$ lower bound for the maximal independent set (MIS) problem in trees. In this work we prove lower bounds for a much more relaxed family of distributed symmetry breaking problems. As a by-product, we obtain improved lower bounds for the distributed MIS problem in trees. For a parameter $k$ and an orientation of the edges of a graph $G$, we say that a subset $S$ of the nodes of $G$ is a $k$-outdegree dominating set if $S$ is a dominating set of $G$ and if in the induced subgraph $G[S]$, every node in $S$ has outdegree at most $k$. Note that for $k=0$, this definition coincides with the definition of an MIS. For a given $k$, we consider the problem of computing a $k$-outdegree dominating set. We show that, even in regular trees of degree at most $\Delta$, in the standard \LOCAL model, there exists a constant $\epsilon>0$ such that for $k\leq \Delta^\epsilon$, for the problem of computing a $k$-outdegree dominating set, any randomized algorithm requires at least $\Omega(\min\{\log\Delta,\sqrt{\log\log n}\})$ rounds and any deterministic algorithm requires at least $\Omega(\min\{\log\Delta,\sqrt{\log n}\})$ rounds. The proof of our lower bounds is based on the recently highly successful round elimination technique. We provide a novel way to do simplifications for round elimination, which we expect to be of independent interest. Our new proof is considerably simpler than the lower bound proof in [FOCS '20]. In particular, our round elimination proof uses a family of problems that can be described by only a constant number of labels. The existence of such a proof for the MIS problem was believed impossible by the authors of [FOCS '20]., Comment: Accepted at PODC 2021

We study the link scheduling problem of wireless networks where signal propagation delays are multiples of certain time interval. The problem can be modeled as a character of the independent sets of periodic graphs, which have infinitely many vertices. We show that the rate region of scheduling a network can be achieved using collision-free, periodic schedules, and derive a graphical approach to explicitly characterize the rate region. In particular, a collision-free schedule can be equivalent to a path in a graph called the scheduling graph induced by the network collision profile and the propagation delays, and hence the rate region is equal to the convex hull of the rate vectors associated with the cycles of the scheduling graph, which have bounded length. With the maximal independent set problem as a special case, calculating the whole rate region is NP hard and also hard to approximate. By exploring a partial order on the paths, we derive an algorithm to calculate a subset of the rate region more efficiently. Our results are also of independent interest for periodic graphs.

Graph analytics are at the heart of a broad range of applications such as drug discovery, page ranking, transportation systems, and recommendation models. When graph size exceeds the available memory size in a computing node, out-of-core graph processing is needed. For the widely used out-of-core graph processing systems, the graphs are stored and accessed from a long latency SSD storage, which becomes a significant performance bottleneck. To tackle this long latency this work exploits the key insight that that nearly all graph algorithms have a dynamically varying number of active vertices that must be processed in each iteration. However, existing graph processing frameworks, such as GraphChi, load the entire graph in each iteration even if a small fraction of the graph is active. This limitation is due to the structure of the graph storage used by these systems. In this work, we propose to use a compressed sparse row (CSR) based graph storage that is more amenable for selectively loading only a few active vertices in each iteration. However, CSR based graph processing suffers from random update propagation to many target vertices. To solve this challenge, we propose to use a multi-log update mechanism that logs updates separately, rather than directly update the active edges and vertices in a graph. The multi-log system maintains a separate log per each vertex interval (a group of vertices). This separation enables efficient processing of all updates bound to each vertex interval by just loading the corresponding log. Further, by logging all the updates associated with a vertex interval in one contiguous log this approach reduces read amplification since all the pages in the log will be processed in the next iteration without wasted page reads. Over the current state of the art out-of-core graph processing framework, our evaluation results show that the MultiLogVC framework improves performance by up to $17.84 \times, 1.19 \times$, $1.65 \times, 1.38 \times, 3.15 \times$, and $6.00 \times$ for the widely used breadth-first search, pagerank, community detection, graph coloring, maximal independent set, and random-walk applications, respectively.

We study several fundamental problems in the k-machine model, a message-passing model for large-scale distributed computations where $k\geq 2$ machines jointly perform computations on a large input of size N, (typically, $N\gg k$). The input is initially partitioned (randomly or in a balanced fashion) among the k machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation.Our main result is a general technique for designing efficient deterministic distributed algorithms in the k-machine model using PRAM algorithms. Our technique works by efficiently simulating PRAM algorithms in the k-machine model in a deterministic way. This simulation allows us to arrive at new algorithms in the k-machine model for some problems for which no efficient k-machine algorithms are known before and also improve on existing results in the k-machine model for some problems.While our simulation allows us to obtain k-machine algorithms for any problem with a known PRAM algorithm, we mainly focus on graph problems. For an input graph on n vertices and m edges, we obtain $\tilde{O}(m/k^{2})$ round 4 algorithms for various graph problems such as r-connectivity for $r=1,2,3,4$, minimum spanning tree (MST), maximal independent set (MIS), $(\Delta+1)$-coloring, maximal matching, ear decomposition, and spanners under the assumption that the edges of the input graph are partitioned (randomly, or in an arbitrary, but balanced, fashion) among the k machines. For problems such as connectivity and MST, the above bound is (essentially) the best possible (up to logarithmic factors). Our simulation technique allows us to obtain the first known efficient deterministic algorithms in the k-machine model for other problems with known deterministic PRAM algorithms.4$\tilde{O}$ notation hides a polylog $(.)$ factor and an additive polylog $(.)$ term.

In this paper, we propose a bio-molecular algorithm with O( ${n}^{{2}} + {m}$ ) biological operations, O( $2^{n}$ ) DNA strands, O( ${n}$ ) tubes and the longest DNA strand, O( ${n}$ ), for solving the independent-set problem for any graph G with ${m}$ edges and ${n}$ vertices. Next, we show that a new kind of the straightforward Boolean circuit yielded from the bio-molecular solutions with ${m}$ NAND gates, ( ${m} +{n} \times $ ( ${n} + {1}$ )) AND gates and (( ${n} \times $ ( ${n} + {1}$ ))/2) NOT gates can find the maximal independent-set(s) to the independent-set problem for any graph ${G}$ with ${m}$ edges and ${n}$ vertices. We show that a new kind of the proposed quantum-molecular algorithm can find the maximal independent set(s) with the lower bound $\Omega $ ( $2^{n/{2}}$ ) queries and the upper bound O( $2^{n/{2}}$ ) queries. This work offers an obvious evidence for that to solve the independent-set problem in any graph ${G}$ with ${m}$ edges and ${n}$ vertices, bio-molecular computers are able to generate a new kind of the straightforward Boolean circuit such that by means of implementing it quantum computers can give a quadratic speed-up. This work also offers one obvious evidence that quantum computers can significantly accelerate the speed and enhance the scalability of bio-molecular computers. Next, the element distinctness problem with input of ${n}$ bits is to determine whether the given $2^{n}$ real numbers are distinct or not. The quantum lower bound of solving the element distinctness problem is $\Omega $ ( $2^{n\times {(}{2}/{3}{)}}$ ) queries in the case of a quantum walk algorithm. We further show that the proposed quantum-molecular algorithm reduces the quantum lower bound to $\Omega $ (( $2^{n/{2}}$ )/( $2^{\text {1/2}}{)}$ ) queries. Furthermore, to justify the feasibility of the proposed quantum-molecular algorithm, we successfully solve a typical independent set problem for a graph G with two vertices and one edge by carrying out experiments on the backend ibmqx4 with five quantum bits and the backend simulator with 32 quantum bits on IBM’s quantum computer.

In this paper, we introduce the notions of m-shadow graphs and n-splitting graphs,m ≥ 2, n ≥ 1. We prove that, the m-shadow graphs for paths, complete bipartite graphs and symmetric product between paths and null graphs are odd graceful. In addition, we show that, the m-splitting graphs for paths, stars and symmetric product between paths and null graphs are odd graceful. Finally, we present some examples to illustrate the proposed theories.

Introduced by Emek and Wattenhofer (PODC 2013), the \emph{stone age (SA)} model provides an abstraction for network algorithms distributed over randomized finite state machines. This model, designed to resemble the dynamics of biological processes in cellular networks, assumes a weak communication scheme that is built upon the nodes' ability to sense their vicinity in an asynchronous manner. Recent works demonstrate that the weak computation and communication capabilities of the SA model suffice for efficient solutions to some core tasks in distributed computing, but they do so under the (somewhat less realistic) assumption of fault free computations. In this paper, we initiate the study of \emph{self-stabilizing} SA algorithms that are guaranteed to recover from any combination of transient faults. Specifically, we develop efficient self-stabilizing SA algorithms for the \emph{leader election} and \emph{maximal independent set} tasks in bounded diameter graphs subject to an asynchronous scheduler. These algorithms rely on a novel efficient self-stabilizing \emph{asynchronous unison (AU)} algorithm that is "thin" in terms of its state space: the number of states used by the AU algorithm is linear in the graph's diameter bound, irrespective of the number of nodes.

We consider the distributed message-passing model and the Local Computational Algorithms (LCA) model. In both models a network is represented by an n-vertex graph G = (V, E). We focus on labeling problems, such as vertex-coloring, edge-coloring, maximal independent set (MIS) and maximal matching. In the distributed model the vertices of v perform computations in parallel, in order to compute their parts in the solution for G. In the LCA model, on the other hand, probes are performed on certain vertices in order to compute their labels in a solution to a given problem. We study the possibility of estimating a solution produced by an algorithm, much before the algorithm terminates. This estimation not only allows for size estimation of a solution, but also for an early detection of failure in randomized algorithms, so that a correcting procedure can be executed. To this end, we propose a sampling technique, in which the labels in the sampling are distributed proportionally to the distribution in the algorithm’s output. However, the sampling running time is significantly smaller than that of the algorithm in hand. We achieve the following results, in terms of the maximum degree Δ and the arboricity a of the input graph. The running time of our procedures is O(log a + log log n), for sampling vertex-coloring, edge-coloring, maximal matching and MIS. This significantly improves upon previous sampling techniques, which incur additional dependency on the maximum degree Δ that can be much higher than the arboricity, as well as more significant dependency on n. Our techniques for sampling in the distributed model provide a powerful and general tool for estimation in the LCA model. In this setting the goal is estimating the size of a solution to a given problem, by making as few vertex probes as possible. For the above-mentioned problems, we achieve estimations with probe complexity dO(log a + log log n), where d = min(Δ, a · poly(log(n)).

Let \({\mathcal {C}}\) be a class of graphs. A graph \(G=(V,E)\) is \({\mathcal {C}}\)–probe if V(G) can be partitioned into two sets: non-probes \(\mathcal {N}\) and probes \(\mathcal {P}\), where \(\mathcal {N}\) is an independent set and new edges may be added between some non-probe vertices such that the resulting graph is in the class \({\mathcal {C}}\). In this case, we say that \((\mathcal {N},\mathcal {P})\) is a \({\mathcal {C}}\)–probe partition of G. In the Unpartitioned Probe problem for a graph class \({\mathcal {C}}\) we are given a graph G and asked whether G has a \({\mathcal {C}}\)–probe partition, i.e., such a problem consist of recognizing the class of \(\mathcal {C}\)-probe graphs. A graph \(G=(V,E)\) is an \((r,\ell )\)-graph when V can be partitioned into \((S^1,S^2,\ldots , S^r, K^1, K^2, \ldots , K^{\ell })\) such that \(S^1,S^2,\ldots , S^r\) are independent sets, and \(K^1, K^2, \ldots , K^{\ell }\) are cliques. A graph G is well-covered if every maximal independent set is also maximum, and it is \((r,\ell )\)-well-covered if it is well-covered as well as an \((r,\ell )\)-graph. In this paper, we study the complexity of the Unpartitioned Probe problem for the class of \((r,\ell )\)-well-covered graphs. We classify all but the (2, 0) and (1, 2) cases.

We consider the problem of optimal allocation strategies for a (perfect) vaccine in an infinite-metapopulation model (including SIS, SIR, SEIR,. . .), when the loss function is given by the effective reproduction number Re, which is defined as the spectral radius of the effective next generation matrix (in finite dimension) or more generally of the effective next generation operator (in infinite dimension). We give sufficient conditions for Re to be a convex or a concave function of the vaccination strategy. Then, following a previous work, we consider the bi-objective problem of minimizing simultaneously the cost and the loss of the vaccination strategies. In particular, we prove that a cordon sanitaire might not be optimal, but it is still better than the "worst" vaccination strategies. Inspired by the graph theory, we compute the minimal cost which ensures that no infection occurs using independent sets. Using Frobenius decomposition of the whole population into irreducible sub-populations, we give some explicit formulae for optimal ("best" and "worst") vaccinations strategies. Eventually, we provide equivalence properties on models which ensure that the function Re is unchanged.

We analyze the impact of transient and Byzantine faults on the construction of a maximal independent set in a general network. We adapt the self-stabilizing algorithm presented by Turau [15] for computing such a vertex set. Our algorithm is self-stabilizing, and also works under the more difficult context of arbitrary Byzantine faults.

We study the deterministic silent self-stabilizing construction of two disjoint minimal dominating sets (MDSs) in anonymous networks. We focus on algorithms where nodes share only their status (i.e. the name of their MDS to which they belong, if they belong to a MDS). We prove that such an algorithm cannot be designed in distance-1 model under a central daemon; therefore, we study this problem in the distance-2 model under a central daemon. We present an algorithm building two disjoint minimal dominating sets such that one of them is also a maximal independent set (MIS). Any execution of this algorithm converges in 5n moves. Our approach to compute this value is novel: the number of moves is not computed per node. We propose a second algorithm faster than the first one at the expense of the independence property of one of the constructed sets. A node executes at most 2 moves. If the network is not anonymous, the presented algorithms can be translated into a silent self-stabilizing algorithms converging in O($n$•$m$) moves in the distance-1 model under the distributed daemon where m is the number of edges and n the number of nodes. This improves the complexity of O($n$.$m$) moves of proposed algorithms with the same assumptions.

Transition systems (TS) and Petri nets (PN) are important models of computation ubiquitous in formal methods for modeling systems. An important problem is how to extract from a given TS a PN whose reachability graph is equivalent (with a suitable notion of equivalence) to the original TS. This paper addresses the decomposition of transition systems into synchronizing state machines (SMs), which are a class of Petri nets where each transition has one incoming and one outgoing arc and all markings have exactly one token. This is an important case of the general problem of extracting a PN from a TS. The decomposition is based on the theory of regions, and it is shown that a property of regions called excitation-closure is a sufficient condition to guarantee the equivalence between the original TS and a decomposition into SMs. An efficient algorithm is provided which solves the problem by reducing its critical steps to the maximal independent set problem (to compute a minimal set of irredundant SMs) or to satisfiability (to merge the SMs). We report experimental results that show a good trade-off between quality of results vs. computation time. © 2021 IEEE.

Finding complete subgraphs of an undirected graph is another fundamental problem with a variety of interesting applications in diverse scientific and engineering disciplines. Clique algorithms also find application in the comparison of structures described by trees or graphs and, as a matter of fact, finding maximal and maximum cliques is the basis of the algorithms discussed in Chap. 7 for finding maximal and maximum common subgraph isomorphisms between two graphs.

Identify influential nodes is essential to the immunization and propagation process on complex networks that this node selects based on the influence maximization problem. However, most of the previous strategies face many challenges, such as accuracy and efficiency. To solve these challenges, in this paper, we propose a novel influence maximization algorithm, named NFIM (Node filtering in influence maximization), which is based on deleting a maximal independent set and creating a subgraph. First, the search space for selecting seed nodes is reduced in the NFIM algorithm Then, seed nodes are selected by examining independent paths and clustering coefficient. Experiment results present that the NFIM algorithm performs better than PHG, LIR, CI, and ProbDegree on influence spread and faster than PHG, LIR, and CI.

In this chapter, we introduce the self-stabilizing algorithm model and present several definitive examples that illustrate the simplicity and elegance of this algorithmic paradigm when applied to problems related to dominating sets in graphs. In this paradigm, a distributed computing system or network is modeled by an undirected graph G = (V, E), where V is its set of nodes, or processors, and E is its set of edges, or communication links. Each node has only a local view of the system, namely its immediate neighbors. Thus, it has no knowledge of the network, its size, or how it is structured. Every node executes the same algorithm simultaneously, and in a finite amount of time, often O(n), the system converges, or stabilizes, to a global, stable state, satisfying some desired property. For example, the states of the nodes in the given graph G can define a maximal independent set, a maximal matching, a minimal dominating set, a minimal total dominating set, or even two disjoint minimal dominating sets.

Consider the following distributed graph sketching model: There is a referee and n vertices in an undirected graph G sharing public randomness. Each vertex v only knows its neighborhood in G and the referee receives no input initially. The vertices simultaneously each sends a message, called a sketch, to the referee who then based on the received sketches outputs a solution to some combinatorial problem on G, say, the minimum spanning tree problem. Previous work on graph sketching have shown that numerous problems, including connectivity, minimum spanning tree, edge or vertex connectivity, cut or spectral sparsifiers, and (Δ + 1)-vertex coloring, all admit efficient algorithms in this model that only require sketches of size polylog(n) per vertex. In contrast, we prove that the two fundamental problems of maximal matching and maximal independent set do not admit such efficient solutions: Any algorithm for either problem that errs with a small constant probability requires sketches of size Ω(n1/2--e) for any constant e > 0. We prove our results by analyzing communication complexity of these problems in a communication model that allows sharing of inputs between limited number of players, and hence lies between the standard number-in-hand and number-on-forehead multi-party communication models. Our proofs are based on a family of hard instances using Ruzsa-Szemeredi graphs and information-theoretic arguments to establish the communication lower bounds.

We present improved algorithms for approximating maximum-weight independent set (MaxIS) in the CONGEST model. Given an input graph, let n and Δ be the number of nodes and maximum degree, respectively, and let MIS(n, Δ) be the running time of finding a maximal independent set (MIS) in the CONGEST model. Bar-Yehuda et al. [PODC 2017] showed that there is an algorithm in the CONGEST model that finds a Δ-approximation for MaxIS in O(MIS(n, Δ) log W) rounds, where W is the maximum weight of a node in the graph, which can be as high as poly(n). Whether their algorithm is deterministic or randomized depends on the MIS algorithm that is used as a black-box. Our results: (1) A deterministic O(MIS(n, Δ)/∈)-round algorithm that finds a (1 + ∈)Δ-approximation for MaxIS in the CONGEST model. (2) A randomized (poly(log log n)/∈)-round algorithm that finds, with high probability, a (1 + ∈)Δ-approximation for MaxIS in the CONGEST model. That is, by sacrificing only a tiny fraction of the approximation guarantee, we achieve an exponential speed-up in the running time over the previous best known result.

The Massively Parallel Computation (MPC) model is an emerging model which distills core aspects of distributed and parallel computation. It has been developed as a tool to solve (typically graph) problems in systems where the input is distributed over many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in $n$, the number of nodes in the input graph) memory, with randomized algorithms presented for fundamental graph problems of Maximal Matching and Maximal Independent Set. However, there have been no prior corresponding \emph{deterministic} algorithms. A major challenge underlying the sublinear space setting is that the local space of each machine might be too small to store all the edges incident to a single node. This poses a considerable obstacle compared to the classical models in which each node is assumed to know and have easy access to its incident edges. To overcome this barrier we introduce a new \emph{graph sparsification technique} that \emph{deterministically} computes a low-degree subgraph with additional desired properties. Using this framework to derandomize the well-known randomized algorithm of Luby [SICOMP'86], we obtain $O(\log \Delta+\log\log n)$-round \emph{deterministic} MPC algorithms for solving the fundamental problems of \emph{Maximal Matching} and \emph{Maximal Independent Set} with $O(n^{\epsilon})$ space on each machine for any constant $\epsilon > 0$. Based on the recent work of Ghaffari et al. [FOCS'18], this additive $O(\log\log n)$ factor is \emph{conditionally} essential. These algorithms can also be shown to run in $O(\log \Delta)$ rounds in the closely related model of \congc, improving upon the state-of-the-art bound of $O(\log^2 \Delta)$ rounds by Censor-Hillel et al. [DISC'17]., Comment: he coloring part was omitted from the current version, and will appear soon on a separate arXiv manuscript

We present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated $2^{O(\sqrt{\log n})}$-time algorithm of Panconesi and Srinivasan [STOC'92] and settles a central and long-standing question in distributed graph algorithms. It also leads to the first polylogarithmic-time deterministic distributed algorithms for numerous other problems, hence resolving several well-known and decades-old open problems, including Linial's question about the deterministic complexity of maximal independent set [FOCS'87; SICOMP'92]---which had been called the most outstanding problem in the area. The main implication is a more general distributed derandomization theorem: Put together with the results of Ghaffari, Kuhn, and Maus [STOC'17] and Ghaffari, Harris, and Kuhn [FOCS'18], our network decomposition implies that $$\mathsf{P}\textit{-}\mathsf{RLOCAL} = \mathsf{P}\textit{-}\mathsf{LOCAL}.$$ That is, for any problem whose solution can be checked deterministically in polylogarithmic-time, any polylogarithmic-time randomized algorithm can be derandomized to a polylogarithmic-time deterministic algorithm. Informally, for the standard first-order interpretation of efficiency as polylogarithmic-time, distributed algorithms do not need randomness for efficiency. By known connections, our result leads also to substantially faster randomized distributed algorithms for a number of well-studied problems including $(\Delta+1)$-coloring, maximal independent set, and Lov\'{a}sz Local Lemma, as well as massively parallel algorithms for $(\Delta+1)$-coloring., Comment: Extended version of an article that appears at the Symposium on Theory of Computing (STOC) 2020

For a huge number of features versus a small size of samples, feature selection methods are useful preprocessing approaches that could eliminate the irrelevant and redundant features from the final feature subset. One of the recent research areas in feature selection is DNA microarray that the number of dimensions increase fast and requires further research in the field of feature selection. Modeling the feature search space as a graph leads to improving the visualizing of features and using graph theoretic concepts in the feature selection process. In this paper, a filer-based feature selection algorithm using graph technique is proposed for reducing the dimension of dataset named as Symmetric Uncertainty Class-Feature Association Map feature selection (SU-CFAM). In the first step, it uses the Symmetric Uncertainty concept for visualizing the feature search space as a graph. After clustering the graph into several clusters using a community detection algorithm, SU-CFAM constructs an adjacency matrix for each cluster and the final subset is selected by using the concept of maximal independent set. The performance of SU-CFAM has been compared with five well-known feature selection approaches using three classifiers including SVM, DT, NB. Experiments on fifteen public DNA microarray datasets show that SU-CFAM can achieve a better classification performance compared with other methods.

The vertex cover problem and the dominating set problem are two well-known problems in graph theory. Their goal is to find the minimum size of a vertex subset satisfying some properties. Both hold a connected version, which imposes that the vertex subset must induce a connected component. To study the interdependence between the connected version and the original version of a problem, the Price of Connectivity ( $$PoC$$ ) was introduced by Cardinal and Levy (Theor Comput Sci 411(26–28):2581–2590, 2010) and Levy (Approximation algorithms for covering problems in dense graphs. Ph.D. thesis, Universite libre de Bruxelles, Brussels, 2009) as the ratio between invariants from the connected version and the original version of the problem. Camby et al. (Discret Math Theor Comput Sci 16:207–224, 2014) for the vertex cover problem, Camby and Schaudt (Discret Appl Math 177:53–59, 2014) for the dominating set problem characterized some classes of $$PoC$$ -Near-Perfect graphs, hereditary classes of graphs in which the Price of Connectivity is bounded by a fixed constant. Moreover, only for the vertex cover problem, Camby et al. (2014) introduced the notion of critical graphs, graphs that can appear in the list of forbidden induced subgraphs characterization. By definition, the Price of Connectivity of a critical graph is strictly greater than that of any proper induced subgraph. In this paper, we prove that for the vertex cover problem, every critical graph is either isomorphic to a cycle on 5 vertices or bipartite. To go further in the previous studies, we also present conjectures on $$PoC$$ -Near-Perfect graphs and critical graphs with the help of the computer software GraphsInGraphs (Camby and Caporossi in Studying graphs and their induced subgraphs with the computer: GraphsInGraphs. Cahiers du GERAD G-2016-10, 2016). Moreover, for the dominating set problem, we investigate critical trees and we show that every minimum dominating set of a critical graph is independent.

We consider two models of computation: centralized local algorithms and local distributed algorithms. Algorithms in one model are adapted to the other model to obtain improved algorithms. Distributed vertex coloring is employed to design improved centralized local algorithms for: maximal independent set, maximal matching, and an approximation scheme for maximum (weighted) matching over bounded degree graphs. The improvement is threefold: the algorithms are deterministic, stateless, and the number of probes grows polynomially in log ⁎ ⁡ n , where n is the number of vertices of the input graph. The recursive centralized local improvement technique by Nguyen and Onak (FOCS 2008) is employed to obtain a distributed approximation scheme for maximum (weighted) matching.

Chordal graphs, permutation graphs, and interval graphs are among many classes of graphs which can be characterized by the existence of certain acyclic orientations and vertex orderings. These types of characterizations exist for some of their bipartite analogues such as chordal bipartite graphs and bipartite permutation graphs. Chvatal proved that a bipartite graph G is chordal bipartite if and only if the complement G ¯ of G has a vertex ordering ≺ such that for every induced path a b c d in G ¯ , a ≺ b implies c ≺ d . Recently, Le proved that a bipartite graph G is a permutation graph if and only if G ¯ admits an acyclic orientation such that for every induced path a b c d in G ¯ , a b is an oriented edge if and only if c d is. Interestingly these orientation and vertex ordering characterizations are stated on the complements of bipartite graphs. We show that interval bigraphs and interval containment bigraphs also admit similar characterizations in terms of vertex orderings and acyclic orientations of their complements.

A vertex of a connected graph is a contour vertex provided the eccentricity of the vertex is at least as large as that of each of its neighbors. We consider the question of whether the set S of contour vertices of a connected graph is geodetic, i.e., whether every vertex of the graph lies on a shortest path (geodesic) between some pair of vertices in S . In general, it is known that when long induced cycles are forbidden (for chordal graphs) the answer is in the affirmative, but otherwise (even for weakly chordal graphs) the answer is in the negative. For bipartite graphs, it is known that when long induced cycles are allowed, the answer is in the negative. In contrast, we show that when long induced cycles are forbidden in bipartite graphs, namely for chordal bipartite graphs, the answer is in the affirmative. Our result also shows that while the answer is in the negative for bipartite graphs and weakly chordal graphs, for a graph that is both bipartite and weakly chordal, the answer is in the affirmative.

We show that the non-existence of mad families is equiconsistent with $$\textit{ZFC}$$ , answering an old question of Mathias. We also consider the above result in the general context of maximal independent sets in Borel graphs, and we construct a Borel graph G such that $$\textit{ZF}+\textit{DC}+$$ “there is no maximal independent set in G” is equiconsistent with $$\textit{ZFC}+$$ “there exists an inaccessible cardinal”.

Computing a maximal independent set is an important step in many parallel graph algorithms. This article introduces ECL-MIS, a maximal independent set implementation that works well on GPUs. It includes key optimizations to speed up computation, reduce the memory footprint, and increase the set size. Its CUDA implementation requires fewer than 30 kernel statements, runs asynchronously, and produces a deterministic result. It outperforms the maximal independent set implementations of Pannotia, CUSP, and IrGL on each of the 16 tested graphs of various types and sizes. On a Titan X GPU, ECL-MIS is between 3.9 and 100 times faster (11.5 times, on average). ECL-MIS running on the GPU is also faster than the parallel CPU codes Ligra, Ligra+, and PBBS running on 20 Xeon cores, which it outperforms by 4.1 times, on average. At the same time, ECL-MIS produces maximal independent sets that are up to 52% larger (over 10%, on average) compared to these preexisting CPU and GPU implementations. Whereas these codes produce maximal independent sets that are, on average, about 15% smaller than the largest possible such sets, ECL-MIS sets are less than 6% smaller than the maximum independent sets.

We give a new randomized distributed algorithm for (Δ +1)-coloring in the LOCAL model, running in O (√ log Δ)+ 2 O (√log log n ) rounds in a graph of maximum degree Δ. This implies that the (Δ +1)-coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds of Ω(min(√/log n log log n , /log Δ log log Δ)) by Kuhn, Moscibroda, and Wattenhofer [PODC’04]. Our algorithm also extends to list-coloring where the palette of each node contains Δ +1 colors. We extend the set of distributed symmetry-breaking techniques by performing a decomposition of graphs into dense and sparse parts.

Graph matching is essential in several fields that use structured information, such as biology, chemistry, social networks, knowledge management, document analysis and others. Except for special classes of graphs, graph matching has in the worst-case an exponential complexity; however, there are algorithms that show an acceptable execution time, as long as the graphs are not too large and not too dense. In this paper we introduce a novel subgraph isomorphism algorithm, VF3, particularly efficient in the challenging case of graphs with thousands of nodes and a high edge density. Its performance, both in terms of time and memory, has been assessed on a large dataset of 12,700 random graphs with a size up to 10,000 nodes, made publicly available. VF3 has been compared with four other state-of-the-art algorithms, and the huge experimentation required more than two years of processing time. The results confirm that VF3 definitely outperforms the other algorithms when the graphs become huge and dense, but also has a very good performance on smaller or sparser graphs.