# Tag Info

21

I think, your problem is NP-complete. It is a special case of a theorem by Farrugia, stating that it is NP-hard to test if the vertex set a graph can be partitioned into two subsets $V_1,$ and $V_2$ such that $G(V_1)$ belongs to the graph class $\mathcal{P}$ and $G(V_2)$ belongs to the graph class $\mathcal{Q}$, provided $\mathcal{P}$ and $\mathcal{Q}$ ...

15

Here is a reduction from PARTITION to this problem. Let $(a_1,\dots, a_n)$ be an instance of PARTITION. Assume that $a_1\leq a_2\leq \dots \leq a_n$. Let $N$ be a “very large number”, e.g. $N = (\sum_{i=1}^n |a_i|) + 1$. Consider the instance $$\underbrace{N, \dots, N}_{5n \text{ times}}, N + a_1, \dots, N+a_n,\underbrace{4N, \dots, 4N}_{n \text{ times}}$$ ...

11

Rao has two papers on sparsest cut in planar graphs, a constant-factor approximation in quasi-linear time seems possible. Recursive bisection, while not ideal, might be a feasible approach for your problem. Satish Rao. Finding near optimal separators in planar graphs. In 28th Symposium on Foundations of Computer Science (FOCS), pages 225-237, 1987. Satish ...

9

For a graph $G=(V,E)$, deciding if $V$ can be partitioned into equal sized subsets (say, for a fixed size $r$) where each subset induces a connected subgraph is $\mathsf{NP}$-hard. It remains $\mathsf{NP}$-hard for planar graphs, and also if the number of subsets is fixed instead of the subset size ($|V|/r$ fixed). However, the problem is polynomial for ...

9

This problem is in P, it can be reduced to the Minimum cut problem. The graph construction is as follows - Add a source and a sink vertex. For each vertex $i$, add an edge with cost $w(i)$ from source to $i$ and another edge of cost $s(i)$ from $i$ to sink. Also add edges from $i$ to $j$ of cost $t(i,j)$ for every pair of vertices $i$ and $j$. The cost of ...

8

http://cse.iitkgp.ac.in/~pabitra/paper/barna-sdm07.pdf BAM, here's the answer. Incremental min cut graph partitions in $O(k^3)$ time for insertions and deletions. If you make $k = O(\log n)$ then it's poly logarithmic for insertions and deletions, which is damn good.

7

The problem you asked is the unweighted version of the Balance Connected 2-Partition ($BCP_2$). For unweighted case, any 2-connected graph can be partitioned into two connected subgraphs whose numbers of vertices differ by at most one. A simple algorithm uses st-numbering. For any 2-connected graph, we can label the vertices by $[1...n]$ such that any ...

7

One can solve the decision problem in $\tilde{O}(nA)$ time. Let the sequence of numbers be $S$. Define $F_S$ to be a set such that $(i,j)\in F_S$ iff there exist a subsequence of $S$ of length $j$ that sums to $i$. If we have computed $F_S$, then we just need $O(nA)$ additional time to go thorough $F_S$ to solve your problem. If $S_1$ and $S_2$ are two ...

5

From both states in $\{n_1,n_2\}$, action $\pi_1$ takes you to $n_2$, while action $\pi_2$ takes you to states in $\{n_3,n_4\}$. Hence no refinement of that block takes place. The second block doesn't refine either; therefore the partition refinement terminates. At this point you have proved that $n_1$ and $n_2$ are bisimilar and $n_3$ and $n_4$ are ...

5

It's still NP-complete, via a reduction from the partition problem (in the form of: given a collection of $n$ positive numbers $x_i$, where $n$ is even, partition the numbers into two subsets with equal sums). This exact form of the partition problem is not one of the ones mentioned by Garey and Johnson (SP12); in particular they don't mention the constraint ...

5

The largest number is the soft number I claim that for any instance of your problem, if the instance is solvable (it is possible to partition the numbers using one soft number) then it is possible to solve the instance using the largest number as the sole soft number. This is easy to prove: any solution can be modified into a solution with the largest ...

5

