15
$\begingroup$

Consider the following problem: Given a query graph $G = (V, E)$ and a reference graph $G' = (V', E')$, we want to find the injective mapping $f : V \rightarrow V'$ which minimizes the number of edges $(v_1, v_2) \in E$ such that $(f(v_1), f(v_2)) \notin E'$. This is a generalization of the subgraph isomorphism problem where we allow the subgraphs to be isomorphic up to a few missing edges and want to find the way to minimize the number of missing edges.

I would also be interested in the weighted version of this problem, where vertex couples $(v_1, v_2) \in V^2$ carry a weight $w(v_1, v_2)$ (which must be zero if $(v_1, v_2) \notin E)$, and likewise for $G'$, and we wish to minimize $\sum_{v_1, v_2} (\max(0, w(v_1, v_2) - w(f(v_1), f(v_2))))$ (the $\max$ is there to only penalize weights from the query graph being larger than those of the reference graph).

My question are: Has this problem already been studied? Does it have a well-known name? Are there any efficient approximation algorithms known?

The motivation of this problem (apart from the fact that it seems like a natural generalization of the subgraph isomorphism problem) is that it is a nice way to make a table plan for a party: the query graph is the graph of guests with edge weights representing the extent to which two people want to interact, the reference graph has the table seats as vertices and edge weights indicating to what extent communication is possible, the solution of the problem is a mapping from people to table seats which respects the social structure to the fullest possible extent.

Improve this question
$\endgroup$
2
  • $\begingroup$ Why do you need "induced" in the title? $\endgroup$
    – Yota Otachi
    May 30, 2012 at 23:16
  • $\begingroup$ @Yota Otachi: Because I messed up. Thanks! $\endgroup$
    – a3nm
    May 30, 2012 at 23:38

1 Answer 1

Reset to default
7
$\begingroup$

Your problem is Maximum Common Edge Subgraph Problem (Max CES) defined as follows: given two graphs $G$ and $G'$, find a graph $H$ with the maximum number of edges that is isomorphic to a subgraph of $G$ and to a subgraph of $G'$.

Proof: You are finding a subgraph $H$ of $G$ isomorphic to a subgraph of $G'$, where $|E_{G}| - |E_{H}|$ is minimized. Since $|E_{G}|$ is an invariant of $G$, $|E_{G}| - |E_{H}|$ is minimized if and only if $|E_{H}|$ is maximized. Clearly, $H$ is isomorphic to a subgraph of $G$ and to a subgraph of $G'$. Q.E.D.

Approximability. In the Ph.D thesis of Kann, I found the description "not known to be approximable within a constant" [3] (p. 115). In a recent paper by Bahiense et al. [1], it is mentioned that if $|V_{G}|$ and $|V_{G'}|$ are not required to be equal, the problem becomes APX-hard. But the citation for this result is an unpublished private communication [2].

  1. L. Bahiense, G. Manic, B. Piva, C.C. de Souza. The maximum common edge subgraph problem: A polyhedral investigation. Discrete Applied Mathematics, to appear. doi:10.1016/j.dam.2012.01.026
  2. M.M. Halldorsson, Personal communication, unpublished manuscript, 1994.
  3. V. Kann. On the Approximability of NP-complete Optimization Problems. Ph.D. Thesis, NADA report TRITA-NA-9206, 1992. http://www.nada.kth.se/~viggo/papers/phdthesis.pdf
Improve this answer
$\endgroup$
4
  • $\begingroup$ It looks like this is indeed equivalent to my problem. Thanks a lot! Are you aware of results on a weighted version of Max CES? $\endgroup$
    – a3nm
    Jun 4, 2012 at 16:45
  • $\begingroup$ I have no idea on weighted version. I think $\max_{v_1,v_2} \max (\ldots)$ should be $\sum_{v_1,v_2} \max (\ldots)$, right? $\endgroup$
    – Yota Otachi
    Jun 4, 2012 at 23:17
  • $\begingroup$ Yes, the sum is more natural if we want to generalize the unweighted case, though I guess it could make sense to minimize the sum of squares or any function of the weight difference. $\endgroup$
    – a3nm
    Jun 5, 2012 at 12:07
  • $\begingroup$ Thanks for editing. I agree, it's natural to use the sum of weight differences (or any function on it) as penalty. $\endgroup$
    – Yota Otachi
    Jun 5, 2012 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.