# Questions tagged [partition-problem]

The tag has no usage guidance.

83 questions
Filter by
Sorted by
Tagged with
544 views

### Partition into interval graphs

Suppose there is a graph $G=(V,E)$. I want to test if $V$ can be partitioned into two disjoint sets $V_1$ and $V_2$ such that the subgraphs induced by $V_1$ and $V_2$ are unit interval graphs. I know ...
• 1,006
384 views

### Another variant of PARTITION

I've got a reduction of the following partition problem to a certain scheduling problem: Input: A list $a_1\leqslant\cdots\leqslant a_n$ of positive integers in non-decreasing order. Question: Does ...
• 1,026
820 views

### Intermediate $\mathsf{NP}$-complete problems?

Partition problem is weakly NP-complete since it has polynomial (pseudo-polynomial) time algorithm if input integers are bounded by some polynomial. However, 3-Partition is strongly NP-complete ...
2k views

### Partitioning graphs while minimizing inter-partition edges

I'm working on trying to partition a triangulated graph into connected subgraphs with some guarantees on the number of inter-partition edges. Here's an example of a triangulated graph that has been ...
• 383
242 views

### Finding vertex separator such that the induced subgraph has minimal number of edges

My problem is related to edge and vertex cuts with a little twist. Given a graph $G$ and two vertexes $u$ and $v$. I want to find a set of vertexes $S \subset V$ that disconnects $u$ and $v$ such that ...
• 183
934 views

### A partition problem in which some numbers may be cut

In the standard partition problem, we are given some numbers whose sum is $2s$ and have to decide whether they can be partitioned into two subset whose sum is $s$. It is known to be NP-hard. However,...
• 2,078
2k views

### Faster pseudo-polynomial time algorithms for PARTITION

I want to partition N given numbers (may or may not be equal) into 2 subsets such that the 2 subsets have sum as close as possible and also the cardinality of the sets are equal (if n is even) or ...
• 155
332 views

### A partition problem with order constraints

In the OrderedPartition problem, the input is two sequences of $n$ positive integers, $(a_i)_{i\in [n]}$ and $(b_i)_{i\in [n]}$. The output is a partition of the ...
• 2,078
815 views

### Is this minimization problem NP-Complete?

We are given an $n \times (n + k)$ matrix $A$, with entries in GF(2), of the form $A =[I_n\ B]$, where $I_n$ is the $n \times n$ identity matrix, and $B$ has no "zero" rows or columns. The problem is ...
2k views

### Partition planar graph into connected subgraphs of equal size

Work Jünger, Michael, Gerhard Reinelt, and William R. Pulleyblank. "On partitioning the edges of graphs into connected subgraphs." Journal of graph theory 9.4 (1985): 539-549. states that for 4-...
• 891
2k views

• 2,733
832 views

### Approximation results for 3-partition

The 3-partition as defined here is a strongly NP-complete decision problem. Consider one optimization problem of 3-partition where the $m$ subsets each have at most three elements and a sum of not ...
• 951
167 views

• 239
192 views

### Set partitioning algorithm

I'm a working software engineer and I'm trying to develop some planning software. I have faced the following problem. I have some finite set $U$ of some distinct elements $e_i \in U$. I have ...
138 views

### Split a string of positive numbers into substrings with decreasing totals

Suppose we're given a string of $n$ positive numbers and asked to split it into the maximum number of substrings whose totals are decreasing. I have an $O(n)$ time DP algorithm, but is it already ...
• 51
48 views

### Minimal partition covering?

I am working on a problem that arises in the design of experiments. I wonder if it is part of a well-studied class of problems. The problem is: Start with a set of points $S$ and a target partition of ...
• 141
429 views

• 41
86 views

### Is the following special case of multiway number partitioning NP-hard?

The following problem is a decision problem of multiway number partitioning (wikipedia) (Note that $k$ is also a part of an input in the following problem, while $k$ is a fixed number in wikipedia ...
58 views

### Complexity of a matrix partition problem in graphs

All graphs in this question are finite, simple, and undirected. Let $H$ be a regular graph on at least five vertices, let $v_1,v_2,\dots,v_n$ be the vertices in $H$, and let $M$ be the adjacency ...
• 1,723
114 views

• 101
73 views

### Partition into c and 1-c

Let $c\in(0,1/2]$ be a constant. Given a set of positive integers with sum $S$, is there a partition into two subsets such that both subsets have sum at least $cS$? If $c=1/2$, this is the famous ...
53 views

### Min cut problem on unbalanced partitions for planar graphs with unit capacity edges

The question is: given a planar graph $G$ with unit capacity edge weights and a fixed positive integer $k$, what is an approximation algorithm for finding the minimum size of a cut $(A,B)$ with $|A|=k$...
• 21
249 views

### Optimal partition according to partition cardinality

Given $N$ sets of integers $S_1, \ldots,S_N$ with $|S_i| \le K$. We want to partition those sets such that the union of all sets in any given partition doesn't contain more than $K$ elements. Can ...
181 views

### Is Non-linear Constrained Optimal Exact Cover NP-Hard?

Playing around I ran into a problem which looks like a Exact Set Covering / Partition Problem, but I am unable to find a reduction to categorize the complexity of the problem, despite it looks NP-Hard....
113 views

### Unbalanced connected partition

Let $G = (V, E)$ be a connected graph with (possibly negative) vertex weights $w(v)\in\mathbb{Z}$. We want to partition the vertices into two parts such that the induced graphs $G'$ and $G''$ are ...
• 121
Let's assume that we have a directed acyclic graph $G = (V, E)$, non-negative vertex weight functions $w_a(v)$ and $w_b(v)$, and a non-negative edge weight function $t(u,v)$. We can divide vertices in ...