# How do I describe this (graph-)problem for a research paper?

I have a function f(x, y) which takes two integers and returns a scalar.

My task is to find the set of (x, y) pairs, 0<x<W, 0<y<H where f(x, y)>0, which maximize the sum f(x_i, y_i) with the constraint that no two pairs shall overlap. Two pairs (x1, y1) and (x2, y2) overlap if (x2 >= x1 and x2 < x1+y1).

I have implemented a practical solution which processes in O(WxH) time with O(W) memory. I'm pretty sure this is optimal. It seems to me that it is a kind of a graph flow algorithm, but I don't know how to formally describe it without pseudo code.

Can anybody tell me what class of problems this problem belongs to?

I attach a screenshot of a solution to one configuration (darker means higher f(x, y)).

• Your problem belongs to the class P, the class of problems that are solvable in polynomial time. – Gamow Mar 23 '16 at 16:34

Replace any negative value with zero. Then, think of the numbers in the range $1\dots W$ as vertices in a graph, and think of a pair $(x,y)$ as corresponding to an edge from vertex $x$ to vertex $x+y$ (or to $W$ if $x+y>W$), with weight $f(x,y)$. This graph is a DAG, and what you are looking for are the nonzero edges on a longest path from $1$ to $W$ in this DAG. DAG longest path problems can be solved in time linear in the size of the DAG (here, $O(WH)$); see https://en.wikipedia.org/wiki/Longest_path_problem.