FPT Dynamic programming Flashcards
What is the Independent Set Problem?
Finding a subset of nodes in a graph such that no two nodes in the subset are adjacent.
What makes solving problems on trees different from general graphs?
Trees have no cycles and are structurally simpler, allowing problems to be solved efficiently with dynamic programming or greedy methods.
What is the key advantage of working on trees for NP-hard problems?
Subproblems on subtrees only interact through their roots, enabling a divide-and-conquer approach.
What is the greedy algorithm for finding an independent set on trees?
Start with a leaf node, include it in the independent set, remove it and its neighbor, and repeat until the tree is empty.
Why does the greedy algorithm work for independent sets on trees?
Every tree has at least one leaf, and including a leaf is always part of some maximum independent set.
What is a forest in graph theory?
A graph consisting of multiple disconnected trees.
How does the greedy algorithm handle forests?
It applies the same logic to each tree in the forest independently.
What is the time complexity of the greedy independent set algorithm on trees?
O(n), where n is the number of nodes in the tree.
What is the Maximum-Weight Independent Set Problem?
Finding an independent set in a graph where the total weight of the nodes in the set is maximized.
How does Maximum-Weight Independent Set differ from the unweighted version?
Each node has a weight, so choosing nodes must consider both independence and weight optimization.
What is the difficulty in solving Maximum-Weight Independent Set on trees?
Deciding locally whether to include a node or its neighbor requires considering global effects on the tree’s structure and weights.
What are the two subproblems for Maximum-Weight Independent Set on trees?
OPTin(u): Maximum weight including node u. OPTout(u): Maximum weight excluding node u.
What is the recurrence relation for OPTin(u) in Maximum-Weight Independent Set?
OPTin(u) = wu + sum(OPTout(v) for v in children(u)), where wu is the weight of u.
What is the recurrence relation for OPTout(u) in Maximum-Weight Independent Set?
OPTout(u) = sum(max(OPTin(v), OPTout(v)) for v in children(u)).
How does dynamic programming solve the Maximum-Weight Independent Set Problem?
By building solutions for subtrees recursively from leaves to the root using the OPTin and OPTout recurrences.
What is the significance of post-order traversal in the dynamic programming solution?
It ensures children are processed before their parent, enabling correct computation of OPTin and OPTout values.
How do you recover the actual Maximum-Weight Independent Set from the computed values?
Trace back decisions made for each node while solving the subproblems.
What is the time complexity of the dynamic programming algorithm for Maximum-Weight Independent Set on trees?
O(n), where n is the number of nodes in the tree.
Why can’t the greedy algorithm solve Maximum-Weight Independent Set with weights?
Including a leaf or its parent depends on weights, and a greedy choice may not lead to a global optimum.
Can the greedy algorithm partially solve non-tree graphs?
Yes, it can eliminate nodes with degree 1 and their neighbors, simplifying the graph before applying other methods.
How does dynamic programming handle subtrees in the Maximum-Weight Independent Set Problem?
It computes optimal solutions for each subtree and combines them to solve the problem for the whole tree.
What is the relationship between OPTin and OPTout for leaf nodes?
For leaf u: OPTin(u) = wu, OPTout(u) = 0, since there are no children.
How is the Maximum-Weight Independent Set value obtained from the root?
By taking max(OPTin(r), OPTout(r)), where r is the root of the tree.
Why are trees a special case for solving NP-hard problems?
Their acyclic nature allows problems to be broken into independent subproblems on subtrees.
How can the dynamic programming solution for Maximum-Weight Independent Set be adapted for forests?
Solve each tree in the forest independently and combine the results.
Why does the dynamic programming approach require linear time?
Each node and edge is processed exactly once in post-order traversal.
What is the key idea behind dynamic programming for tree problems?
Breaking down problems into independent subproblems on subtrees and combining their solutions.
Why is rooting the tree important for the dynamic programming algorithm?
It orients the tree to allow recursive processing from leaves to the root.
How does the recurrence for OPTin and OPTout ensure independence in the set?
OPTin excludes children of the node, while OPTout allows independent decisions for children.
