Questions tagged [graph-cut]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
0 answers
73 views

Minimum cost k-edge connected subgraph

The problem of finding a k-edge connected spanning subgraph with the minimum number of edges is $ \mathcal{NP} $-hard in general. Is it the case for positive weighted graphs with "fractional ...
Bence's user avatar
  • 21
0 votes
0 answers
27 views

What is known about "overlapping" models/minors of graphs

Suppose we are given a graph $G$ from a graph class of sublinear treewidth and connected subgraphs $G_1,G_2,..,G_l$ of $G$ such that each $G_i$ intersects (shares a node with) constant many other $G_j$...
Hao S's user avatar
  • 181
1 vote
0 answers
104 views

Maximum cut variation

Given an undirected graph $G=(V,E)$, the max-cut problem asks for the partition $S_1,S_2\subset V$ , s.t., the number of edges going from $S_1$ to $S_2$ are maximized. Is it possible to maximize the ...
Weslley Lioba Caldas's user avatar
0 votes
2 answers
237 views

Random Optimization on Graphs: Minimum Cut

Consider a complete graph on $n$ vertices. To each edge, $(i,j)$, we assign a weight, $W_{ij}$, which comes from some known distribution iid. Then, we ask the following question. Among all (weighted) ...
hookah's user avatar
  • 1,096
1 vote
0 answers
81 views

Karger's algorithm randomized min cut - probability of not contracting a particular edge

I know how Karger's algorithm works, and that the probability of finding a min-cut is over $1/n^2$. My question is the following. How can I find the probability of not contracting edges of a min-cut ...
K.Sot's user avatar
  • 11
2 votes
0 answers
204 views

expected number of edges for fixed min cut

It is known that a graph $G=(V,E)$ with $n$ nodes and min cut $k$, must have at least $\frac{1}{2}nk$ edges. Are there any tighter bounds or expectations I can place on $|E|$ if I assume that $G$ ...
user1798883's user avatar
1 vote
1 answer
1k views

Minimum spanning subgraph with at least one incoming and one outgoing edge

Given a single-component, directed acyclic graph with one source (vertex with only outgoing edges) and one sink (vertex with only incoming edges), I'd like to find a minimum spanning subgraph which ...
Alec Jacobson's user avatar
1 vote
1 answer
382 views

almost-bipartite nearly-isolated subgraphs

I am looking for examples/families of graphs with the following (maybe vague-sounding at first) property: the graph $G$ has a relatively large subgraph $B$ such that $B$ is bipartite-plus-a-few-edges ...
Felix Goldberg's user avatar