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

Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth

Tools
- Tools
+ Tools

Lokshtanov, Daniel, Pilipczuk, Marcin, Pilipczuk, Michał and Saurabh, Saket (2014) Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth. In: 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014), Philadelphia, PA, 18-21 Oct 2014. Published in: Proceedings of 2014 IEEE Annual Symposium on Foundations of Computer Science pp. 186-195. ISBN 9781479965175. ISSN 0272-5428. doi:10.1109/FOCS.2014.28

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

Download (611Kb) | Preview
Official URL: http://dx.doi.org/10.1109/FOCS.2014.28

Request Changes to record.

Abstract

We give a fixed-parameter tractable algorithm that, given a parameter k and two graphs G1, G2, either concludes that one of these graphs has treewidth at least k, or determines whether G1 and G2 are isomorphic. The running time of the algorithm on an n-vertex graph is 2O(k5 log k) · n5, and this is the first fixed-parameter algorithm for Graph Isomorphism parameterized by treewidth. Our algorithm in fact solves the more general canonization problem. We namely design a procedure working in 2OO(k5 log k) · n5 time that, for a given graph G on n vertices, either concludes that the treewidth of G is at least k, or finds an isomorphism-invariant construction term - an algebraic expression that encodes G together with a tree decomposition of G of width O(k4). Hence, a canonical graph isomorphic to G can be constructed by simply evaluating the obtained construction term, while the isomorphism test reduces to verifying whether the computed construction terms for G1 and G2 are equal.

Item Type: Conference Item (Paper)
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Graph theory
Series Name: Annual IEEE Symposium on Foundations of Computer Science
Journal or Publication Title: Proceedings of 2014 IEEE Annual Symposium on Foundations of Computer Science
Publisher: IEEE Computer Society
ISBN: 9781479965175
ISSN: 0272-5428
Book Title: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science
Official Date: December 2014
Dates:
DateEvent
December 2014Published
11 December 2014Available
Page Range: pp. 186-195
DOI: 10.1109/FOCS.2014.28
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Funder: Bergen Research Foundation (BRF), Seventh Framework Programme (European Commission) (FP7), European Research Council (ERC)
Grant number: 267959 (ERC), 306992 (ERC)
Embodied As: 1
Conference Paper Type: Paper
Title of Event: 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014)
Type of Event: Conference
Location of Event: Philadelphia, PA
Date(s) of Event: 18-21 Oct 2014

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