DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2023.25

Deterministic Constrained Multilinear Detection

Authors: Cornelius Brand, Viktoriia Korchemna, and Michael Skotnica

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract

We extend the algebraic techniques of Brand and Pratt (ICALP'21) for deterministic detection of k-multilinear monomials in a given polynomial with non-negative coefficients to the more general situation of detecting colored k-multilinear monomials that satisfy additional constraints on the multiplicities of the colors appearing in them. Our techniques can be viewed as a characteristic-zero generalization of the algebraic tools developed by Guillemot and Sikora (MFCS'10) and Björklund, Kaski and Kowalik (STACS'13) As applications, we recover the state-of-the-art deterministic algorithms for the Graph Motif problem due to Pinter, Schachnai and Zehavi (MFCS'14), and give new deterministic algorithms for generalizations of certain questions on colored directed spanning trees or bipartite planar matchings running in deterministic time O^∗(4^k), studied originally by Gutin, Reidl, Wahlström and Zehavi (J. Comp. Sys. Sci. 95, '18). Finally, we give improved randomized algorithms for intersecting three and four matroids of rank k in characteristic zero, improving the record bounds of Brand and Pratt (ICALP'21) from O^∗(64^k) and O^∗(256^k), respectively, to O^∗(4^k).

Cite as

Cornelius Brand, Viktoriia Korchemna, and Michael Skotnica. Deterministic Constrained Multilinear Detection. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{brand_et_al:LIPIcs.MFCS.2023.25,
  author =	{Brand, Cornelius and Korchemna, Viktoriia and Skotnica, Michael},
  title =	{{Deterministic Constrained Multilinear Detection}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.25},
  URN =		{urn:nbn:de:0030-drops-185595},
  doi =		{10.4230/LIPIcs.MFCS.2023.25},
  annote =	{Keywords: Fixed-parameter algorithms, Algebraic algorithms, Motif discovery, Matroid intersection}
}

Search Results

Documents authored by Skotnica, Michael

Deterministic Constrained Multilinear Detection

Abstract

Cite as

Thanks for your feedback!

Could not send message