The Library
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
|
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
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 > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Graph theory | ||||
| 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: | 2014 | ||||
| Dates: |
|
||||
| Date of first compliant deposit: | 28 December 2015 | ||||
| Page Range: | pp. 186-195 | ||||
| DOI: | 10.1109/FOCS.2014.28 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| 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 |
Downloads
Downloads per month over past year
