I have been looking at two problem that I have narrowed down to being graph DP problems, but for the love of me I can’t figure out how to write the dp!
Of course, we all know that the maximum disjoint set problem is NP-hard. But what if graph is 2 x n “grid graph” (only perpendicular edges). And we are given n subgraphs on this graph. What is the maximum number of these subgraphs we can select so that no two of those we pick share a vertex? My intuition say to use DP on the vertices, but I simply don’t know how, because the subgraphs can be irregularly shaped (like “L”, etc).
We have a map with some cities and highways between the cities that take positive time t_i to travel on. At each city we want to taste the local cuisines, but the restaurants are only open between start time s_i and finish time f_i. We start at our home city at time t=0. What is the maximum number of cuisines we can try (we don’t have to try the cuisine of a city if we visit it). Thinking of doing a DP on the vertices that keep track of the max current cuisines tasted on a path to that vertex. But I don’t know if this works?