Search

While there has been significant work on parallel graph processing, there has been very surprisingly little work on high-performance hypergraph processing. This paper presents a collection of efficient parallel algorithms for hypergraph processing, including algorithms for betweenness centrality, maximal independent set, k-core decomposition, hypertrees, hyperpaths, connected components, PageRank, and single-source shortest paths. For these problems, we either provide new parallel algorithms or more efficient implementations than prior work. Furthermore, our algorithms are theoretically-efficient in terms of work and depth. To implement our algorithms, we extend the Ligra graph processing framework to support hypergraphs, and our implementations benefit from graph optimizations including switching between sparse and dense traversals based on the frontier size, edge-aware parallelization, using buckets to prioritize processing of vertices, and compression. Our experiments on a 72-core machine and show that our algorithms obtain excellent parallel speedups, and are significantly faster than algorithms in existing hypergraph processing frameworks.

The goal of this paper is to obtain quantitative results on the number and on the size of maximal independent sets and maximal matchings in several block-stable graph classes that satisfy a proper sub-criticality condition. In particular we cover trees, cacti graphs and series-parallel graphs. The proof methods are based on a generating function approach and a proper singularity analysis of solutions of implicit systems of functional equations in several variables. As a byproduct, this method extends previous results of Meir and Moon for trees [Meir, Moon: On maximal independent sets of nodes in trees, Journal of Graph Theory 1988]., Comment: 32 pages, 7 figures

A \((k, \ell )\)-partition of a graph G is a partition of its vertex set into k independent sets and \(\ell \) cliques. A graph is \((k, \ell )\) if it admits a \((k, \ell )\)-partition. A graph is well-covered if every maximal independent set is also maximum. A graph is \((k,\ell )\)-well-covered if it is both \((k,\ell )\) and well-covered. In 2018, Alves et al. provided a complete mapping of the complexity of the \((k,\ell )\)-Well-Covered Graph problem, in which given a graph G, it is asked whether G is a \((k,\ell )\)-well-covered graph. Such a problem is polynomial-time solvable for the subclasses (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), and (2, 0), and NP-hard or coNP-hard, otherwise. In the Graph Sandwich Problem for Property \(\Pi \) we are given a pair of graphs \(G^1=(V,E^1)\) and \(G^2=(V,E^2)\) with \(E^1\subseteq E^2\), and asked whether there is a graph \(G=(V,E)\) with \(E^1\subseteq E\subseteq E^2\), such that G satisfies the property \(\Pi \). It is well-known that recognizing whether a graph G satisfies a property \(\Pi \) is equivalent to the particular graph sandwich problem where \(E^1=E^2\). Therefore, in this paper we extend previous studies on the recognition of \((k,\ell )\)-well-covered graphs by presenting a complexity analysis of Graph Sandwich Problem for the property of being \((k,\ell )\)-well-covered. Focusing on the classes that are tractable for the problem of recognizing \((k,\ell )\)-well-covered graphs, we prove that Graph Sandwich for \((k,\ell )\)-well-covered is polynomial-time solvable when \((k,\ell )=(0,1),(1,0),(1,1)\) or (0, 2), and NP-complete if we consider the property of being (1, 2)-well-covered.

