Maximum common edge subgraph: Difference between revisions
No edit summary |
|||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
{{one source |date=April 2024}} |
|||
Given two [[Graph (discrete mathematics)|graph]]s <math>G</math> and <math>G'</math>, the '''maximum common edge subgraph problem''' is the problem of finding a graph <math>H</math> with as many edges as possible which is [[graph isomorphism|isomorphic]] to both a [[Glossary_of_graph_theory#Subgraphs|subgraph]] of <math>G</math> and a subgraph of <math>G'</math>. |
Given two [[Graph (discrete mathematics)|graph]]s <math>G</math> and <math>G'</math>, the '''maximum common edge subgraph problem''' is the problem of finding a graph <math>H</math> with as many edges as possible which is [[graph isomorphism|isomorphic]] to both a [[Glossary_of_graph_theory#Subgraphs|subgraph]] of <math>G</math> and a subgraph of <math>G'</math>. |
||
The maximum common edge subgraph problem on general graphs is [[NP-complete]] as it is a generalization of [[subgraph isomorphism]]: a graph <math>H</math> is isomorphic to a subgraph of another graph <math>G</math> if and only if the maximum common edge subgraph of <math>G</math> and <math>H</math> has the same number of edges as <math>H</math>. |
The maximum common edge subgraph problem on general graphs is [[NP-complete]] as it is a generalization of [[subgraph isomorphism]]: a graph <math>H</math> is isomorphic to a subgraph of another graph <math>G</math> if and only if the maximum common edge subgraph of <math>G</math> and <math>H</math> has the same number of edges as <math>H</math>. The problem is [[APX-hard]], unless the two input graphs <math>G</math> and <math>G'</math> are required to have the same number of vertices.<ref>{{citation |
||
| last1 = Bahiense | first1 = L. |
| last1 = Bahiense | first1 = L. |
||
| last2 = Manic | first2 = G. |
| last2 = Manic | first2 = G. |
||
Latest revision as of 12:22, 27 November 2024
 | This article relies largely or entirely on a single source. (April 2024) |
Given two graphs and , the maximum common edge subgraph problem is the problem of finding a graph with as many edges as possible which is isomorphic to both a subgraph of and a subgraph of .
The maximum common edge subgraph problem on general graphs is NP-complete as it is a generalization of subgraph isomorphism: a graph is isomorphic to a subgraph of another graph if and only if the maximum common edge subgraph of and has the same number of edges as . The problem is APX-hard, unless the two input graphs and are required to have the same number of vertices.[1]
See also
[edit]- Maximum common subgraph isomorphism problem
- Subgraph isomorphism problem
- Induced subgraph isomorphism problem
References
[edit]- ^ Bahiense, L.; Manic, G.; Piva, B.; de Souza, C. C. (2012), "The maximum common edge subgraph problem: A polyhedral investigation", Discrete Applied Mathematics, 160 (18): 2523–2541, doi:10.1016/j.dam.2012.01.026.
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |
 | This graph theory-related article is a stub. You can help Wikipedia by expanding it. |