0
$\begingroup$

My graph is as follows: enter image description here

I need to find a maximum weight subgraph.

The problem is as follows:

There are n Vectex clusters, and in every Vextex cluster, there are some vertexes. For two vertexes in different Vertex cluster, there is a weighted edge, and in the same Vextex cluster, there is no edge among vertexes. Now I want to find a maximum weight subgraph by finding only one vertex in each Vertex cluster. And the total weight is computed by adding all weights of the edges between the selected vertex. I add a picture to explain the problem. Now I know how to model this problem by ILP method. However, I do not know how to solve it by an approximation algorithm and how to get its approximation ratio.

Could you give some solutions and suggestions?

Thank you very much. If any unclear points in this description, please feel free to ask.

Improve this question
$\endgroup$
1
  • $\begingroup$ Probably a local search may be a good heuristic to try here: given a current solution $S$, you find a cluster $C$ and a vertex $c'$ in this cluster such that weight$(S\setminus c \cup c')>$ weight$(S)$ where $c$ was the vertex in $C\cap S$ $\endgroup$
    – Mathieu Mari
    Jun 25, 2019 at 20:37

1 Answer 1

Reset to default
2
$\begingroup$

This is the weighted, non-bipartite generalization of the Max-Rep problem, which is equivalent to LabelCover-Max. See Page 20 of Kortsarz. As far as I know, the best approximation algorithm to that problem is $O(n^{1/3})$, due to Charikar, Hajiaghayi, and Karloff

In terms of approximation, the original Max-Rep problem and your generalization are similar. Up to a factor of $O(\log n)$, the weights can be taken care of by a standard bucketing argument. Up to a factor of $2$, the graph can be made bipartite by randomly assigning each cluster one of two sets (say $A$ or $B$) according to a fair coin toss, and removing any edges that go from $A$ to $B$. So this gives an immediate $O(n^{1/3} \log n)$ approximation algorithm, using the algorithm of CHK as a subroutine.

The previous hardness of $O(2^{\log^{1-\epsilon} n})$ carries through (again, see the Kortsarz paper for more details), and there are some conjectures out there that for some $\epsilon>0$, the problem is hard to approximate to within $O(n^{\epsilon})$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for your nice answer and sorry for that I have some problems. I am confused about the process of transforming this question into the Max-Rep problem. I do not understand how we could transform the weight by a factor O(logn). After we assign cluster to A or B, A and B may consist of n/2 clusters (may be bigger than 2) and the clusters in the same set are connected by many edges, so I also confused why we could apply the CHK as the subroutine? Sorry for these stupid questions. Thanks! $\endgroup$
    – Refrain
    Jun 26, 2019 at 14:36
  • $\begingroup$ The bucketing argument works as follows. With only a constant-factor loss, we throw out all edges with weight less than $w_{\max} / n^2$. For each $r \in \{0, 1, 2, \cdots, \lceil 2 \log_2\ n \} \rceil$, let $E_r$ be the set of edges with weight between $2^r w_\min$ and $2^{r+1} w_\min$. This forms a partition of all edges, putting each into one of $O(\log n)$ buckets. The problem restricted to $G=(V,E_r)$ has all weights that are within a factor of $2$ of each other, so treating this as an unweighted problem gives a $\tfrac{1}{2}$-approximation to the optimal solution (for that problem). ... $\endgroup$
    – Yonatan N
    Jun 26, 2019 at 21:28
  • $\begingroup$ ... Since there are only $O(\log n)$ buckets, at least one of these buckets has a solution with objective value $\Omega(\textrm{OPT}/\log n)$. So the algorithm here is to use CHK as a subroutine on each of the $O(\log n)$ buckets and return the one with the largest objective score, which has a lower bound of $\tfrac{1}{2} \Omega(\textrm{OPT}/\log n) = \Omega(\textrm{OPT}/\log n)$ on its performance. $\endgroup$
    – Yonatan N
    Jun 26, 2019 at 21:28
  • $\begingroup$ The factor-2 reduction to the bipartite case randomly assigns each vertex cluster to one of two sides of a bipartition $(A,B)$. Let's consider the approach that works by randomly choosing $n/2$ vertex clusters for $A$, and the other $n/2$ go to $B$. We then just discard all edges between two clusters in $A$ and between any two clusters in $B$, leaving only edges that go between clusters in A and those in B. Let $\textrm{OPT}_1$ be the set of edges in the original optimal solution, and $\textrm{OPT}_2 \subseteq \textrm{OPT}_1$ be the edges that survived our discarding procedure. ... $\endgroup$
    – Yonatan N
    Jun 26, 2019 at 21:42
  • $\begingroup$ ... For an edge in $\textrm{OPT}_1$, what is its contribution to $\textrm{OPT}_2$? Well, for any such edge $e$, it survives the discarding procedure with probability at least $1/2$, so in expectation it contributes at least $w_e / 2$ to the total weight of $\textrm{OPT}_2$. Summing over all edges in $\textrm{OPT}_1$, one can use linearity of expectations to conclude that $E[w(\textrm{OPT}_2)] \geq w(\textrm{OPT}_1) / 2$, so the loss incurred by such a procedure is at most some multiplicative constant. $\endgroup$
    – Yonatan N
    Jun 26, 2019 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.