Wireless sensor networks (WSNs) are composed of a large number of wireless self-organized sensor nodes connected through a wireless decentralized distributed network without the aid of a predefined infrastructure. Fault-tolerance and power management are fundamental challenges in WSNs. A WSN is self-stabilizing if it can initially start at any state and obtain a legitimate state in a finite time without any external intervention. Self-stabilization is an important method for providing fault-tolerance in WSNs. Maximal independent set (MIS) is an extensively used structure for many important applications such as clustering (Randhawa and Jain in Wirel Personal Commun 97(3):3355, 2017. 10.1007/s11277-017-4674-5) and routing (Attea et al. in Wirel Personal Commun 81(2):819, 2015. 10.1007/s11277-014-2159-3; Lipinski in Wirel Personal Commun 101(1):251, 2018. 10.1007/s11277-018-5686-5) in WSNs. the capacitated MIS (CapMIS) problem is an extension of MIS in that each node has a capacity that determines the number of nodes it may dominate. in this paper, we propose a distributed self-stabilizing capacitated maximal independent set algorithm (CapMIS) in order to reduce energy consumption and support load balancing in WSNs. To the best of our knowledge, this is the first algorithm in this manner. the algorithm is validated through theoretical analysis as well as testbed implementations and simulations., TUBITAK (Scientific and Technical Research Council of Turkey)Turkiye Bilimsel ve Teknolojik Arastirma Kurumu (TUBITAK) [215E115], The authors would like to thank TUBITAK (Scientific and Technical Research Council of Turkey) for the project grant (Project Number 215E115).

Let \(G=(V, E)\) be a graph with a vertex set V and set of edges E. The Graph Coloring Problem consists of splitting the set V into k independent sets (color classes); if two vertices are adjacent (i.e. vertices which share an edge), then they cannot have the same color. In order to address this problem, a plethora of techniques have been proposed in literature. Those techniques are especially based on heuristic algorithms, because the execution time noticeably increases if exact solutions are applied to graphs with more than 100 vertices. In this research, a metaheuristic approach that combines a deterministic algorithm and a heuristic algorithm is proposed, in order to approximate the chromatic number of a graph. This method was experimentally validated by using a collection of graphs from the literature in which the chromatic number is well-known. Obtained results show the feasibility of the metaheuristic proposal in terms of the chromatic number obtained. Moreover, when the proposed methodology is compared against robust techniques, this procedure increases the quality of the residual graph and improves the Tabu search that solves conflicts involved in a path as coloring phase.

Maximal Independent Set (MIS) is one of the fundamental problems in distributed computing. The round (time) complexity of distributed MIS has traditionally focused on the worst-case time for all nodes to finish. The best-known (randomized) MIS algorithms take O(log n) worst-case rounds on general graphs (where n is the number of nodes). Breaking the O(log n) worst-case bound has been a longstanding open problem, while currently the best-known lower bound is [EQUATION] rounds. Motivated by the goal to reduce total energy consumption in energy-constrained networks such as sensor and ad hoc wireless networks, we take an alternative approach to measuring performance. We focus on minimizing the total (or equivalently, the average) time for all nodes to finish. It is not clear whether the currently best-known algorithms yield constant-round (or even o(log n)) node-averaged round complexity for MIS in general graphs. We posit the sleeping model, a generalization of the traditional model, that allows nodes to enter either "sleep" or "waking" states at any round. While waking state corresponds to the default state in the traditional model, in sleeping state a node is "offline", i.e., it does not send or receive messages (and messages sent to it are dropped as well) and does not incur any time, communication, or local computation cost. Hence, in this model, only rounds in which a node is awake are counted and we are interested in minimizing the average as well as the worst-case number of rounds a node spends in the awake state, besides the traditional worst-case round complexity (i.e., the rounds for all nodes to finish including both the awake and sleeping rounds). Our main result is that we show that MIS can be solved in (expected) O(1) rounds under node-averaged awake complexity measure in the sleeping model. In particular, we present a randomized distributed algorithm for MIS that has expected O(1)-rounds node-averaged awake complexity and, with high probability1 has O(log n)-rounds worst-case awake complexity and O(log3.41 n)-rounds worst-case complexity. Our work is a step towards understanding the node-averaged complexity of MIS both in the traditional and sleeping models, as well as designing energy-efficient distributed algorithms for energy-constrained networks.

