License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2018.32
URN: urn:nbn:de:0030-drops-83144
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8314/
Lokshtanov, Daniel ;
Misra, Pranabendu ;
Panolan, Fahad ;
Saurabh, Saket ;
Zehavi, Meirav
Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity
Abstract
Deterministic polynomial-time computation of a representation of a transversal matroid is a longstanding open problem. We present a deterministic computation of a so-called union representation of a transversal matroid in time quasipolynomial in the rank of the matroid. More precisely, we output a collection of linear matroids such that a set is independent in the transversal matroid if and only if it is independent in at least one of them. Our proof directly implies that if one is interested in preserving independent sets of size at most r, for a given r\in\mathbb{N}, but does not care whether larger independent sets are preserved, then a union representation can be computed deterministically in time quasipolynomial in r. This consequence is of independent interest, and sheds light on the power of union~representation.
Our main result also has applications in Parameterized Complexity. First, it yields a fast computation of representative sets, and due to our relaxation in the context of r, this computation also extends to (standard) truncations. In turn, this computation enables to efficiently solve various problems, such as subcases of subgraph isomorphism, motif search and packing problems, in the presence of color lists. Such problems have been studied to model scenarios where pairs of elements to be matched may not be identical but only similar, and color lists aim to describe the set of compatible elements associated with each element.
BibTeX - Entry
@InProceedings{lokshtanov_et_al:LIPIcs:2018:8314,
author = {Daniel Lokshtanov and Pranabendu Misra and Fahad Panolan and Saket Saurabh and Meirav Zehavi},
title = {{Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {32:1--32:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-060-6},
ISSN = {1868-8969},
year = {2018},
volume = {94},
editor = {Anna R. Karlin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8314},
URN = {urn:nbn:de:0030-drops-83144},
doi = {10.4230/LIPIcs.ITCS.2018.32},
annote = {Keywords: travserval matroid, matroid representation, union representation, representative set}
}
|
Keywords: |
|
travserval matroid, matroid representation, union representation, representative set |
|
Collection: |
|
9th Innovations in Theoretical Computer Science Conference (ITCS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
12.01.2018 |
