Live briefing
Everything about Subgraph isomorphism problem
Problem in theoretical computer science
In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs and are given as input, and one must determine whether contains a subgraph that is isomorphic to . Subgraph isomorphism is a generalization of both the maximum clique problem and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete. However certain other cases of subgraph isomorphism may be solved in polynomial time. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Subgraph isomorphism problemA 5-minute orientation
- Skim a recent paper: LAD2025, A constraint-based solver for the subgraph isomorphism problemInfluential work since 2022
- Pick up a classic book: Algorithms in computational molecular biologyThe most-reprinted book on the subject
- Read the landmark paper: Subgraph Isomorphism in Planar Graphs and Related ProblemsCited 183 times
- Go sideways: Maximum common edge subgraphA closely related topic
- Go sideways: Graph isomorphism problemA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Subgraph Isomorphism in Planar Graphs and Related Problems
Solving subgraph isomorphism problems with constraint programming
The subgraph isomorphism problem for outerplanar graphs
Improvements to Ullmann's Algorithm for the Subgraph Isomorphism Problem
PathLAD+: Towards effective exact methods for subgraph isomorphism problem
Approximating the maximum common subgraph isomorphism problem with a weighted graph
Investigation of incremental hybrid genetic algorithm with subgraph isomorphism problem
On parallel complexity of the subgraph homeomorphism and the subgraph isomorphism problem for classes of planar graphs
🆕 Influential since 2022
LAD2025, A constraint-based solver for the subgraph isomorphism problem
Recursive-Parallel Algorithm for Solving the Graph-Subgraph Isomorphism Problem
Recursive-Parallel Algorithm for Solving the Graph-Subgraph Isomorphism Problem
Evolutionary algorithms for the optimization variant of the graph-subgraph isomorphism problem
On the computational power of the light: An optical method for the subgraph isomorphism problem
📚 Books worth reading
Algorithms in computational molecular biologyMourad Elloumi · 2010
Graph theory with applications to engineering and computer scienceNarsingh Deo, Narsingh Deo · 1974
2000 Solved Problems in Discrete MathematicsSeymour Lipschutz · 1991
Graph-Theoretic Concepts in Computer ScienceMartin Charles Golumbic · 2012
Discrete mathematical structures for computer scienceRonald E. Prother, Ronald E. Prather · 1976
Discrete mathematics for computer scienceGary Haggard · 2006
Rational Drug DesignDonald G. Truhlar · 1999
Discrete MathmaticsR. K. Bisht, H. S. Dhami · 2015
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Maximum common edge subgraph Given two graphs G {\displaystyle G} and G ′ {\displaystyle G'} , the maximum common edge subgraph problem (or MCES problem) is the problem of finding…
- Graph isomorphism problem Unsolved problem in computer science Can the graph isomorphism problem be solved in polynomial time? More unsolved problems in computer science The graph…
- Maximum common induced subgraph In graph theory and theoretical computer science, a maximum common induced subgraph of two graphs G and H is a graph that is an induced subgraph of both…
- NP-completeness In computational complexity theory, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. NP is short for "nondetermi…
- Induced subgraph isomorphism problem In complexity theory and graph theory, induced subgraph isomorphism is an NP-complete decision problem that involves finding a given graph as an induced…
- List of NP-complete problems This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems. As there are thousands of such problems…
- Graph isomorphism In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f:V(G)→V(H) such that any two vertices u and v of G…
- Feedback vertex set In the mathematical discipline of graph theory, a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles…