1
$\begingroup$

I am working on proving the NP-hardness of a problem by reducing it from the subgraph isomorphism problem. Currently, I can reduce it from the following problem:

Problem 1: Given two graphs $G=(V, E)$ and $H=(V', E')$, is there a subgraph $G_0$ of $G$ that is isomorphism to $H$ under a linear mapping of vertices?

But the original subgraph isomorphism problem is defined as:

Problem 2: Given two graphs $G=(V, E)$ and $H=(V', E')$, is there a subgraph $G_0$ of $G$ that is isomorphism to $H$ under a bijection of vertices?

Can anybody tell me how to further reduce Problem 1 from Problem 2?

Edit: say I have the following graphs where $A_i, b_j \in \mathbb{R}$, and I want to see if there is a linear function parameterized by $\beta$ in the form of $b_j=\beta A_i$ that can make $G_0$ and $H$ isomorphism.

Note that the figure is just for demo and we don't know if $H$ is a complete graph.

enter image description here

Improve this question
$\endgroup$
10
  • 4
    $\begingroup$ I don't know what is meant by "linear mapping of vertices." $\endgroup$
    – Gerry Myerson
    Commented Jun 9, 2021 at 4:38
  • $\begingroup$ It means that the bijection should be linear $\endgroup$
    – lisi
    Commented Jun 10, 2021 at 0:57
  • $\begingroup$ Sure, but what does "linear" mean, when we're talking about graphs? I know linear $y=ax+b$ from analytic geometry, and I know linear from linear transformations on vector spaces, but I don't know linear for graphs. $\endgroup$
    – Gerry Myerson
    Commented Jun 10, 2021 at 1:13
  • $\begingroup$ Sorry for this. Let's consider the value of the vertices as in a vector space and then linear means linear transformation $\endgroup$
    – lisi
    Commented Jun 10, 2021 at 5:04
  • $\begingroup$ I don't know what you mean by "the value of the vertices". Maybe you can give an example of two graphs, and a linear map between them? $\endgroup$
    – Gerry Myerson
    Commented Jun 10, 2021 at 6:24

0

Reset to default

You must log in to answer this question.