Questions tagged [partition-problem]
The partition-problem tag has no usage guidance.
6
questions
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
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
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
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
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
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