We propose a multivariable continuous polynomial optimization formulation to find arbitrary maximal independent sets of any size for any graph. A local optima of the optimization problem yields a maximal independent set, while the global optima yields a maximum independent set. The solution is two phases. The first phase is listing all the maximal cliques of the graph and the second phase is solving the optimization problem. We believe that our algorithm is efficient for sparse graphs, for which there exist fast algorithms to list their maximal cliques. Our algorithm was tested on some of the DIMACS maximum clique benchmarks and produced results efficiently. In some cases our algorithm outperforms other algorithms, such as cliquer.

The Maximum Weight Independent Set Problem (WIS) is a well-known NP-hard problem. A popular way to study WIS is to detect graph classes for which WIS can be solved in polynomial time, with particular reference to hereditary graph classes, i.e., defined by a hereditary graph property or equivalently by forbidding one or more induced subgraphs. Given two graphs G and H, $$G+H$$ G + H denotes the disjoint union of G and H. This manuscript shows that (i) WIS can be solved for ($$P_4+P_4$$ P 4 + P 4 , Triangle)-free graphs in polynomial time, where a $$P_4$$ P 4 is an induced path of four vertices and a Triangle is a cycle of three vertices, and that in particular it turns out that (ii) for every ($$P_4+P_4$$ P 4 + P 4 , Triangle)-free graph G there is a family $${{\mathcal {S}}}$$ S of subsets of V(G) inducing (complete) bipartite subgraphs of G, which contains polynomially many members and can be computed in polynomial time, such that every maximal independent set of G is contained in some member of $${\mathcal {S}}$$ S . These results seem to be harmonic with respect to other polynomial results for WIS on [subclasses of] certain $$S_{i,j,k}$$ S i , j , k -free graphs and to other structure results on [subclasses of] Triangle-free graphs.

A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of diamond-free graphs, from both structural and algorithmic points of view. We show that the following five NP-hard or co-NP-hard problems remain intractable when restricted to the class of diamond-free graphs: Is a given clique strong? Does the graph have a strong clique? Is every vertex contained in a strong clique? Given a partition of the vertex set into cliques, is every clique in the partition strong? Can the vertex set be partitioned into strong cliques?

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.

The core issue of multiple graphs clustering is to find clusters of vertices from graphs such that these clusters are well-separated in each graph and clusters are consistent across different graphs. The problem can be formulated as a multiple orthogonality constrained optimization model which can be shown to be a relaxation of a multiple graphs cut problem. The resulting optimization problem can be solved by a gradient flow iterative method. The convergence of the proposed iterative scheme can be established. Numerical examples are presented to demonstrate the effectiveness of the proposed method for solving multiple graphs clustering problems in terms of clustering accuracy and computational efficiency.

We study spanning properties of sparse cone-based graphs of constant degree, parameterized by a positive integer k > 1 . Cone-based graphs partition the space around each vertex into k equiangular cones, and select at most one outgoing edge in each cone. This guarantees an out-degree of at most k, but the in-degree may be unbounded. To bound the in-degree, at most one incoming edge is retained in each cone. This yields a sparse graph of degree at most 2k (in-degree k and out-degree k). In this paper we introduce the notion of canonical k-cone graphs and establish a spanning ratio of 16.76 for this class of graphs, provided that k = 6 k ′ and k ′ ≥ 5 . The spanning ratio decreases to 4.64 as k ′ increases to 8. We show that both Yao–Yao and Theta–Theta graphs are canonical k-cone graphs and therefore they inherit these spanning ratios. Yao–Yao and Theta–Theta graphs differ only in the way edges are selected. Yao–Yao graphs select an edge of minimum Euclidean length, whereas Theta–Theta graphs select an edge of minimum orthogonal projection onto the cone bisector.

A subset S of vertices in a graph G is a secure dominating set of G if S is a dominating set of G and, for each vertex uS, there is a vertex vS such that uv is an edge and (S{v}){u} is also a dominating set of G. We show that if G is a maximal outerplane graph of n vertices, then G has a secure dominating set of size at most 3n7. Moreover, if a maximal outerplane graph G has no internal triangles, it has a secure dominating set of size at most n3. Finally, we show that any secure dominating set of a maximal outerplane graph without internal triangles has more than n4 vertices.

