FPT Dynamic programming

Question 1

What is the Independent Set Problem?

Answer 1

Finding a subset of nodes in a graph such that no two nodes in the subset are adjacent.

Question 2

What makes solving problems on trees different from general graphs?

Answer 2

Trees have no cycles and are structurally simpler, allowing problems to be solved efficiently with dynamic programming or greedy methods.

Question 3

What is the key advantage of working on trees for NP-hard problems?

Answer 3

Subproblems on subtrees only interact through their roots, enabling a divide-and-conquer approach.

Question 4

What is the greedy algorithm for finding an independent set on trees?

Answer 4

Start with a leaf node, include it in the independent set, remove it and its neighbor, and repeat until the tree is empty.

Question 5

Why does the greedy algorithm work for independent sets on trees?

Answer 5

Every tree has at least one leaf, and including a leaf is always part of some maximum independent set.

Question 6

What is a forest in graph theory?

Answer 6

A graph consisting of multiple disconnected trees.

Question 7

How does the greedy algorithm handle forests?

Answer 7

It applies the same logic to each tree in the forest independently.

Question 8

What is the time complexity of the greedy independent set algorithm on trees?

Answer 8

O(n), where n is the number of nodes in the tree.

Question 9

What is the Maximum-Weight Independent Set Problem?

Answer 9

Finding an independent set in a graph where the total weight of the nodes in the set is maximized.

Question 10

How does Maximum-Weight Independent Set differ from the unweighted version?

Answer 10

Each node has a weight, so choosing nodes must consider both independence and weight optimization.

Question 11

What is the difficulty in solving Maximum-Weight Independent Set on trees?

Answer 11

Deciding locally whether to include a node or its neighbor requires considering global effects on the tree’s structure and weights.

Question 12

What are the two subproblems for Maximum-Weight Independent Set on trees?

Answer 12

OPTin(u): Maximum weight including node u. OPTout(u): Maximum weight excluding node u.

Question 13

What is the recurrence relation for OPTin(u) in Maximum-Weight Independent Set?

Answer 13

OPTin(u) = wu + sum(OPTout(v) for v in children(u)), where wu is the weight of u.

Question 14

What is the recurrence relation for OPTout(u) in Maximum-Weight Independent Set?

Answer 14

OPTout(u) = sum(max(OPTin(v), OPTout(v)) for v in children(u)).

Question 15

How does dynamic programming solve the Maximum-Weight Independent Set Problem?

Answer 15

By building solutions for subtrees recursively from leaves to the root using the OPTin and OPTout recurrences.

Question 16

What is the significance of post-order traversal in the dynamic programming solution?

Answer 16

It ensures children are processed before their parent, enabling correct computation of OPTin and OPTout values.

Question 17

How do you recover the actual Maximum-Weight Independent Set from the computed values?

Answer 17

Trace back decisions made for each node while solving the subproblems.

Question 18

What is the time complexity of the dynamic programming algorithm for Maximum-Weight Independent Set on trees?

Answer 18

O(n), where n is the number of nodes in the tree.

Question 19

Why can’t the greedy algorithm solve Maximum-Weight Independent Set with weights?

Answer 19

Including a leaf or its parent depends on weights, and a greedy choice may not lead to a global optimum.

Question 20

Can the greedy algorithm partially solve non-tree graphs?

Answer 20

Yes, it can eliminate nodes with degree 1 and their neighbors, simplifying the graph before applying other methods.

Question 21

How does dynamic programming handle subtrees in the Maximum-Weight Independent Set Problem?

Answer 21

It computes optimal solutions for each subtree and combines them to solve the problem for the whole tree.

Question 22

What is the relationship between OPTin and OPTout for leaf nodes?

Answer 22

For leaf u: OPTin(u) = wu, OPTout(u) = 0, since there are no children.

Question 23

How is the Maximum-Weight Independent Set value obtained from the root?

Answer 23

By taking max(OPTin(r), OPTout(r)), where r is the root of the tree.

Question 24

Why are trees a special case for solving NP-hard problems?

Answer 24

Their acyclic nature allows problems to be broken into independent subproblems on subtrees.

Question 25

How can the dynamic programming solution for Maximum-Weight Independent Set be adapted for forests?

Answer 25

Solve each tree in the forest independently and combine the results.

Question 26

Why does the dynamic programming approach require linear time?

Answer 26

Each node and edge is processed exactly once in post-order traversal.

Question 27

What is the key idea behind dynamic programming for tree problems?

Answer 27

Breaking down problems into independent subproblems on subtrees and combining their solutions.

Question 28

Why is rooting the tree important for the dynamic programming algorithm?

Answer 28

It orients the tree to allow recursive processing from leaves to the root.

Question 29

How does the recurrence for OPTin and OPTout ensure independence in the set?

Answer 29

OPTin excludes children of the node, while OPTout allows independent decisions for children.