This paper presents a largely improved version of the VF2 algorithm for the Subgraph Isomorphism Problem. The improvements are twofold. Firstly, it is based on a new approach for determining the ...matching order of the nodes, and secondly, more efficient — nevertheless easier to compute — cutting rules are proposed. They together reduce the search space significantly.
In addition to the usual Subgraph Isomorphism Problem, the paper also presents specialized algorithms for the Induced Subgraph Isomorphism and for the Graph Isomorphism Problems.
Finally, an extensive experimental evaluation is provided using a wide range of inputs, including both real-life biological and chemical datasets and standard randomly generated graph series. The results show major and consistent running time improvements over the other known methods.
The C++ implementations of the algorithms are available open-source as part of the LEMON graph and network optimization library.
We present and compare various methods to construct efficient QUBO formulations for the Graph Isomorphism Problem—one of a very few problems in NP that is neither known to be solvable in polynomial ...time nor NP-complete—and two related Subgraph Isomorphism Problems that are NP-hard. Experimental results on two QUBO formulations of the Graph Isomorphism Problem suggest that our direct formulation is more practical than the others with respect to running on the D-Wave architecture.
•An efficient direct QUBO objective function F for the Graph Isomorphism Problem is proposed.•An efficient QUBO objective function F for the Graph Isomorphism Problem via reduction to the Clique Problem is proposed.•The above constructions have been extended for the (Induced) Subgraph Isomorphism Problem(s).•Experimental results comparing the efficiency of the QUBO formulations is pesented.
The paper proposes a parallel algorithm for solving the graph-subgraph isomorphism problem and makes an experimental study of its efficiency. The problem is one of the most well-known NP-complete ...problems. Its solution may be required when solving many practical problems associated with the study of complex structures. We solve the problem in a formulation that requires finding all the existing isomorphic substitutions or proving their absence. Due to the complexity of the problem, it is natural to want to speed up its solution by parallelizing the algorithm. We use the RPM_ParLib library, developed by the author, as the main tool to program the algorithm. This library allows us to develop effective applications for parallel computing on a local network under the control of the runtime environment .NET Framework. Due to this library, the applications have the ability to generate parallel branches of computation directly during program execution and dynamically redistribute work between computing modules. Any language with support of the .NET Framework can be used as a programming language in conjunction with this library. For the numerical experiment, an open database from the Internet was used, which was specially developed to study algorithms for searching for isomorphic substitutions. The author has also developed a special application in C# for generating additional sets of initial data with the specified characteristics. The aim of the experiment is to study the speedup achieved due to the recursively parallel organization of computations. This paper provides a detailed description of the proposed algorithm and the results obtained during the experiment.
Quantum computations are typically performed as a sequence of basic operations, called quantum gates. Different gate sequences, called quantum circuits, can implement the same overall quantum ...computation. Since every additional quantum gate takes time and introduces noise into the system, it is important to find the smallest possible quantum circuit that implements a given computation, especially for near-term quantum devices that can execute only a limited number of quantum gates before noise renders the computation useless. An important building block for many quantum circuit optimization techniques is pattern matching: given a large and small quantum circuit, we would like to find all maximal matches of the small circuit, called a pattern, in the large circuit, considering pairwise commutation of quantum gates. In this work, we present the first classical algorithm for pattern matching that provably finds all maximal matches and is efficient enough to be practical for circuit sizes typical for near-term devices. We demonstrate numerically1 that combining our algorithm with known pattern-matching-based circuit optimization techniques reduces the gate count of a random quantum circuit by ∼ 30% and can further improve practically relevant quantum circuits that were already optimized with state-of-the-art techniques.
Graph pattern matching is a key problem in many applications which data is represented in the form of a graph, and this problem is generally defined as a subgraph isomorphism. In this paper, we ...analyze an incremental hybrid genetic algorithm for the subgraph isomorphism problem considering various design issues to improve the performance of the algorithm. An incremental hybrid genetic algorithm was previously suggested to solve the subgraph isomorphism problem and have shown good performance. It decomposes the problem into a sequence of consecutive subproblems which has an optimal substructure. Each subproblem is solved by the hybrid genetic algorithm and the solutions obtained are extended to be applied to the next subproblem as initial solutions. We examine a wide range of schemes that determine the overall performance of the incremental process and make a number of experiments to verify the effectiveness of each scheme with the synthetic dataset of random graphs. We show that the performance of incremental approach can be significantly improved compared to the previous representative studies by applying appropriate schemes found by the experiments. In addition, we also investigate the effect of different genetic parameters and identify the scalability of our method by conducting experiments using real world dataset with large-sized graphs.
In this paper, we study a certain case of a subgraph isomorphism problem. We consider the Hasse diagram of the lattice Mk (the unique lattice with k + 2 elements and one anti-chain of length k) and ...find the maximal k for which it is isomorphic to a subgraph of the reduction graph of a given one-rule string rewriting system. We obtain a complete characterization for this problem and show that there is a dichotomy. There are one-rule string rewriting systems for which the maximal such k is 2 and there are cases where there is no maximum. No other intermediate option is possible.
Celotno besedilo
Dostopno za:
DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
Let
v
(
F
) denote the number of vertices in a fixed connected pattern graph
F
. We show an infinite family of patterns
F
such that the existence of a subgraph isomorphic to
F
is expressible by a ...first-order sentence of quantifier depth 2/3
v
(
F
) + 1, assuming that the host graph is sufficiently large and connected. However, this is impossible for any
F
using less than 2/3
v
(
F
) - 2 first-order variables.
The big graph database provides strong modeling capabilities and efficient querying for complex applications. Subgraph isomorphism which finds exact matches of a query graph in the database ...efficiently, is a challenging problem. Current subgraph isomorphism approaches mostly are based on the pruning strategy proposed by Ullmann. These techniques have two significant drawbacks- first, they are unable to efficiently handle complex queries, and second, their implementations need the large indexes that require large memory resources. In this paper, we describe a new subgraph isomorphism approach, the HyGraph algorithm, that is efficient both in querying and with memory requirements for index creation. We compare the HyGraph algorithm with two popular existing approaches, GraphQL and Cypher using complexity measures and experimentally using three big graph data sets—(1) a country-level population database, (2) a simulated bank database, and (3) a publicly available World Cup big graph database. It is shown that the HyGraph solution performs significantly better (or equally) than competing algorithms for the query operations on these big databases, making it an excellent candidate for subgraph isomorphism queries in real scenarios.
Let
F
be a connected graph with
ℓ
vertices. The existence of a subgraph isomorphic to
F
can be defined in first-order logic with quantifier depth no better than
ℓ
, simply because no first-order ...formula of smaller quantifier depth can distinguish between the complete graphs
K
ℓ
and
K
ℓ
− 1
. We show that, for some
F
, the existence of an
F
subgraph in
sufficiently large connected
graphs is definable with quantifier depth
ℓ
− 3. On the other hand, this is never possible with quantifier depth better than
ℓ
/2. If we, however, consider definitions over connected graphs with
sufficiently large treewidth
, the quantifier depth can for some
F
be arbitrarily small comparing to
ℓ
but never smaller than the treewidth of
F
. Moreover, the definitions over
highly connected graphs
require quantifier depth strictly more than the density of
F
. Finally, we determine the exact values of these descriptive complexity parameters for all connected pattern graphs
F
on 4 vertices.
Given a graph $F$, let $I(F)$ be the class of graphs containing $F$ as an induced subgraph. Let $WF$ denote the minimum $k$ such that $I(F)$ is definable in $k$-variable first-order logic. The ...recognition problem of $I(F)$, known as Induced Subgraph Isomorphism (for the pattern graph $F$), is solvable in time $O(n^{WF})$. Motivated by this fact, we are interested in determining or estimating the value of $WF$. Using Olariu's characterization of paw-free graphs, we show that $I(K_3+e)$ is definable by a first-order sentence of quantifier depth 3, where $K_3+e$ denotes the paw graph. This provides an example of a graph $F$ with $WF$ strictly less than the number of vertices in $F$. On the other hand, we prove that $WF=4$ for all $F$ on 4 vertices except the paw graph and its complement. If $F$ is a graph on $t$ vertices, we prove a general lower bound $WF>(1/2-o(1))t$, where the function in the little-o notation approaches 0 as $t$ inreases. This bound holds true even for a related parameter $W^*F\le WF$, which is defined as the minimum $k$ such that $I(F)$ is definable in the infinitary logic $L^k_{\infty\omega}$. We show that $W^*F$ can be strictly less than $WF$. Specifically, $W^*P_4=3$ for $P_4$ being the path graph on 4 vertices. Using the lower bound for $WF$, we also obtain a succintness result for existential monadic second-order logic: A usage of just one monadic quantifier sometimes reduces the first-order quantifier depth at a super-recursive rate.
PDF
