LN11 Polynomial-time reductions Flashcards
P, NP, NP-completeness, Satisfiability problem
What is the Minimum Spanning Tree (MST) problem in graph algorithms?
The MST problem seeks a tree that spans all nodes in a graph with the minimum total edge cost, useful in network design for minimizing connection costs.
Explain the MST lemma related to partitions of a graph’s node set.
For any partition of nodes into two sets, the cheapest edge between the sets must be part of the MST, as replacing a more expensive edge would reduce the total cost.
Describe Prim’s algorithm for MST.
Prim’s algorithm starts from a node and repeatedly adds the cheapest edge that extends the current tree without forming a cycle, until the tree spans all nodes.
Describe Kruskal’s algorithm for MST.
Kruskal’s algorithm starts with an empty edge set and adds the cheapest edge that does not form a cycle, effectively merging disjoint components until a single spanning tree is formed.
How can Prim’s algorithm be optimized for different types of graphs?
Using adjacency lists results in O(n²) time for dense graphs, while a priority queue can reduce this to O(m log n) for sparse graphs by efficiently selecting and updating the smallest edge.
What is the problem of detecting directed cycles in graphs?
It involves finding a sequence of nodes that form a directed cycle, or verifying if the graph is a Directed Acyclic Graph (DAG).
Why are directed cycles undesirable in task scheduling graphs?
Directed cycles indicate a loop in task dependencies, implying circular prerequisites that make it impossible to complete tasks without violating constraints.
What is a topological order in a directed graph?
A topological order is an ordering of nodes where each directed edge (u, v) points from an earlier to a later node in the order, ensuring no cycles exist.
Describe the basic algorithm for finding a topological order in a DAG.
Repeatedly select a node with no incoming edges, place it in the topological order, remove it and its outgoing edges from the graph, and repeat until all nodes are ordered.
How does DFS help in constructing a topological order?
By ignoring non-tree edges and processing nodes in reverse order upon marking them as explored, DFS can create a valid topological order in O(n + m) time for a DAG.
What is the Longest Paths problem, and why is it important in DAGs?
It seeks the longest path from a source node without revisiting nodes. In DAGs, it reveals critical paths in project scheduling, representing maximum completion time.
What is a priority queue’s role in optimizing Prim’s algorithm?
The priority queue allows efficient selection of the smallest edge connecting the current tree to an outside node, essential for achieving O(m log n) performance in sparse graphs.
Explain the significance of back edges in cycle detection with DFS.
In a directed DFS traversal, a back edge indicates a path from a node to one of its ancestors, forming a directed cycle and confirming the graph is not a DAG.
How can an MST algorithm handle equal edge weights?
By adding small unique perturbations to edges with identical weights, algorithms like Prim’s and Kruskal’s can handle ties without affecting the correctness of the MST result.
What is the critical path in a project schedule represented as a DAG?
The critical path is the longest path in a DAG where edge weights represent task durations, determining the minimum time required to complete all tasks.
