79. Directed k-way Cut and Sparsest Set in Bipartite Graphs
Invited abstract in session TE-2: Network Optimization, stream Discrete Optimization.
Thursday, 16:45 - 18:15Room: C 103
Authors (first author is the speaker)
| 1. | Daniel Szabo
|
| Mathematics, Eötvös Loránd University | |
| 2. | Tamás Király
|
| Eötvös Loránd University |
Abstract
Given an edge weighted undirected graph G=(V,E), the k-way cut problem asks to find a minimum weight subset C of E such that G\C has k connected components. We extend this problem to directed graphs by requiring that G\C have k distinct vertices of which none can reach any other. This is a natural extension of the global bicut problem, which admits a less than 2-approximation yet there is a no known hardness result. Very little is known about the directed k-way cut problem, so we show NP hardness by reducing from the hardness of finding the sparsest set in bipartite graphs. This problem asks, given a bipartite graph G=(A,B;E), to find a set of max{|A|,|B|}+1 vertices with the minimum number of edges between them. We explore hardness of approximation as well as positive results for both of these problems.
Keywords
- Complexity and efficiency of optimization algorithms
- Complementarity and variational problems
- Analysis and engineering of optimization algorithms
Status: accepted
Back to the list of papers