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

<p>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.</p>

CC BY-SA 2.5
2010-10-08T23:38:25.147Z
This is a nice observation that rules out many natural problems of this type.
Aaron Roth
CC BY-SA 2.5
2010-10-08T19:16:54.637Z
2010-10-08T20:49:32.760Z
2010-10-08T20:49:32.760Z
Moritz
<p>Domatic partition / weak 2-colouring.</p>

<p>(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.)</p>

CC BY-SA 2.5
2010-10-08T20:37:33.487Z
2010-10-08T20:37:33.487Z
Jukka Suomela
<p>Maximal independent set.</p>

<p>(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|$.)</p>

CC BY-SA 2.5
2010-10-09T00:18:42.530Z
How do you find maximal independent set in polynomial time?
Yaroslav Bulatov
CC BY-SA 2.5
2010-10-09T07:48:22.210Z
@Yaroslav: greedily.
Jukka Suomela
CC BY-SA 2.5
2010-10-09T08:08:37.497Z
@Yaroslav: Hint - the difference between maximum and maximal is massive. ;-)
Ross Snider
CC BY-SA 2.5
2010-10-08T21:32:32.660Z
2010-10-08T21:32:32.660Z
Jukka Suomela
<p>Minimum cut (specifically, vertex cut).</p>

<p>(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.)</p>

<p>You can also define a similar function that corresponds to minimum edge cuts.</p>

<p>(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$.)</p>

CC BY-SA 2.5
2010-10-08T21:30:48.690Z
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.
Aaron Roth
CC BY-SA 2.5
2010-10-08T20:25:45.760Z
2010-10-08T21:11:45.220Z
2010-10-08T21:11:45.220Z
Jukka Suomela
<p>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.</p>

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

<blockquote>
  <p>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?</p>
</blockquote>

<p>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 <em>can</em> be efficiently maximized.</p>

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

<p>Edit: Its true that sometimes <em>minimization</em> 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. </p>

CC BY-SA 2.5
2010-10-08T18:32:28.020Z
Do you have an example of such function?
Yaroslav Bulatov
CC BY-SA 2.5
2010-10-08T18:35:18.020Z
No, hence the question. :-)
Aaron Roth
CC BY-SA 2.5
2010-10-08T18:41:40.303Z
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
Yaroslav Bulatov
CC BY-SA 2.5
2010-10-08T18:49:16.927Z
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.
Aaron Roth
CC BY-SA 2.5
2010-10-08T20:38:20.410Z
Shouldn't this be CW? We can generate arbitrarily many examples, and whether those are "interesting" is subjective.
Jukka Suomela
CC BY-SA 2.5
2010-10-08T21:09:00.183Z
I disagree about CW. I think the question of even one natural example is legitimate. The question should perhaps specify further what counts as cheating, e.g., turning minimization problems into maximization problems by flipping signs, turning decision problems into maximization problems etc.
Moritz
CC BY-SA 2.5
2010-10-08T21:39:47.707Z
@Moritz: I am not sure if it is possible to plug all loopholes. I gave yet another example that demonstrates how you can cheat (without making it too explicit).
Jukka Suomela
CC BY-SA 2.5
2010-10-08T21:52:10.767Z
@Aaron: It might help if you told why you are asking the question – what is your motivation or application. Perhaps then it would be easier to guess what kind of answers you'd expect to get.
Jukka Suomela
CC BY-SA 2.5
2010-10-08T23:28:35.803Z
Here's a natural possibility that doesn't work out: maximize the weight of the maximum spanning tree of S. Unfortunately this is equivalent to the prize collecting steiner tree problem.
Warren Schudy
<ds.algorithms><graph-theory><co.combinatorics>
Interesting functions on graphs that can be efficiently maximized.
Aaron Roth
# Interesting functions on graphs that can be efficiently maximized.

(Asked by: username_0 on 2010-10-08)

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.

**Tags:** ds.algorithms, graph-theory, co.combinatorics

> **Comments:**
> **username_1**: Do you have an example of such function?  
> **username_0**: No, hence the question. :-)  
> **username_1**: 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  
> **username_0**: 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.  
> **username_2**: Shouldn't this be CW? We can generate arbitrarily many examples, and whether those are "interesting" is subjective.  
> **username_3**: I disagree about CW. I think the question of even one natural example is legitimate. The question should perhaps specify further what counts as cheating, e.g., turning minimization problems into maximization problems by flipping signs, turning decision problems into maximization problems etc.  
> **username_2**: @username_3: I am not sure if it is possible to plug all loopholes. I gave yet another example that demonstrates how you can cheat (without making it too explicit).  
> **username_2**: @Aaron: It might help if you told why you are asking the question – what is your motivation or application. Perhaps then it would be easier to guess what kind of answers you'd expect to get.  
> **username_4**: Here's a natural possibility that doesn't work out: maximize the weight of the maximum spanning tree of S. Unfortunately this is equivalent to the prize collecting steiner tree problem.  

---

## 4 answers

### Answer by username_3 on 2010-10-08. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_0**: This is a nice observation that rules out many natural problems of this type.  

---

### Answer by username_2 on 2010-10-08. Score: 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 by username_2 on 2010-10-08. Score: 1

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

> **Comments:**
> **username_1**: How do you find maximal independent set in polynomial time?  
> **username_2**: @Yaroslav: greedily.  
> **username_5**: @Yaroslav: Hint - the difference between maximum and maximal is massive. ;-)  

---

### Answer by username_2 on 2010-10-08. Score: 1

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

> **Comments:**
> **username_0**: 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.  

---

