Skip to main content
MathOverflow

Return to Question

Bumped by Community user
Bumped by Community user
Bumped by Community user
tag edit
Link
Ben Barber
Ben Barber
  • 4.6k
  • 2
  • 25
  • 38
Minor Math Jaxing and emphasis on the question
Source Link
edit approved Mar 3, 2020 at 21:13
Daniele Tampieri
edit approved Mar 3, 2020 at 21:13
Daniele Tampieri
  • 6.4k
  • 7
  • 30
  • 45

I wonder whether the following problem is a well-studied NP-hard problem?

Get a graph G$G$ and a number k$k$, we partition the graph G$G$ into two components where each component should have at most k$k$ vertices and the number of edges in the cut is minimal.

In other words, is the mini-cut problem with the vertex budget constraint NP-hard?In other words, is the mini-cut problem with the vertex budget constraint NP-hard?

Thanks.

I wonder whether the following problem is a well-studied NP-hard problem?

Get a graph G and a number k, we partition the graph G into two components where each component should have at most k vertices and the number of edges in the cut is minimal.

In other words, is the mini-cut problem with the vertex budget constraint NP-hard?

Thanks.

I wonder whether the following problem is a well-studied NP-hard problem?

Get a graph $G$ and a number $k$, we partition the graph $G$ into two components where each component should have at most $k$ vertices and the number of edges in the cut is minimal.

In other words, is the mini-cut problem with the vertex budget constraint NP-hard?

Thanks.

Source Link
Polaris
Polaris
  • 111
  • 2

Is the graph minicut with the node cardinality constraint NP-hard?

I wonder whether the following problem is a well-studied NP-hard problem?

Get a graph G and a number k, we partition the graph G into two components where each component should have at most k vertices and the number of edges in the cut is minimal.

In other words, is the mini-cut problem with the vertex budget constraint NP-hard?

Thanks.