How to reduce a Subgraph Isomorphism problem to an instance of the Hamiltonian Cycle problem (not the other way around)?
1
- $\begingroup$ If you claim that you have a polynomial time algorithm for Hamiltonian Cycle and need a polynomial time algorithm for Subgraph Isomorphism, that should be your question. $\endgroup$Ainsley H.– Ainsley H.2024-06-16 07:16:55 +00:00Commented Jun 16, 2024 at 7:16
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
4 Let $G$ be a graph and $H=C_n$.
- $\begingroup$ This is not the (implied) reduction asked in the question. I am looking for SI --to --> HC reduction. Not otherway around. Even a reduction to SAT from SI would be helpful (using Cook-Levin Theorem) $\endgroup$Javaid Aslam– Javaid Aslam2024-06-14 23:02:46 +00:00Commented Jun 14, 2024 at 23:02
- $\begingroup$ Well, SI is a generalization of HC, so it is a proof of the NP-hardness of SI. $\endgroup$Ainsley H.– Ainsley H.2024-06-15 05:09:07 +00:00Commented Jun 15, 2024 at 5:09
- $\begingroup$ Yes, but that was not my question. Your "answer" is well known!I have a P-time solution to HC. If I can find an existing reduction of SI--> HC, then I could solve SI too. The only other way is to go through the long path of SI--> SAT --> HC. And even SI--> SAT is not known. $\endgroup$Javaid Aslam– Javaid Aslam2024-06-15 17:25:42 +00:00Commented Jun 15, 2024 at 17:25
- $\begingroup$ I see... you have a polynomial time algorithm for Hamiltonian Cycle and need one for Subgraph Isomorphism? $\endgroup$Ainsley H.– Ainsley H.2024-06-15 21:04:47 +00:00Commented Jun 15, 2024 at 21:04