 # Subgraph Isomorphism, Independent Set, and Scheduling with Profits and Deadlines NP Problems

Subject Computer Science Data Structures and Algorithms

## Question

Check the attached three problems.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

Problem 34.5-1
The first part is to prove that our problem (subgraph-isomorphism) is in NP class.
For an instance (G1,G2) it can be considered a map from the vertices of G1 to those of G2. This will show which vertices of the graph G2 correspond to nodes of G1. So if f: V1->V2 is the mapping, where G1(V1, E1) and G2(V2, E2), the certificate will verify if f is one-to-one function and whether for any two vertices a, b from V1, the edge (a,b) belongs to G1 if and only if the edge (f(a),f(b)) belongs to G2. Since we have at most n^2 pairs, it means the certificate runs in quadratic polynomial time. In conclusion the isomorphism between G1 and a specified subgraph of G2 can be verified in polynomial time => subgraph isomorphism is in NP....

This is only a preview of the solution. Please use the purchase button to see the entire solution

## Related Homework Solutions

Algorithm Analysis Recurrence Questions \$35.00
Algorithm
Analysis
Recurrence
Question
BST
Binary
Tree
Search
Distinct
Way
Stair
Master
Theorem
Algorithm Analysis, Correctness and Sorted Linked List Algorithm \$10.00
Algorithm
List
Loop
Invariant
Worst
Case
Analysis
Complexity
Correctness
Ascending
Initialization
Maintenance
Termination
Computer Science - Algorithm Assignment \$25.00
Algorithm
Computer Science
Dynamic Programming
Longest Increasing Subsequence
Array
Benchmarking Bellman-Ford's Algorithm \$38.00
Bellman Ford
Algorithm
Graph
Single Source
Shortest Path
Critical Operation
Big-O
Analysis
Documentation
Test Plan
Complexity
Benchmark
Approach
Improvement
Dijkstra
Relaxation
Edge
Node
Lessons Learned
Live Chats