LN12 NP-complete problems Flashcards
How can the shortest paths in a Directed Acyclic Graph (DAG) be efficiently computed?
By using a topological order, which allows computing shortest paths in O(m) time by iterating from the source node and updating distances for each edge.
Why can we apply the same algorithm for longest paths in DAGs by replacing min with max?
Since DAGs have no cycles, paths can be extended without revisiting nodes, making the approach safe for finding maximum distances.
What is the Union-Find data structure used for in Kruskal’s MST algorithm?
Union-Find helps efficiently check if adding an edge would form a cycle by determining if two nodes belong to the same component, maintaining disjoint sets as trees.
Describe the Union-Find optimization known as “path compression.”
Path compression flattens the structure of the tree by making all nodes on the path point directly to the root, reducing future search times for Find operations.
How does the greedy algorithm for Interval Partitioning work?
Intervals are sorted by their start times, and each interval is assigned to the first subset where it does not overlap with any interval, minimizing the number of subsets.
Explain the duality-based proof technique for the Interval Partitioning greedy algorithm.
The proof shows that the algorithm achieves the minimum possible number of partitions by equating the maximum overlapping intervals as a lower bound on required partitions.
Why is finding the longest path NP-complete in general graphs, but feasible in DAGs?
In general graphs, longest paths can contain cycles, making the problem exponentially complex. In DAGs, no cycles exist, enabling linear time solutions with topological order.
What purpose does sorting edges serve in Kruskal’s algorithm for MST?
Sorting edges by cost ensures each addition to the MST is the cheapest option, enabling optimal MST construction.
How does Union-by-size improve the efficiency of Union operations in Union-Find?
Union-by-size links the smaller tree to the root of the larger tree, minimizing the number of relabelings and reducing tree depth.
Why can shortest paths in DAGs be solved with a dynamic programming approach?
The directed acyclic structure allows updating shortest distances in a single pass following the topological order, treating each subpath as an independent subproblem.
What is the time complexity for computing shortest paths in a DAG?
The complexity is O(n + m), where n is the number of nodes and m is the number of edges, due to single-pass processing of each edge.
How does the greedy approach in Interval Partitioning ensure optimality?
The algorithm minimizes partitions by assigning each interval to the earliest possible subset, achieving the lower bound on subsets required due to maximum overlaps.
In Union-Find, how many times can an element be relabeled in the worst case?
Each element can be relabeled at most log₂(n) times, as each Union operation doubles the set size, leading to an O(n log n) time bound.
What is the role of duality in optimization problems like Interval Partitioning?
Duality provides a lower bound on the primal solution by establishing a maximum condition that must be met, ensuring optimality when the primal solution meets this bound.
Describe the key difference between BFS-based shortest paths and Dijkstra’s algorithm in non-negative edge-weighted graphs.
BFS is optimal for unit weights by processing nodes layer by layer, while Dijkstra’s uses a priority queue to manage varying weights, selecting the minimum distance nodes iteratively.
