Questions tagged [partition-problem]
The partition-problem tag has no usage guidance.
83
questions
13
votes
1
answer
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
13
votes
1
answer
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
13
votes
1
answer
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 ...
- 20.8k
8
votes
4
answers
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
8
votes
1
answer
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
8
votes
3
answers
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
8
votes
2
answers
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
8
votes
1
answer
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
8
votes
0
answers
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 ...
- 189
7
votes
2
answers
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
7
votes
2
answers
2k
views
Partition a graph into 2 connected subgraphs
I'm stumped on a sub problem that I'm working on for my thesis. I need to be able to partition a graph into 2 connected subgraphs of almost equal size. So if there are $m$ vertices in $G$, subgraphs $...
- 383
7
votes
1
answer
1k
views
K-Clustering of a Graph maximizing intra-cluster weights?
I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results.
Input: A complete graph G with non-...
- 263
7
votes
0
answers
999
views
Partitioning DAG into Paths
What bounds (lower or upper) are known about the complexity of partitioning a Directly Acyclic Graph (DAG) into paths of respective sizes $n_1,\ldots,n_w$, such that to minimize their entropy $n{\cal ...
- 2,733
7
votes
0
answers
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
6
votes
2
answers
167
views
$NP$-Completeness of $\epsilon$-balanced graph partitioning for fixed $\epsilon$
Consider this graph partitioning problem: Let $G = (V, E)$ be a simple undirected graph and $0 \leq \epsilon \leq 1, M \geq 0$ be constants. Are there disjoint subsets $V_1, V_2$ with $V = V_1 \cup ...
- 71
6
votes
2
answers
922
views
Is this partition problem strongly NP-complete?
Some computational problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's Graph Isomorphism result) while the ...
- 20.8k
6
votes
1
answer
249
views
Uniformly sampling or counting connected graph partitions with any number of blocks
Question: Is it possible to uniformly sample in polynomial time from the set of all connected partitions of a graph? Or is there a JVV type argument that proves this to be NP-hard?
To clarify: By a ...
- 1,439
5
votes
0
answers
78
views
A simultaneous FPTAS for both max-min and min-max number partitioning
The multiway number partitioning problem has two optimization variants: in one variant the goal is to minimize the largest bin sum (the "makespan"), and in the other variant the goal is to ...
- 2,078
5
votes
0
answers
122
views
Variation on block design/set cover
Given 3 parameters $s, r$ and $t$, where $r \leq t$, I want to construct $t$ sets such that each integer $\{1, \ldots, s\}$ appears in exactly $r$ of these sets. The question is:
Is it possible to ...
- 51
4
votes
1
answer
491
views
Proof that the graph optimization problem is NP-hard
I'm trying to prove that the following optimization problem is NP-hard:
Given a graph $G=(V,E)$, non-negative vertex weight functions $w(v)$ and $s(v)$, and a non-negative edge weight function $t(u,v)...
- 239
4
votes
1
answer
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 ...
- 141
4
votes
0
answers
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
4
votes
0
answers
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
3
votes
1
answer
429
views
Variant of Subset Sum Problem with Changing Bound
Given a sequence of decreasing integers, i.e., $a_1 \geq a_2 \geq \cdots \geq a_T $ and a positive real $k\geq 1$, find a subset $S$ such that
$$\max_{S\subseteq \{1,\ldots,T\}} \sum_{i\in S} a_i$$
$$...
- 41
3
votes
1
answer
112
views
Meet of integer partitions
An integer partition of $n$, $A$, is a multiset of positive integers such that $\sum_{a \in A} a= n$. We say that $B \leq A$, if there exists a map $\phi: |B| \to |A|$, such that for $a \in A$, we ...
- 603
3
votes
2
answers
1k
views
Strongly NP-complete variants of subset sum or partition problem
Some problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's GI result). However, the fixed-point free GA ...
- 20.8k
3
votes
0
answers
93
views
Number of connected partitions (or labelings) in a grid graph
Let $G$ be a 2D lattice graph (undirected) of size $W\times H$. Each "inner" vertex has $4$ adjacent vertices, whereas "boundary" vertices have $2$ or $3$ adjacent vertices, ...
- 31
3
votes
0
answers
681
views
Graph partition with weighted vertices and edges
I am searching for an algorithm to apply to a specific graph partition problem that I am interested in. It feels like a topic that people from CS may have worked on but it is also different from ...
- 31
3
votes
0
answers
2k
views
DAG partitioning for parallel computing
Consider a set of processes ($P=\{p_1, p_2,\dots, p_n \}$) and their data dependencies. Each process $p_i$ has an execution runtime which is denoted by $d_i$. We are interested to parallelize these ...
- 251
2
votes
2
answers
278
views
Partitioning a connected polygon into connected pieces of equal area
Armaselu and Daescu (TCS, 2015) present algorithms that, given a convex polygon $P$ and an integer $m$ (which must be a power of $2$), return a partition of $P$ into $m$ convex polygons with the same ...
- 2,078
2
votes
1
answer
107
views
Can the Banach-Tarski paradox be "realized" by floating-point round-off?
The Banach-Tarski paradox says that
a ball in $\mathbb{R}^3$ can be partitioned into a finite number of pieces, whose rearrangement has a larger volume than the original.
It occurred to me that it ...
- 3,743
2
votes
1
answer
390
views
Partition refinement in transition state systems (bisimulation contraction)
I am trying to understand bisimulation contraction of Kripke models.
I have read these lecture slides and this Wikipedia page, but I still don't fully understand it.
I can understand that the two ...
- 129
2
votes
1
answer
111
views
NP hard proving: separate graph into a set of the same size disjoint parts by maximizing the shared neighbours of each part
Given a graph $G=\{V,E\}$ where $V$ denotes the nodes and $E$ denotes edges. The size of the node $|V| = nk$. The target is to separte the graph into $n$ disjoint parts $P=\{V_i\}_{i=1}^n$ and the ...
- 67
2
votes
1
answer
1k
views
Max-sum graph-partition for maximizing intra-edge weights?
I would like to know if the following problem has already been studied, and if so how is it called. In particular I'm interested in approximability results.
Input: A graph G with negative or non-...
- 21
2
votes
1
answer
121
views
partition to min the max number of intersections
Given $n$ items and $m$ customers, each of whom is interested in some subset of the items, partition the set of items among $k$ different stores so that the maximum number of customers visiting any ...
- 21
2
votes
1
answer
432
views
Partitioning a matrix into equal-sized regions: finding the maximum
I am facing the following research problem. We are given a matrix $M[1..p,1..p]$ of elements such that:
each element has value in the range $[0, \frac 1 j]$, $j <= p$, $j$ is given,
the sum of all ...
- 21
2
votes
0
answers
21
views
Hardness of 3-Partition with Small Target Value
In the 3-partition problem, we are given a set of positive integers $a_1,\ldots,a_n$ and a target value $T$; the goal is to decide if there is a partition of the numbers to triplets such that the sum ...
- 173
2
votes
0
answers
63
views
Partition of a set of integers into subsets where the max. of the subset-sums is minimum
Let $S$ be a set of $n$ positive integers, and $p$ be a partition of $S$ into $m$ mutually disjoint subsets, such that no subset contains more than $k$ elements.
Let $\mathcal{P}$ denote the set of ...
2
votes
0
answers
59
views
hardness of partition of permutation into a minimum number of monotone subsequences
Given a permutation P, a monotone subsequence is a subsequence (i.e. the elements do not have to be consecutive in P) that increases or decreases. This leads naturally to the following optimization ...
- 71
2
votes
0
answers
105
views
Small set expansion and expanders
Given a graph $G=(V,E)$ on $n$ vertices and $0 \leq \delta \leq 1/2$, we can define the expansion of $G$ over small sets:
$$
h(G,\delta)= \min_{\vert S\vert \leq \delta n } \phi(S) \ ,
$$
with
$$\phi(...
- 41
2
votes
0
answers
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 ...
- 21
2
votes
0
answers
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
2
votes
0
answers
114
views
a direct polynomial reduction from 3EQU-SUM to EQU-SUM problem [closed]
Given a multiset of integers $S$, in the Equ-Sum problem we want to check
whether
or not $S$ can be divided into two disjoint subsets, say $X_1$, $X_2$ such that $\sum_{x_i \in X_1}x_i = \sum_{x_j \...
2
votes
0
answers
76
views
Hardness result or reference for a set partition problem
I'm wondering if the following problem is (or has been proven to be) NP-Complete.
Input: integer $n\ge0$, set $S_1,S_2,\ldots,S_{2n}$, set $T_1,T_2,\ldots,T_n$.
Accept iff: there exists $\{a_i,...
- 101
2
votes
0
answers
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 ...
- 21
2
votes
0
answers
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
2
votes
1
answer
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 ...
user30584
2
votes
0
answers
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....
- 81
2
votes
0
answers
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
2
votes
0
answers
216
views
Graph optimization problem with multiple objectives/constraints
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 ...
- 239