Intuitively, the intermediate cases should be neither in P, nor NP-hard. Perhaps it depends exactly on what we mean by "intermediate case". Here is one interpretation for which we can prove something. Note: The Exponential-Time Hypothesis, or ETH, is that it is not the case that, for every constant $\epsilon>0$, SAT has an algorithm running in time $2^{... 4 This problem is called MIN-SUM clustering and is NP-hard. There's a paper by Bartal, Charikar and Raz from 2001 that has an approximation scheme for it: the paper also includes references to the NP-hardness result and other related results. 4 Compute a constant degree spanning tree$T$of your graph, root it, and now greedily find subtrees of roughly size$r$, extract them, and repeat. Naturally, if there is no constant degree spanning tree, then the star example shown above demonstrates that this algorithm can fail. 3 It's like cheating, but if you change the representation of the numbers in the input then the problem becomes strongly NPC: SUBSET SUM OF FACTORIZED SEMIPRIMES "SUBSUMS" Input: A list of$N+1$integers:$q_0$and$A = \{q_1, ..., q_N\}$each one represented as a (sub)sum of factorized (semiprime) integers; i.e.$q_i$is given as$p_{i,1} 2^{a_{i,1}} + ... +...

3

I will consider the case of non-negative weights only. As I mentioned in the comment the problem is related to the minimum k-way cut problem where the goal is to partition a given graph G into k non-trivial components to minimize the number (or weight in the weighted case) of edges crossing the partition. This is the same as maximizing the number of edges in ...

3

The problem is indeed NP-complete - reduce from the 3-partition problem where you are given $3n$ positive integers and asked to group them into $n$ groups such that for all the groups the sum of the elements is the same. Note (1) that partition is strongly NP-complete - i.e remains NP-complete when the input numbers are polynomial in $n$. Note (2) that if ...

3

It seems that $Sep(u, v)$ is a vertex separator extended to graphs where $u$ and $v$ are adjacent, by ignoring their common edge. I assume the correct definition is ... vertex separator in $G$ if $\{u,v\} \notin E$ or in $G′=(V,E \setminus \{\{u,v\}\})$ otherwise. As given, the definition makes no sense. There is no point in removing $\{u, v\}$ from $... 3 The problem can be solved via the assignment problem/network flow. Create a bipartite graph with the left side consisting of$N$vertices$a_1,\ldots,a_N$corresponding to the sets$A_1,\ldots,A_n$. The right side has$m$vertices$u_1,\ldots,u_m$one for each element in$U$. Connect$a_i$via directed arcs of capacity$1$to each element vertex that$A_i$... 3 If anybody care about the$\log$factors, with careful analysis we can prove the time complexity for Chao's algorithm is$O(nA\log(nA))$. Proof. At the even-th layer of the recursion tree, we partition the set$S$into two equally sized set$S_1$and$S_2, which gives $$T_e(n,A)=T_o(n/2,A')+T_o(n/2,A-A')+O(nA\log(nA)),$$ and at the odd-th layer of the ... 3 Your problem is an instance of an integer programming problem and more specifically an integer linear programming problem since your constraints are linear. For instance the second version of your problem can be written as finding integer solutions of the system \begin{align} x + y &= 30 \\ x + 5 &= 2(3 + y) \end{align} There is a huge literature ... 3 This answer does not solve the question. It only settles the following auxiliary problem formulated by @JohnDvorak in the comments (partitioning a set in 1:2 ratio): Auxiliary problem: Instance: Positive rationalsa_1,\ldots,a_m$with$\sum_{i=1}^m a_i = 3A$. Question: Does there exist an index set$I\subseteq\{1,\ldots,n\}$with$\sum_{i\in I}a_i=A$?... 3 Edit: The result is incorrect, see the discussion at the end. Inspired by Mikhail Rudoy's answer, we can generalize to partitioning into$k$parts with equal sum. The problem is polynomial time solvable for each constant$k$. The input is$a_1,\ldots,a_n$such that$a_n$is the largest number. Mikhail's observations are, wlog, the soft number is$a_n...

2

This is a partial answer that only gives a candidate intermediate $NP$-complete problem. $k$-Equal Sum Subsets problem: Given a multiset of $n$ positive integers $A = \{a_1,...,a_n\}$, are there $k$ nonempty disjoint subsets $S_1,...,S_k ⊆ \{a_1,...,a_n\}$ such that $sum(S_1) = ... = sum(S_k)$? The problem is weakly $NP$-complete when $k= O(1)$ and ...

2

It is $NP$-complete to determine the existence of a partition of the vertex set $V$ of cubic graph into two vertex-induced trees of equal size. This follows immediately from the the NP-completeness of deciding whether a cubic graph is Yutsis graph ( Yutsis graphs are also known as dual Hamiltonian cubic graphs). Jaeger proved that a graph $G(V, E)$ is dual ...

2

In the proof of theorem 2 in Improved Approximation Algorithms for Rectangle Tiling and Packing by Berman et al, they proved an upper bound of $\frac{11}{5} \max\{W/p,y\}$, where $W$ is the sum of the weight of all elements, $p$ is the number of rectangles and $y$ is the weight of the largest element. This implies a upper bound of $\frac{11}{5j}$ for your ...

2

Even in the current updated version of the question, it still remains ill defined. There many different ways by which you can partition a graph into symmetric (or balanced if you like) clusters. One question that you might have in mind but have problem expressing is the minimum multisection (or partition): Given a graph $G$ find a symmetric partition $P$ of ...

2

Your problem can be reduced to the Partition problem (which is weakly NP-complete) without an exponential blowup of the numeric values; so your problem is weakly NP-complete, too. This is the idea: you can view the $2N$ integers as nodes of a graph $G$, the pairs in $P$ indentify the edges between the nodes. Clearly $G$ cannot contain cycles of odd length (...

1

This problem is NPC; we can use it to decide whether there exist a $k$-clique. Each edge $(u,v)$ is transformed into a set $S_{u,v}$, we put $u$ and $v$ into $S_{u,v}$, as well as $U$ globally unique elements. Set $K=\frac{k(k-1)}{2}U+k$ and $U=n^3$. Each share of the partition can contain $\frac{k(k-1)}{2}$ edges, if they form a $k$-clique; otherwise it ...

Only top voted, non community-wiki answers of a minimum length are eligible