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.

  • $\begingroup$ Do you have an example of such function? $\endgroup$ – Yaroslav Bulatov Oct 8 '10 at 18:32
  • $\begingroup$ No, hence the question. :-) $\endgroup$ – Aaron Roth Oct 8 '10 at 18:35
  • $\begingroup$ Ah ok. My impression that a function that can be efficiently maximized for all graphs must be uninteresting. But there may be interesting functions that can be efficiently maximized for restricted sets of graphs. For instance, for planar graphs, some interesting functions can be efficiently maximized, while other interesting functions don't yet have an efficient algorithm $\endgroup$ – Yaroslav Bulatov Oct 8 '10 at 18:41
  • $\begingroup$ I'd be happy to see answers about results for restricted classes of graphs if we can't think of any interesting functions that can be maximized over all graphs. $\endgroup$ – Aaron Roth Oct 8 '10 at 18:49
  • $\begingroup$ Shouldn't this be CW? We can generate arbitrarily many examples, and whether those are "interesting" is subjective. $\endgroup$ – Jukka Suomela Oct 8 '10 at 20:38

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.

  • $\begingroup$ This is a nice observation that rules out many natural problems of this type. $\endgroup$ – Aaron Roth Oct 8 '10 at 23:38

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.)


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$.)

  • $\begingroup$ Ok, but this is a minimization problem in disguise, which tends to be easier when you ignore the edge weights. (Note that if you take into account edge weights, since I specify we have may have negative weights, then min-cut is also a hard problem). I will try to edit the question to emphasize this point. $\endgroup$ – Aaron Roth Oct 8 '10 at 21:30

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|$.)

  • $\begingroup$ How do you find maximal independent set in polynomial time? $\endgroup$ – Yaroslav Bulatov Oct 9 '10 at 0:18
  • 1
    $\begingroup$ @Yaroslav: greedily. $\endgroup$ – Jukka Suomela Oct 9 '10 at 7:48
  • $\begingroup$ @Yaroslav: Hint - the difference between maximum and maximal is massive. ;-) $\endgroup$ – Ross Snider Oct 9 '10 at 8:08

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.