Search

Subgraph counting aims to count occurrences of a template T in a given network G(V, E). It is a powerful graph analysis tool and has found real-world applications in diverse domains. Scaling subgraph counting problems is known to be memory bounded and computationally challenging with exponential complexity. Although scalable parallel algorithms are known for several graph problems such as Triangle Counting and PageRank, this is not common for counting complex subgraphs. Here we address this challenge and study connected acyclic graphs or trees. We propose a novel vectorized subgraph counting algorithm, named Subgraph2Vec, as well as both shared memory and distributed implementations: 1) reducing algorithmic complexity by minimizing neighbor traversal; 2) achieving a highly-vectorized implementation upon linear algebra kernels to significantly improve performance and hardware utilization. 3) Subgraph2Vec improves the overall performance over the state-of-the-art work by orders of magnitude and up to 660x on a single node. 4) Subgraph2Vec in distributed mode can scale up the template size to 20 and maintain good strong scalability. 5) enabling portability to both CPU and GPU., Comment: arXiv admin note: text overlap with arXiv:1903.04395

We consider a group-theoretic analogue of the classic subset sum problem. In this brief note, we show that the subset sum problem is NP-complete in the first Grigorchuk group. More generally, we show NP-hardness of that problem in weakly regular branch groups, which implies NP-completeness if the group is, in addition, contracting., Comment: v3: final version for journal of Groups, Complexity, Cryptology. arXiv admin note: text overlap with arXiv:1703.07406

Subgraph counting aims to count the occurrences of a subgraph template T in a given network G. The basic problem of computing structural properties such as counting triangles and other subgraphs has found applications in diverse domains. Recent biological, social, cybersecurity and sensor network applications have motivated solving such problems on massive networks with billions of vertices. The larger subgraph problem is known to be memory bounded and computationally challenging to scale; the complexity grows both as a function of T and G. In this paper, we study the non-induced tree subgraph counting problem, propose a novel layered softwarehardware co-design approach, and implement a shared-memory multi-threaded algorithm: 1) reducing the complexity of the parallel color-coding algorithm by identifying and pruning redundant graph traversal; 2) achieving a fully-vectorized implementation upon linear algebra kernels inspired by GraphBLAS, which significantly improves cache usage and maximizes memory bandwidth utilization. Experiments show that our implementation improves the overall performance over the state-of-the-art work by orders of magnitude and up to 660x for subgraph templates with size over 12 on a dual-socket Intel(R) Xeon(R) Platinum 8160 server. We believe our approach using GraphBLAS with optimized sparse linear algebra can be applied to other massive subgraph counting problems and emerging high-memory bandwidth hardware architectures., Comment: 12 pages

We consider a group-theoretic analogue of the classic subset sum problem. It is known that every virtually nilpotent group has polynomial time decidable subset sum problem. In this paper we use subgroup distortion to show that every polycyclic non-virtually-nilpotent group has NP-complete subset sum problem., Comment: 11 pages. To appear in Journal of Symbolic Computation

This work explores a structure of the Deprit perturbation series and its connection to a Kato resolvent expansion. It extends the formalism previously developed for the Hamiltonians linearly dependent on perturbation parameter to a nonlinear case. We construct a canonical intertwining of perturbed and unperturbed averaging operators. This leads to an explicit expression for the generator of the Lie-Deprit transform in any perturbation order. Using this expression, we discuss a regular pattern in the series, non-uniqueness of the generator and normalised Hamiltonian, and the uniqueness of the Gustavson integrals. Comparison of the corresponding computational algorithm with classical perturbation methods demonstrates its competitiveness for Hamiltonians with a limited number of perturbation terms., Comment: 23 pages, 2 figures

We consider several subgroup-related algorithmic questions in groups, modeled after the classic computational lattice problems, and study their computational complexity. We find polynomial time solutions to problems like finding a subgroup element closest to a given group element, or finding a shortest non-trivial element of a subgroup in the case of nilpotent groups, and a large class of surface groups and Coxeter groups. We also provide polynomial time algorithm to compute geodesics in given generators of a subgroup of a free group., Comment: 17 pages, 2 figures

For finitely generated nilpotent groups, we employ Mal'cev coordinates to solve several classical algorithmic problems efficiently. Computation of normal forms, the membership problem, the conjugacy problem, and computation of presentations for subgroups are solved using only logarithmic space and quasilinear time. Logarithmic space presentation-uniform versions of these algorithms are provided. Compressed-word versions of the same problems, in which each input word is provided as a straight-line program, are solved in polynomial time., Comment: Accepted in Transactions of the AMS

The classic knapsack and related problems have natural generalizations to arbitrary (non-commutative) groups, collectively called knapsack-type problems in groups. We study the effect of free and direct products on their time complexity. We show that free products in certain sense preserve time complexity of knapsack-type problems, while direct products may amplify it. Our methods allow to obtain complexity results for rational subset membership problem in amalgamated free products over finite subgroups., Comment: 15 pages, 5 figures. Updated to include more general results, mostly in Section 4

