# Tag Info

## Hot answers tagged partition-problem

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

11

An independent set that disconnects its graph is called an "independent cut", graphs that contain an independent cut are called "fragile graphs", and recognizing fragile graphs is known NP-complete [C. deFigueiredo, S. Klein, "NP-completeness of multipartite cutset testing", Congr. Numer. 119 (1996) 217–222, as cited by Guantao ...

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

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

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

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

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

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^{... 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 This seems to have little to do with Banach-Tarski. In your setting, f is simply not an isometry due to floating-point errors, and in particular there must be a single piece$i$such that$\mathrm{Vol}(f(P_i))>\mathrm{Vol}(P_i)$, so no need to cut into several pieces. Banach-Tarski works because the notion of volume is not well-defined on the pieces. ... 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. 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 The case where$\epsilon$is a fixed constant in$(0,1)$represents a partition that each part contains at least a constant fraction of the vertices. This was proven to be NP-complete by Wagner and Wagner. This is also known as balanced minimum cut problem. Note that$|V_i| \leq (1+\epsilon)|V|/2$if and only if$|V_i| \ge (1-\epsilon)|V|/2$for$\epsilon$... 4 The problem is strongly NP-complete. Reduction from 3-partition, a strongly NP-complete problem. The multiset$S$,$|S| = 3m$,$\sum_{x \in S} x = n$can be partitioned into tuples of size three of equal sum if and only if$A \leq B$where$A = S$and$B$is$m$duplicates of$\frac{n}{m}$. If$A \leq B$, we can have$C = A$. If$A \not\leq B$, we must have ... 4 To complement Sariel's answer, some closely related problems are hard. In particular, for a non-convex polygon, it's NP-hard to find a partition into two pieces of equal area while minimizing the length of the cut. See: Elias Koutsoupias, Christos Papadimitriou, and Martha Sideri (1992), "On the optimal bisection of a polygon", ORSA J. Comput. 4 (4)... 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...

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 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 rationals$a_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 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 (... 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 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 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

You can notice that $SN_i$ is maximum if $P_i$ is a clique of size $|P_i|$. So the decision version of your problem is very similar to the CLIQUE PARTITION PROBLEM which is NP-complete, the only difference is that you require that all parts $P_i$ have the same size. But the problem of partitioning a graph into 3 cliques of the same size is still NP-...

3

There must be many ways to do it - here is one way... Compute the medial axis of the polygon using the $L_1$ metric. Any point on the boundary defines a natural segment that goes from this point to a point on the medial axis - lets call the leash of the point. Pick an arbitrary point on the boundary of the polygon, and start moving it counterclockwise. ...

3

(Copied from a comment:) If you are not interested in approximations, then you can equally well look at the question of maximizing the number of edges between different parts, and this is usually known as "maximum k-cut" and also "maximum k-colorable subgraph".

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