A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909357618233344 |
|---|---|
| author | Beines, Arne Kaibel, Michael Mayer, Philip Mutzel, Petra Sauer, Jonas |
| author_facet | Beines, Arne Kaibel, Michael Mayer, Philip Mutzel, Petra Sauer, Jonas |
| contents | We present parametric breadth-first search (PBFS), a new algorithm for solving the parametric minimum cut problem in a network with source-sink-monotone capacities. The objective is to find the set of breakpoints, i.e., the points at which the minimum cut changes. It is well known that this problem can be solved in the same asymptotic runtime as the static minimum cut problem. However, existing algorithms that achieve this runtime bound involve fairly complicated steps that are inefficient in practice. PBFS uses a simpler approach that discovers the breakpoints in ascending order, which allows it to achieve the desired runtime bound while still performing well in practice. We evaluate our algorithm on benchmark instances from polygon aggregation and computer vision. Polygon aggregation was recently proposed as an application for parametric minimum cut, but the monotonicity property has not been exploited fully. PBFS outperforms the state of the art on most benchmark instances, usually by a factor of 2-3. It is particularly strong on instances with many breakpoints, which is the case for polygon aggregation. Compared to the existing min-cut-based approach for polygon aggregation, PBFS scales much better with the instance size. On large instances with millions of vertices, it is able to compute all breakpoints in a matter of seconds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_15920 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order Beines, Arne Kaibel, Michael Mayer, Philip Mutzel, Petra Sauer, Jonas Data Structures and Algorithms We present parametric breadth-first search (PBFS), a new algorithm for solving the parametric minimum cut problem in a network with source-sink-monotone capacities. The objective is to find the set of breakpoints, i.e., the points at which the minimum cut changes. It is well known that this problem can be solved in the same asymptotic runtime as the static minimum cut problem. However, existing algorithms that achieve this runtime bound involve fairly complicated steps that are inefficient in practice. PBFS uses a simpler approach that discovers the breakpoints in ascending order, which allows it to achieve the desired runtime bound while still performing well in practice. We evaluate our algorithm on benchmark instances from polygon aggregation and computer vision. Polygon aggregation was recently proposed as an application for parametric minimum cut, but the monotonicity property has not been exploited fully. PBFS outperforms the state of the art on most benchmark instances, usually by a factor of 2-3. It is particularly strong on instances with many breakpoints, which is the case for polygon aggregation. Compared to the existing min-cut-based approach for polygon aggregation, PBFS scales much better with the instance size. On large instances with millions of vertices, it is able to compute all breakpoints in a matter of seconds. |
| title | A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.15920 |