2026-08-18T21:30:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18618 2024-03-06T11:02:16Z ddc:004 open_access

Dependent k-Set Packing on Polynomoids Tsai, Meng-Tsung Tsai, Shi-Chun Wu, Tsung-Ta Hereditary Systems Hypergraph Matchings Compleixty Trichotomy Specialized hereditary systems, e.g., matroids, are known to have many applications in algorithm design. We define a new notion called d-polynomoid as a hereditary system (E, ℱ ⊆ 2^E) so that every two maximal sets in ℱ have less than d elements in common. We study the problem that, given a d-polynomoid (E, ℱ), asks if the ground set E contains 𝓁 disjoint k-subsets that are not in ℱ, and obtain a complexity trichotomy result for all pairs of k ≥ 1 and d ≥ 0. Our algorithmic result yields a sufficient and necessary condition that decides whether each hypergraph in some classes of r-uniform hypergraphs has a perfect matching, which has a number of algorithmic applications. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Meng-Tsung Tsai and Shi-Chun Tsai and Tsung-Ta Wu 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.84 urn:nbn:de:0030-drops-186180 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.84 eng https://creativecommons.org/licenses/by/4.0/legalcode