A family of sets is intersecting if any two sets in the family intersect. Given a graph G and an integer r ≥ 1 , let I ( r ) ( G ) denote the family of independent sets of size r of G . For a vertex v of G , let I v ( r ) ( G ) denote the family of independent sets of size r that contain v . This family is called an r -star and v is its centre. Then G is said to be r -EKR if no intersecting subfamily of I ( r ) ( G ) is bigger than the largest r -star, and if every maximum size intersecting subfamily of I ( r ) ( G ) is an r -star, then G is said to be strictly r -EKR. Let μ ( G ) denote the minimum size of a maximal independent set of G . Holroyd and Talbot conjectured that if 2 r ≤ μ ( G ) , then G is r -EKR, and it is strictly r -EKR if 2 r μ ( G ) . This conjecture has been investigated for several graph classes, but not trees (except paths). In this note, we present a result for a family of trees. A depth-two claw is a tree in which every vertex other than the root has degree 1 or 2 and every vertex of degree 1 is at distance 2 from the root. We show that if G is a depth-two claw, then G is strictly r -EKR if 2 r ≤ μ ( G ) + 1 , confirming the conjecture of Holroyd and Talbot for this family. Hurlbert and Kamat had conjectured that one can always find a largest r -star of a tree whose centre is a leaf. Baber and Borg have independently shown this to be false. We show that, moreover, for all integers n ≥ 2 and d ≥ 3 , there exists a positive integer r such that there is a tree where the centre of the largest r -star is a vertex of degree n at distance d from every leaf.

The second-largest eigenvalue and second-smallest Laplacian eigenvalue of a graph are measures of its connectivity. These eigenvalues can be used to analyze the robustness, resilience, and synchronizability of networks, and are related to connectivity attributes such as the vertex- and edge-connectivity, isoperimetric number, and characteristic path length. In this paper, we present two upper bounds for the second-largest eigenvalues of regular graphs and multigraphs of a given order which guarantee a desired vertex- or edge-connectivity. The given bounds are in terms of the order and degree of the graphs, and hold with equality for infinite families of graphs. These results answer a question of Mohar., 24 pages

We introduce the family of $k$-gap-planar graphs for $k \geq 0$, i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most $k$ of its crossings. This definition is motivated by applications in edge casing, as a $k$-gap-planar graph can be drawn crossing-free after introducing at most $k$ local gaps per edge. We present results on the maximum density of $k$-gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of $k$-gap-planar complete graphs, and the computational complexity of recognizing $k$-gap-planar graphs., Comment: A preliminary version of this paper appeared in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)

The “Towers of Hanoi” is a problem that has been extensively studied and frequently generalized. In particular, it has been generalized to be played on arbitrary directed graphs and using parallel moves of two types. We ask what is the largest number of parallel moves, in either of the two models, that is required to move n disks from the starting node to the destination node. Not all directed graphs allow solving this problem; we will call those graphs that do Hanoi graphs. In previous work, we settled the question of what are the worst sequential Hanoi graphs, that is, those graphs that require the largest number of sequential moves. We also demonstrated that the characterization of sequential Hanoi graphs carries over the parallel Hanoi graphs. Here, we determine the worst Hanoi graphs provided parallel moves are allowed. It turns out that for one of the two models of parallel moves, the worst graphs are quite different from the worst sequential graphs, while in the other model of parallelism, there is little difference with the sequential situation.

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S . The independent domination number, i ( G ) , of G is the minimum cardinality of an independent dominating set. In this paper, we extend the work of Henning, Lowenstein, and Rautenbach (2014) who proved that if G is a bipartite, cubic graph of order n and of girth at least 6 , then i ( G ) ≤ 4 11 n . We show that the bipartite condition can be relaxed, and prove that if G is a cubic graph of order n and of girth at least 6 , then i ( G ) ≤ 4 11 n .