11 votes
Accepted

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

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 ...
David Eppstein's user avatar
9 votes
Accepted

Proof that the graph optimization problem is NP-hard

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 ...
saisandeep's user avatar
5 votes
Accepted

A partition problem in which some numbers may be cut

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 ...
Mikhail Rudoy's user avatar
5 votes

Partition refinement in transition state systems (bisimulation contraction)

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'...
Fabio Somenzi's user avatar
5 votes

Variant of Subset Sum Problem with Changing Bound

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 ...
David Eppstein's user avatar
5 votes
Accepted

A partition problem with order constraints

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 ...
Neal Young's user avatar
  • 10.7k
5 votes

Can the Banach-Tarski paradox be "realized" by floating-point round-off?

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}...
Denis's user avatar
  • 8,843
4 votes

3 Matroid Intersection, a Special Case

Your problem is a multi-budgeted matroid intersection with two budgets. There is a PTAS for that [1]. However, your case is so special, better algorithm exists. You can assume there is only a single ...
Chao Xu's user avatar
  • 4,449
4 votes

Partitioning a connected polygon into connected pieces of equal area

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 ...
David Eppstein's user avatar
4 votes
Accepted

Meet of integer partitions

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 ...
Antti Röyskö's user avatar
4 votes
Accepted

$NP$-Completeness of $\epsilon$-balanced graph partitioning for fixed $\epsilon$

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 ...
Mohammad Al-Turkistany's user avatar
3 votes

Faster pseudo-polynomial time algorithms for PARTITION

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 ...
hqztrue's user avatar
  • 112
3 votes

A partition problem in which some numbers may be cut

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: ...
Gamow's user avatar
  • 5,772
3 votes

Is this partition problem strongly NP-complete?

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: ...
Marzio De Biasi's user avatar
3 votes

A partition problem in which some numbers may be cut

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 ...
Chao Xu's user avatar
  • 4,449
3 votes

Strongly NP-complete variants of subset sum or partition problem

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$ ...
Marzio De Biasi's user avatar
3 votes

Max-sum graph-partition for maximizing intra-edge weights?

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-...
Chandra Chekuri's user avatar
3 votes
Accepted

NP hard proving: separate graph into a set of the same size disjoint parts by maximizing the shared neighbours of each part

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 ...
Marzio De Biasi's user avatar
3 votes
Accepted

Name of this graph partitioning problem? (related to coloring)

(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 ...
Jukka Suomela's user avatar
3 votes
Accepted

Partitioning a connected polygon into connected pieces of equal area

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 ...
Sariel Har-Peled's user avatar
2 votes
Accepted

A k-approximation to k-way number partitioning

Here is a detailed elaboration of Chandra's suggestion in the comments, namely that OP's (first) request, for a poly-time algorithm that can pack $S$ into $k$ bins of size at most MinMax$(S, k-\delta)$...
Neal Young's user avatar
  • 10.7k
1 vote

strong NP-completeness of multi-dimensional Equal-Subset-Sum

EDIT: I did not answer the original question about EQUAL SUBSET SUM but instead described a reduction for the PARTITION version. I am leaving it here since the OP found this answer useful. It may be ...
Chandra Chekuri's user avatar
1 vote

Is this edge-partitioning NP-Hard?

This question boils down to answering to simpler questions. Can you find a graph with 6 edges where it is impossible to partition the edges? In a graph of more than 6 edges can you always find a ...
Martin Vatshelle's user avatar
1 vote

Complexity and Algorithm for specific Vertex Separator Problem

I understand that the question is about the time bound, not about the correctness of the reduction. The claim does not sound obvious (although a bound of $\mathcal{O}(n^3n^2k)$ can be shown with a ...
Vinicius dos Santos's user avatar
1 vote

Name of this graph partitioning problem? (related to coloring)

I think under typical terminology this would be called "Min k-Uncut" (note, Min Uncut asks for a partition into two that minimizes the number of edges not cut, and Max k-Uncut asks for a k ...
Ryan Williams's user avatar
1 vote

Uniformly sampling or counting connected graph partitions with any number of blocks

The generalized question about exact counting of flats of a matroid has an answer. Let $G$ be a graph, and let $G^{\circ}$ be the same graph with a loop at every vertex. Then, the flats of the ...
Elle Najt's user avatar
  • 1,439
1 vote

Complexity of a variant of partition problem

The problem of finding a maximum cardinality discrepancy partition (or determining that one doesn't exist) is solvable in pseudo-polynomial time even if a balanced partition is not given. Suppose ...
Mikhail Rudoy's user avatar
1 vote

Strongly NP-complete variants of subset sum or partition problem

I found a strongly NP-complete variant of partition (which does not take advantage of special number representations ). It is known as Product Partition problem (similar to partition problem but with ...
Mohammad Al-Turkistany's user avatar
1 vote
Accepted

Maximal Clique partition of vertices with smallest number of cut edges

This problem is the Cluster Edge Deletion problem. Given a graph $G = (V,E)$ and an integer, can we delete at most $k$ edges $F \subseteq E$ such that $G-F$ is a cluster graph? A cluster graph ...
Pål GD's user avatar
  • 550

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