Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Minimum bisection is fixed parameter tractable

Tools
- Tools
+ Tools

Cygan, Marek, Lokshtanov, Daniel, Pilipczuk, Marcin, Pilipczuk, Michał and Saurabh, Saket (2014) Minimum bisection is fixed parameter tractable. In: STOC '14 : 46th Annual ACM Symposium on Theory of Computing, New York, 31 May- 3 Jun 2014. Published in: STOC '14 Proceedings of the 46th Annual ACM Symposium on Theory of Computing pp. 323-332. ISSN 9781450327107. doi:10.1145/2591796.2591852

[img]
Preview
PDF
WRAP_1371795-cs-270115-bisection.pdf - Accepted Version - Requires a PDF viewer.

Download (547Kb) | Preview
Official URL: http://dx.doi.org/10.1145/2591796.2591852

Request Changes to record.

Abstract

In the classic Minimum Bisection problem we are given as input a graph G and an integer k. The task is to determine whether there is a partition of V (G) into two parts A and B such that ||A| -- |B|| ≤ 1 and there are at most k edges with one endpoint in A and the other in B. In this paper we give an algorithm for Minimum Bisection with running time O(2O(k3) n3 log3 n). This is the first fixed parameter tractable algorithm for Minimum Bisection. At the core of our algorithm lies a new decomposition theorem that states that every graph G can be decomposed by small separators into parts where each part is "highly connected" in the following sense: any cut of bounded size can separate only a limited number of vertices from each part of the decomposition.

Our techniques generalize to the weighted setting, where we seek for a bisection of minimum weight among solutions that contain at most k edges.

Item Type: Conference Item (Paper)
Alternative Title:
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science > Computer Science
Library of Congress Subject Headings (LCSH): Graph theory, Trees (Graph theory), Computer algorithms
Journal or Publication Title: STOC '14 Proceedings of the 46th Annual ACM Symposium on Theory of Computing
Publisher: ACM
ISSN: 9781450327107
Official Date: 2014
Dates:
DateEvent
2014UNSPECIFIED
Page Range: pp. 323-332
DOI: 10.1145/2591796.2591852
Status: Peer Reviewed
Publication Status: Published
Funder: Narodowe Centrum Nauki (NCN), Universitetet i Bergen‏, Seventh Framework Programme (European Commission) (FP7), European Research Council (ERC)
Grant number: UMO-2013/09/B/ST6/03136 (NCN), 267959 (ERC), 306992 (ERC)
Adapted As:
Embodied As: 1
Conference Paper Type: Paper
Title of Event: STOC '14 : 46th Annual ACM Symposium on Theory of Computing
Type of Event: Conference
Location of Event: New York
Date(s) of Event: 31 May- 3 Jun 2014
Related URLs:
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us