The Problem

An "insect graph" is an unweighted, directed graph resembling an insect in that one vertex - the "body" - appears to have two "antennae" and six "legs". (In the diagram below, there is no particular significance to the vertex labels, other than to highlight that said antennae and legs are edges whose endpoints are vertices.)

We are interested in two related problems:

1. IS-INSECT-GRAPH-PROBLEM (IIGP): Is an arbitrary graph G an "insect graph", i.e. does it have the configuration described above?

2. CONTAINS-INSECT-GRAPH-PROBLEM (CIGP): Does an arbitrary graph G contain an "insect graph", i.e. does it have a subgraph (subsets of vertices and edges) with the configuration above?

Imagine you are giving a lecture on this "Insect Graph Problem": Discuss it the way we might in class, including:

• present pseudocode for several algorithmic approaches to these problems, starting with Brute Force but also consider techniques such as Parallelization, Randomization, Greedy Strategy, Pre-processing, etc. that offer improvement over brute force

• analyze and justify the time complexity of your algorithms for Adjacency Table and Adjacency Matrix graph representations

• conclude which approaches are best suited, and what "it depends" on

Approximate Grading Rubric:

• 20 points for Brute-Force approach to IIGP and CIGP, including analysis for Adj. Matrix and Table

• 15 points for advanced design approach #1 to IIGP and CIGP, including analysis for Adj. Matrix and Table

• 15 points for advanced design approach #2 to IIGP and CIGP, including analysis for Adj. Matrix and Table

• If you have additional approaches, we will count your best approaches and analyses

D a e f f h