11.1. Reductions

Try these first

1. 1.

   What is a bipartite graph?

   Hint

   Think about how the nodes are structured in pairs.

2. 2.

   What is the goal of a matching problem?

   Hint

   Consider how students are assigned to advisors based on preferences.

3. 3.

   What is a reduction in algorithm design?

   • Transforming one problem into another
   • Simplifying a problem
   • Finding a solution directly

   Hint

   Think of problem-solving strategies.

4. 4.

   True or False: A bipartite graph allows edges only within the same group.

   • True
   • False

   Hint

   Recall how the graph structure is defined.

5. 5.

   Given five teachers and four distinct online courses, develop a flow network that represents their allocations. Ensure that each edge reflects the capacity constraint and identify potential matchings.

   Hint

   Use a diagram to visualize flows.

6. 6.

   Evaluate the implications if a matching problem cannot be efficiently solved. Discuss how this affects related problems in the context of reduction.

   Hint

   Consider what underlying properties might relate the difficulties of both problems.