# Tag Info

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 ...
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
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,768

### 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'...

### 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 ...
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 ...
• 10.8k

• 1,786
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 ...
• 6,999
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,349
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.5k
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,469
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,768
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 ...
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 ...
• 550

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