Search Results

Documents authored by Levet, Michael

Document
DOI: 10.4230/LIPIcs.SWAT.2024.3
Pairwise Rearrangement is Fixed-Parameter Tractable in the Single Cut-and-Join Model

Authors: Lora Bailey, Heather Smith Blake, Garner Cochran, Nathan Fox, Michael Levet, Reem Mahmoud, Inne Singgih, Grace Stadnyk, and Alexander Wiedemann

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
Genome rearrangement is a common model for molecular evolution. In this paper, we consider the Pairwise Rearrangement problem, which takes as input two genomes and asks for the number of minimum-length sequences of permissible operations transforming the first genome into the second. In the Single Cut-and-Join model (Bergeron, Medvedev, & Stoye, J. Comput. Biol. 2010), Pairwise Rearrangement is #P-complete (Bailey, et. al., COCOON 2023), which implies that exact sampling is intractable. In order to cope with this intractability, we investigate the parameterized complexity of this problem. We exhibit a fixed-parameter tractable algorithm with respect to the number of components in the adjacency graph that are not cycles of length 2 or paths of length 1. As a consequence, we obtain that Pairwise Rearrangement in the Single Cut-and-Join model is fixed-parameter tractable by distance. Our results suggest that the number of nontrivial components in the adjacency graph serves as the key obstacle for efficient sampling.
Cite as

Lora Bailey, Heather Smith Blake, Garner Cochran, Nathan Fox, Michael Levet, Reem Mahmoud, Inne Singgih, Grace Stadnyk, and Alexander Wiedemann. Pairwise Rearrangement is Fixed-Parameter Tractable in the Single Cut-and-Join Model. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bailey_et_al:LIPIcs.SWAT.2024.3,
  author =	{Bailey, Lora and Blake, Heather Smith and Cochran, Garner and Fox, Nathan and Levet, Michael and Mahmoud, Reem and Singgih, Inne and Stadnyk, Grace and Wiedemann, Alexander},
  title =	{{Pairwise Rearrangement is Fixed-Parameter Tractable in the Single Cut-and-Join Model}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.3},
  URN =		{urn:nbn:de:0030-drops-200436},
  doi =		{10.4230/LIPIcs.SWAT.2024.3},
  annote =	{Keywords: Genome Rearrangement, Phylogenetics, Single Cut-and-Join, Computational Complexity}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.32
Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler-Leman

Authors: Michael Levet, Puck Rombach, and Nicholas Sieger

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
In this paper, we show that computing canonical labelings of graphs of bounded rank-width is in TC². Our approach builds on the framework of Köbler & Verbitsky (CSR 2008), who established the analogous result for graphs of bounded treewidth. Here, we use the framework of Grohe & Neuen (ACM Trans. Comput. Log., 2023) to enumerate separators via split-pairs and flip functions. In order to control the depth of our circuit, we leverage the fact that any graph of rank-width k admits a rank decomposition of width ≤ 2k and height O(log n) (Courcelle & Kanté, WG 2007). This allows us to utilize an idea from Wagner (CSR 2011) of tracking the depth of the recursion in our computation. Furthermore, after splitting the graph into connected components, it is necessary to decide isomorphism of said components in TC¹. To this end, we extend the work of Grohe & Neuen (ibid.) to show that the (6k+3)-dimensional Weisfeiler-Leman (WL) algorithm can identify graphs of rank-width k using only O(log n) rounds. As a consequence, we obtain that graphs of bounded rank-width are identified by FO + C formulas with 6k+4 variables and quantifier depth O(log n). Prior to this paper, isomorphism testing for graphs of bounded rank-width was not known to be in NC.
Cite as

Michael Levet, Puck Rombach, and Nicholas Sieger. Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler-Leman. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{levet_et_al:LIPIcs.SWAT.2024.32,
  author =	{Levet, Michael and Rombach, Puck and Sieger, Nicholas},
  title =	{{Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler-Leman}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{32:1--32:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.32},
  URN =		{urn:nbn:de:0030-drops-200724},
  doi =		{10.4230/LIPIcs.SWAT.2024.32},
  annote =	{Keywords: Graph Isomorphism, Weisfeiler-Leman, Rank-Width, Canonization, Descriptive Complexity, Circuit Complexity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact