5
$\begingroup$

Suppose you have a weighted graph $G = (V, E \subseteq V^2, w \in E \to \mathbb{R}^+)$, where $w$ satisfies the triangle inequality $w(x, y) + w(y, z) \ge w(x, z)$. Suppose $k \in \mathbb{N}$ (in practice, $k \le 6$ is common). I want to find a set $C \subseteq \mathbb{P}(V)$ (a set of subsets of $V$) such that:

  1. $\max_{I \in C} \sum \{w(x, y) \mid x \in I \wedge y \in I\}$ is minimized.
  2. For all $I \in C$, $\mathrm{card}(I) = k$.
  3. No two elements of $C$ have nonempty intersection.
  4. The union of all elements of $C$ is $V$.

Assume that $\mathrm{card}(V) = r \cdot k$ for some $r \in \mathbb{N}$.

Is there a polynomial-time approximation algorithm for this task?

I believe this problem is related to facility location problems, but I am not sure.

Improve this question
$\endgroup$
6
  • $\begingroup$ A small comment on the side, if the graph satisfies the triangle inequality, then it must be a disjoint union of cliques so you do not need to state the part with the cliques (if it is a connected graph it will be a clique anyway). $\endgroup$
    – Narek Bojikian
    Dec 7, 2019 at 20:55
  • $\begingroup$ Also the part with interval graphs is a bit redundant since it is already a clique and hence, the stricture of the graph is well defined. $\endgroup$
    – Narek Bojikian
    Dec 7, 2019 at 20:58
  • $\begingroup$ The problem is very related to the maximum k-cut problem. You might want to give it a shot. $\endgroup$
    – Narek Bojikian
    Dec 7, 2019 at 21:01
  • $\begingroup$ The closest thing I've found in the literature is some stuff on the remote clique problem, but that is trying to maximize the sum of the edge weights in each induced subgraph. I do wonder if the same algorithm would work if we simply change out all of the maximization for minimization -- it is a pretty straightforward greedy algorithm. I'm just a bit skeptical because applying an antitone function to weights of a triangle inequality graph does not give a triangle inequality graph. $\endgroup$
    – taktoa
    Dec 7, 2019 at 23:12
  • 1
    $\begingroup$ @narekBojikian Can you elaborate or provide references on the relationship between this problem and max k-cut? I'm afraid I don't see it. $\endgroup$
    – taktoa
    Dec 7, 2019 at 23:15

1 Answer 1

Reset to default
3
$\begingroup$

Let $n := |V| = rk$ be the total number of vertices in the graph. Basically, we are looking for a partition of $V$ into $r$ sets each of size $k$. The total cost will be then the sum of the weights of all edges present in the graph induced by each of these sets. Note that the edges having one end in one of these sets and the other endpoint in another set form together an $r$-cut and are exactly the edges we do not count in our sum. Hence, instead of minimizing the sum of edges in the subgraphs induced by the sets of the partition, we can maximize the weights of edges having one end in a set of the partition and the other end in a different set.

Note that we are looking here at a special variation of maximum $k$-cut, where we require that all the subsets of the partition have equal sizes and hence the problems are not completely equivalent. However, it is not hard to reduce the maximum $k$-cut problem (let us call it for now maximum $s$-cut to avoid confusion) to your problem, where given an instance of the $s$-cut problem (with $N$ vertices), you can add $(s-1)N$ additional vertices to the graph and connect each of them with all vertices in the graph with edges of weight 0. Set $k = N$ (note that $n = sN$) and hence, we will have $r = s$. Each solution to your problem corresponds to a solution to the maximum cut problem with dummy vertices assigned arbitrarily to make the count consistent.

The maximum cut problem is APX-hard and hence does not admit PTAS (polynomial time approximation scheme) unless P=NP. Using the previous reduction, and since the maximum cut problem is a special case of the maximum $k$-cut problem, your problem is at least as hard as the maximum cut problem.

Improve this answer
$\endgroup$
11
  • 1
    $\begingroup$ I don't yet see how the reduction works. First, you mean "a special variation of maximum $r$-cut", right? Assuming you do mean that: I can see how the extra vertices allow parts of size $<k$, but not parts of size $>k$. Suppose all optimal solutions to the max $r$-cut problem include some part with size $>k$. How does that part map to a part in the constructed instance of the OP's problem, which disallows such large subsets? $\endgroup$
    – j_random_hacker
    Dec 8, 2019 at 2:12
  • $\begingroup$ I used k since that is the common name of the problem. But let us stick to your notation for now to avoid confusion. Can you give a concrete example I dont quite get your point $\endgroup$
    – Narek Bojikian
    Dec 8, 2019 at 2:26
  • $\begingroup$ Regarding $k$ vs. $r$: I appreciate that $k$ is usually used for the number of parts in the partition for Max $k$-partition, but the OP used $k$ for the fixed size of each part, and you seemingly accepted this by defining $r$ to be the number of parts and using in that way in paragraph 1 -- but in later paragraphs you swap to writing $k$ for the number of parts instead of $r$. The difficulty with reusing $k$ like this is that it leaves no way to refer to the OP's original $k$. $\endgroup$
    – j_random_hacker
    Dec 8, 2019 at 10:14
  • $\begingroup$ Suppose $n=4$, $r=2$ in the input max $r$-cut instance, with edge costs from $v_1$ to the 3 other vertices being 10 and the edge costs between other pairs of vertices being 1. (Clearly the opt solution is $\{v_1 | v_2, v_3, v_4\}$.) IIUC, you will create an instance of the OP's problem that adds $(r-1)n = 4$ extra vertices $x_1, \dots, x_4$ that are connected by 0-cost edges to all other vertices. What is $k$ is set to for this constructed instance? $\endgroup$
    – j_random_hacker
    Dec 8, 2019 at 10:56
  • 1
    $\begingroup$ Ah, k=N. That makes sense now, thanks. I'll +1 when you update the answer. $\endgroup$
    – j_random_hacker
    Dec 8, 2019 at 11:20

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.