<p>I recall Jason's thesis had something on this, application was finding differences between versions in a code repository:
<a href="http://archives.ece.iastate.edu/archive/00000493/01/dissertation.pdf" rel="nofollow">http://archives.ece.iastate.edu/archive/00000493/01/dissertation.pdf</a></p>

CC BY-SA 3.0
2013-05-21T21:09:31.277Z
2013-05-21T21:09:31.277Z
Chad Brewbaker
<p>Isn't there a straightforward approximation-preserving reduction from maximum independent set (MIS) in undirected graphs to your problem? </p>

<p>Given undirected graph G=(V,E), form DAG A=(V,E') by ordering the vertices arbitrarily and directing the edges accordingly, then take B=(V,{}) to be the DAG with the same vertices but no edges.</p>

<p>Any subgraph common to A and B corresponds to an independent set in G, and vice versa, no? </p>

<p>If this reduction is correct, then your problem is as hard to approximate as MIS; which is to say, forget about it. :-)</p>

CC BY-SA 3.0
2013-05-20T15:21:29.983Z
2013-05-20T15:21:29.983Z
Neal Young
<p>Suppose we have two directed acyclic graphs $A$ and $B$ and we look to find the subgraph that is common to both graphs and has the most number of vertices. That is to find the biggest graph which is a subgraph of both $A$ and $B$. The vertices are not labeled, but of course, the directions on edges do matter.</p>

<p>Noting that this solves the graph isomorphism, the problem is not known to be solvable in polynomial time. So I was looking for an approximation algorithm. Can you think of any?</p>

CC BY-SA 3.0
2013-05-20T03:00:19.737Z
Isn't there a straightforward approximation-preserving reduction from maximum independent set (MIS) in undirected graphs to your problem?  Given undirected graph G=(V,E), form DAG A=(V,E') by ordering the vertices arbitrarily and directing the edges accordingly, then take B=(V,{}) to be the DAG with the same vertices but no edges.  Any subgraph common to A and B corresponds to an independent set in G, and vice versa, no?  (If this reduction is correct, then your problem is as hard to approximate as MIS; which is to say, forget about it. :-).  What am I missing?
Neal Young
CC BY-SA 3.0
2013-05-20T08:49:53.220Z
You are right Mr.Young . I guess it won't work. I think you should post that as an answer.
Untitled
CC BY-SA 3.0
2013-05-20T15:21:49.447Z
@Unititled: okay.
Neal Young
CC BY-SA 3.0
2013-05-21T15:48:57.300Z
I interpreted the question as wanting the subgraph on the maximum number of edges, not the induced subgraph on the maximum number of vertices...
Andrew D. King
CC BY-SA 3.0
2013-05-21T16:50:54.387Z
@ King. You are right, it looks ambiguous. I'm editing the question.
Untitled
<graph-theory><graph-algorithms><approximation-algorithms>
Approximation algorithm for finding the maximum common subgraph in two DAGs
Untitled
# Approximation algorithm for finding the maximum common subgraph in two DAGs

(Asked by: username_0 on 2013-05-19)

Suppose we have two directed acyclic graphs $A$ and $B$ and we look to find the subgraph that is common to both graphs and has the most number of vertices. That is to find the biggest graph which is a subgraph of both $A$ and $B$. The vertices are not labeled, but of course, the directions on edges do matter.

Noting that this solves the graph isomorphism, the problem is not known to be solvable in polynomial time. So I was looking for an approximation algorithm. Can you think of any?

**Tags:** graph-theory, graph-algorithms, approximation-algorithms
> **Comments:**
> **username_1**: Isn't there a straightforward approximation-preserving reduction from maximum independent set (MIS) in undirected graphs to your problem?  Given undirected graph G=(V,E), form DAG A=(V,E') by ordering the vertices arbitrarily and directing the edges accordingly, then take B=(V,{}) to be the DAG with the same vertices but no edges.  Any subgraph common to A and B corresponds to an independent set in G, and vice versa, no?  (If this reduction is correct, then your problem is as hard to approximate as MIS; which is to say, forget about it. :-).  What am I missing?  
> **username_0**: You are right Mr.Young . I guess it won't work. I think you should post that as an answer.  
> **username_1**: @Unititled: okay.  
> **username_2**: I interpreted the question as wanting the subgraph on the maximum number of edges, not the induced subgraph on the maximum number of vertices...  
> **username_0**: @ King. You are right, it looks ambiguous. I'm editing the question.  

---

## 2 answers

### Answer by username_1 on 2013-05-20. Score: 12 | Accepted answer

Isn't there a straightforward approximation-preserving reduction from maximum independent set (MIS) in undirected graphs to your problem?

Given undirected graph G=(V,E), form DAG A=(V,E') by ordering the vertices arbitrarily and directing the edges accordingly, then take B=(V,{}) to be the DAG with the same vertices but no edges.

Any subgraph common to A and B corresponds to an independent set in G, and vice versa, no?

If this reduction is correct, then your problem is as hard to approximate as MIS; which is to say, forget about it. :-)


---

### Answer by username_3 on 2013-05-21. Score: 2

I recall Jason's thesis had something on this, application was finding differences between versions in a code repository:
<http://archives.ece.iastate.edu/archive/00000493/01/dissertation.pdf>


---

