Editing Subgraph isomorphism problem (section)

==Algorithms==
{{harvtxt|Ullmann|1976}} describes a recursive backtracking procedure for solving the subgraph isomorphism problem. Although its running time is, in general, exponential, it takes polynomial time for any fixed choice of ''H'' (with a polynomial that depends on the choice of ''H''). When ''G'' is a [[planar graph]] (or more generally a graph of [[bounded expansion]]) and ''H'' is fixed, the running time of subgraph isomorphism can be reduced to [[linear time]].<ref name="e99">{{harvtxt|Eppstein|1999}}; {{harvtxt|Nešetřil|Ossona de Mendez|2012}}</ref>

{{harvtxt|Ullmann|2010}} is a substantial update to the 1976 subgraph isomorphism algorithm paper.

{{harvtxt|Cordella|2004}} proposed in 2004 another algorithm based on Ullmann's, VF2, which improves the refinement process using different heuristics and uses significantly less memory.

{{harvtxt|Bonnici|Giugno|2013}} proposed a better algorithm, which improves the initial order of the vertices using some heuristics.

The current state of the art solver for moderately-sized, hard instances is the Glasgow Subgraph Solver ({{harvtxt|McCreesh|Prosser|Trimble|2020}}).<ref>For an experimental evaluation, see {{harvtxt|Solnon|2019}}.</ref> This solver adopts a constraint programming approach, using bit-parallel data structures and specialized propagation algorithms for performance. It supports most common variations of the problem and is capable of counting or enumerating solutions as well as deciding whether one exists.

For large graphs, state-of-the art algorithms include CFL-Match and Turboiso, and extensions thereupon such as DAF by {{harvtxt|Han|Kim|Gu|Park|2019}}.