5
$\begingroup$

Consider an arbitrary undirected graph $G = (V,E)$. Suppose you have a collection of $|E|$ positive integers and each integer must be assigned to one edge. Let us denote the collection of integers assigned to vertex $v$'s edges as $w(v)$. How would one assign the $|E|$ integers to the $|E|$ edges so as to maximize:

\begin{equation} \sum_{v \in V}{max(w(v)) - min(w(v))} \end{equation}

In other words, how would one maximize the sum of the range of each vertice's edge assignments?

As an example, consider the graph pictured below. Same graph, same set of $|E|$ integers, but different assignments of integers to edges leads to the above equation evaluating to either 16 or 18.

two graphs, different equation weights per above equation

$\endgroup$
4
  • $\begingroup$ From trail and error I got this: Let MIN and MAX be the current minimum(maximum) weights available. Pick a vertex with highest degree assign one MIN and one MAX for two edges and choose median values for the rest. Go to the edge of the MIN and choose MAX then choose MIN then MAX..etc till you cover all edges $\endgroup$
    – seteropere
    Oct 11 '14 at 23:42
  • $\begingroup$ @D.W. I've thought about whether it can be expressed as a series of linear constraints and solved using linear programming, though linear programming is an area I'm new to. I guess I'm stuck in that if you use a greedy strategy like say that suggested by seteropere, I don't know whether it is optimal or not. This is not a copy-paste exercise problem. This is based on an original problem I am working on. What I ultimately want to know is whether one can systematically tweak the summation value up or down. Finding the maximum seems like a nice first step. $\endgroup$ Oct 12 '14 at 2:19
  • $\begingroup$ 1. It should be easy to test @seteropere's greedy strategy on a bunch of test cases. Usually, if you want to know if a greedy strategy works, a simple way is to implement it, construct lots of test cases, and see if it always works on all of them. Most greedy strategies that don't work can be immediately disqualified in this way. 2. My first thought on seeing this problem is to suspect that it might possibly be NP-complete, if there doesn't happen to be some simple greedy strategy that miraculously works. $\endgroup$
    – D.W.
    Oct 12 '14 at 23:56
  • $\begingroup$ @D.W. I might do that - implement the greedy strategy and see if it can be disqualified under any test cases. Of course I'd still be interested to see a more formal proof of NP-completeness or that the greedy strategy works, in order to move from conjecture to proof. Not only for the sake of the specific problem at hand, but to see an example/get a feel for how one might formally reason about such a problem. $\endgroup$ Oct 13 '14 at 2:54
3
$\begingroup$

I'll start by giving a negative example to @seteropere algorithm:

Let $G=(V,E)$, where $$V=\{x_1,x_2,x_3,y_1,y_2,y_3\}\ \ \ ,\ \ \ E=\{(x_i,y_i)\mid i\in [3]\}\cup\{(x_1,x_2),(x_1,x_3)\}$$ Let the weight collection be $\{3,3,2,1,1\}$.

The proposed algorithm starts by assigning weights $1,2$ and $3$ for $x_1$, and assume that $(x_1,y_1)$ was assigned 1.

This already means that the optimal solution profit (5, see figure) is not obtainable.

enter image description here enter image description here


That said, this problem is poly time solvable after all , greedily, but differently.

Hint: given a graph $G$ such that $\Delta(G)\geq 2$, prove that in the optimal solution there exists a vertex $v$ such that the maximal number and the minimal number are both in $w(v)$.


P.S.

The opposite problem, in which we aim to minimize $$\sum_{v \in V}{max(w(v)) - min(w(v))}$$

Is quite interesting by itself.

$\endgroup$
1
  • 1
    $\begingroup$ Nice analysis, however, one may start with $(x_1,x_2)=1$ and $(x_1,x_3)=3$ then the proposed strategy will get the optimal. This may help the OP in coming up with optimal alg for the problem. I am not sure if there is a single alg for all kind of graphs though. $\endgroup$
    – seteropere
    Oct 13 '14 at 21:44

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.