We generalize the classical Post correspondence problem ($\mathbf{PCP}_n$) and its non-homogeneous variation ($\mathbf{GPCP}_n$) to non-commutative groups and study the computational complexity of these new problems. We observe that $\mathbf{PCP}_n$ is closely related to the equalizer problem in groups, while $\mathbf{GPCP}_n$ is connected to the double twisted conjugacy problem for endomorphisms. Furthermore, it is shown that one of the strongest forms of the word problem in a group $G$ (we call it the {\em hereditary word problem}) can be reduced to $\mathbf{GPCP}_n$ in $G$ in polynomial time. The main results are that $\mathbf{PCP}_n$ is decidable in a finitely generated nilpotent group in polynomial time, while $\mathbf{GPCP}_n$ is undecidable in any group containing free non-abelian subgroup (though the argument is very different from the classical case of free semigroups). We show that the double endomorphism twisted conjugacy problem is undecidable in free groups of sufficiently large finite rank. We also consider the bounded $\mathbf{PCP}$ and observe that it is in $\mathbf{NP}$ for any group with $\mathbf{P}$-time decidable word problem, meanwhile it is $\mathbf{NP}$-hard in any group containing free non-abelian subgroup. In particular, the bounded $\mathbf{PCP}$ is $\mathbf{NP}$-complete in non-elementary hyperbolic groups and non-abelian right angle Artin groups., Comment: 13 pages

This work explores the structure of Poincare-Lindstedt perturbation series in Deprit operator formalism and establishes its connection to Kato resolvent expansion. A discussion of invariant definitions for averaging and integrating perturbation operators and their canonical identities reveals a regular pattern in a Deprit generator. The pattern was explained using Kato series and the relation of perturbation operators to Laurent coefficients for the resolvent of Liouville operator. This purely canonical approach systematizes the series and leads to the explicit expression for the Deprit generator in any perturbation order: \[G = - \hat{\mathsf S}_H H_i.\] Here, $\hat{\mathsf S}_H$ is the partial pseudo-inverse of the perturbed Liouville operator. Corresponding Kato series provides a reasonably effective computational algorithm. The canonical connection of perturbed and unperturbed averaging operators allows for a description of ambiguities in the generator and transformed Hamiltonian, while Gustavson integrals turn out to be insensitive to normalization style. Non-perturbative examples are used for illustration., Comment: 33 pages. Version 3: Additional discussion of computational algorithm. The supplementary data files, containing demonstrations and large expressions are available from author

We generalize the classical knapsack and subset sum problems to arbitrary groups and study the computational complexity of these new problems. We show that these problems, as well as the bounded submonoid membership problem, are P-time decidable in hyperbolic groups and give various examples of finitely presented groups where the subset sum problem is NP-complete., Comment: 28 pages, 12 figures

Spinlocks are widely used in database engines for processes synchronization. KGX mutexes is new retrial spinlocks appeared in contemporary Oracle versions for submicrosecond synchronization. The mutex contention is frequently observed in highly concurrent OLTP environments. This work explores how Oracle mutexes operate, spin, and sleep. It develops predictive mathematical model and discusses parameters and statistics related to mutex performance tuning, as well as results of contention experiments., Comment: Proceedings of International Conference on Informatics MEDIAS2012. Cyprus, Limassol, May 7--14, 2012. ISBN 978-5-88835-023-2. 12 pages, 15 figures

Rise of hundreds cores technologies bring again to the first plan the problem of interprocess synchronization in database engines. Spinlocks are widely used in contemporary DBMS to synchronize processes at microsecond timescale. Latches are Oracle RDBMS specific spinlocks. The latch contention is common to observe in contemporary high concurrency OLTP environments. In contrast to system spinlocks used in operating systems kernels, latches work in user context. Such user level spinlocks are influenced by context preemption and multitasking. Until recently there were no direct methods to measure effectiveness of user spinlocks. This became possible with the emergence of Solaris 10 Dynamic Tracing framework. DTrace allows tracing and profiling both OS and user applications. This work investigates the possibilities to diagnose and tune Oracle latches. It explores the contemporary latch realization and spinning-blocking strategies, analyses corresponding statistic counters. A mathematical model developed to estimate analytically the effect of tuning _SPIN_COUNT value., Comment: 14 pages, 6 figures, 6 tables. MEDIAS 2011 Conference. Limassol, Cyprus

Let $G$ be a non-elementary hyperbolic group. Let $w$ be a group word such that the set $w[G]$ of all its values in $G$ does not coincide with $G$ or 1. We show that the width of verbal subgroup $w(G)=$ is infinite. That is, there is no such $l\in\mathbb Z$ that any $g\in w(G)$ can be represented as a product of $\le l$ values of $w$ and their inverses., Comment: To appear in Journal of the London Mathematical Society. 22 pages, 8 figures

Groups acting freely on Z^n-trees (Z^n-free groups) play a key role in the study of non-archimedean group actions. Following Stallings' ideas, we develop graph-theoretic techniques to investigate subgroup structure of Z^n-free groups. As an immediate application of the presented method, we give an effective solution to the Uniform Membership Problem and the Power Problem in Z^n-free groups., Comment: 41 pages

Using graph-theoretic techniques for f.g. subgroups of $F^{\mathbb{Z}[t]}$ we provide a criterion for a f.g. subgroup of a f.g. fully residually free group to be of finite index. Moreover, we show that this criterion can be checked effectively. Also we obtain an analogue of Greenberg-Stallings Theorem for f.g. fully residually free groups, and prove that a f.g. non-abelian subgroup of a f.g. fully residually free group is of finite index in its commensurator., Comment: 21 pages, 1 figure