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 ...
- 50.9k
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 ...
- 126
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 ...
- 2,758
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'...
- 151
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 ...
- 50.9k
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 ...
- 9,595
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}...
- 8,598
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 ...
- 4,367
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 ...
- 50.9k
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 ...
- 551
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 ...
- 20.8k
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 ...
- 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: ...
- 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: ...
- 22.6k
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 ...
- 4,367
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$ ...
- 22.6k
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-...
- 6,979
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 ...
- 22.6k
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 ...
- 9,596
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 ...
- 11.5k
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 ...
- 1,339
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 ...
- 1,868
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 ...
- 27.3k
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 ...
- 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 ...
- 2,758
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 ...
- 548
Only top scored, non community-wiki answers of a minimum length are eligible