5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

There is no formal definition. A subproblem is just a (usually smaller!) problem that you solve on the way to solving the problem you're really interested in.

$\endgroup$
  • $\begingroup$ I guess if it's not in some way a "part" of the original problem, we'd not say "subproblem". $\endgroup$ – Raphael Sep 2 '16 at 14:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.