In algorithm analysis what exactly defines a subproblem?
I know that one of the optimality conditions for greedy algorithms is that all subproblems of the solution are also optimal, but to me this begs the question. Are subproblems defined relative to a data set, a problem on that data set, or a solution to that problem?
As an example, a shortest path algorithm on a connected graph with vertices {a,b,c,d,e} for a path from a to e may return {(a,b),(b,c),(c,d),(d,e)}, and the subproblems here to me are every path from an earlier vertex in the list to a later vertex in the list, implying that you have subproblems relative to a solution.
An example that confuses me, however, is dealing with sequence alignment on strings. Given an optimal alignment for two sequences, what are the subproblems? Is it the alignment of any partition of the two strings? Because the answer to an alignment problem can actually return different strings.
For example, if we're aligning ["AT","CAT"] we should get ["_AT","CAT"]
But for the 0th index here it doesn't make sense to say that ["_","C"] is a subproblem, or that ["A","C"] is a subproblem, because they're both trivial (alignment of two singletons can never be suboptimal), and ["A","C"] is never actually aligned/compared in the result.
