Interesting functions on graphs that can be efficiently maximized.

Question

Say that I have a weighted graph $G = (V,E,w)$ such that $w:E\rightarrow [-1,1]$ is the weighting function -- note that negative weights are allowed.

Say that $f:2^V\rightarrow \mathbb{R}$ defines a property of any subset of the vertices $S \subset V$.

Question: What are some interesting examples of $f$s for which the maximization problem: $\arg\max_{S \subseteq V}f(S)$ can be performed in polynomial time?

For example, the graph cut function $$f(S) = \sum_{(u,v) \in E : u \in S, v \not\in S}w((u,v))$$ is an interesting property of subsets of vertices, but cannot be efficiently maximized. The edge density function is another example of an interesting property that alas, cannot be efficiently maximized. I'm looking for functions that are equally interesting, but can be efficiently maximized.

I'll let the definition of "interesting" be somewhat vague, but I want the maximization problem to be non-trivial. For example it should not be that you can determine the answer without examining the edges of the graph (so constant functions, and the cardinality function are not interesting). It should also not be the case that $f$ is really just encoding some other function with a polynomially sized domain by padding it into the domain $2^V$ (i.e. I don't want there to be some small domain $X$, and some function $m:2^S\rightarrow X$ known before looking at the graph, such that the function of interest is really $g:X\rightarrow \mathbb{R}$, and $f(S) = g(m(S))$ If this is the case, then the "maximization" problem is really just a question of evaluating the function on all inputs.)

Edit: Its true that sometimes minimization problems are easy if you ignore the edge weights (although not minimizing the cut function, since I allow negative edge weights). But I'm explicitly interested in maximization problems. It does not become an issue in natural weighted problems in this setting though.

Answer 1

Whenever $f(S)$ counts the number of edges $(u,v)$ satisfying some Boolean predicate defined in terms of $u\in S$ and $v\in S$, then what you wrote is just a Boolean 2-CSP. The objective function asks to maximize the number of satisfied clauses over all assignments to the variables. This is known to be NP-hard and the exact hardness threshold is also known assuming UGC (see Raghavendra'08).

There are many natural positive examples when you want to maximize over subsets of edges, e.g, Maximum matching is one example of a polynomial time problem in this case.

Answer 2

Domatic partition / weak 2-colouring.

(In this case $f(S) = 1$ if each $v \in S$ has a neighbour in $V \setminus S$ and vice versa. Otherwise $f(S) = 0$. A solution with $f(S) = 1$ always exists if there are no isolated nodes, and it can be found easily in polynomial time.)

Answer 3

Minimum cut (specifically, vertex cut).

(In this case $f$ would be something like this: 0 if removing the nodes in the set $S$ does not partition $G$ in at least two components, and $|V| - |S|$ otherwise. Then maximising $f$ is equivalent to finding a minimum cut, which can be done in polynomial time.)

You can also define a similar function that corresponds to minimum edge cuts.

(For example, $f(S)$ is 0 if $S = \emptyset$ or $S = V$; otherwise it is $|E| - |X|$, where $X$ is the set of edges that have one endpoint in $S$ and the other endpoint in $V \setminus S$.)

Answer 4

Maximal independent set.

(Here $f(S)$ = number of nodes in $S$ that are not adjacent to any other node in $S$ + number of nodes in $V \setminus S$ that are adjacent to a node in $S$. Iff $S$ is a maximal independent set we have $f(S) = |V|$.)