SUBGRAPH and SplitSum

Edit the RMarkdown source file for this assignment in RStudio. When you finish, Knit the file to HTML and upload the .html output to Canvas.

Reduction Arguments

To prove that a new problem \(\mathcal{A}\) is NP-hard, you must show that a known NP-hard problem \(\mathcal{B}\) can be solved in polynomial time, given a polynomial time solver for \(\mathcal{A}\). This is called “a reduction from \(\mathcal{B}\).”

In a reduction argument for decision problems, make sure you include three things:

• A clear description of how to solve an instance of \(\mathcal{B}\) using your hypothetical polynomial-time solver for \(\mathcal{A}\).
• An explanation of why it only takes polynomial time to construct this reduction.
• An if-and-only-if argument demonstrating both directions:
  • If the answer to an instance of \(\mathcal{A}\) is YES, then the answer to the corresponding instance of \(\mathcal{B}\) is YES.
  • If the answer to an instance of \(\mathcal{B}\) is YES, then the answer to the corresponding instance of \(\mathcal{A}\) is YES.

So far we have a library of NP-hard decision problems you can reduce from: SAT, 3SAT, IndSet, VertexCover, Clique, 3Color, REP-SET, SubsetSum, etc.

1. Consider the decision problem SUBGRAPH: Given a graph \(G\) and another graph \(H\), is there a subgraph of \(G\) that has the same structure as \(H\)? Prove that SUBGRAPH is NP-hard.

2. Consider the decision problem SplitSum: Given a set \(X\) of positive integers, is there a way to split \(X\) into disjoint subsets \(A\) and \(B\) such that the sum of the elements in \(A\) equals the sum of the elements in \(B\)? Prove that SplitSum is NP-hard.