JIZZ Wikipedia: Input: Two graphs G1 and G2. Question: What is the largest induced subgraph of G1 isomorphic to an induced subgraph of G2? I am trying to develop a C program to solve the decision MCS problem. i.e., given graphs G1, G2 and an integer k, decide whether G1 contains an induced subgraph of at least k edges isomorphic to an induced subgraph of G2 I am not looking for the fastest algorithm, but the easiest one to implement (bruteforce). I just need an explanation on how to solve this problem. What data structures should i use (other than adjacency list or adjacency matrix)? An explanation or a simple drawing on how to find a solution would be great :)
CSGeek I don't know. Tell us what you've tried so far.. The bruteforcing technique is explained on the Web somewhere.
JIZZ Can you provide a link for the bruteforce solution? i found nothing! all i found are some papers relating to solving biology/chemistry problems with MCS I haven't tried anything yet. I have no idea how/where to start.
geek a simple solution: 1. generate all induced subgraphs of G1 and G2 with at least k edges (all subsets, with cardinality greater than or equal to k, of the edge sets E1 and E2. see how to generate combinations. fill missing edges) 2. test the subgraphs with the same edge count and vertex count for isomorphism (two graphs are isomorphic if their adjacency matrices are permutations of each other. reorder the vertices until the adjacency matrices/lists match or you run out of permutations) 3. pray that it returns an answer this year 4. it did? you can't get the implementation right the first n tries, go back to 1 alternatively, if you're allowed to use a clique solver, build the modular product graph and apply the solver (as described on wikipedia)