Document Open Access Logo

Dependent k-Set Packing on Polynomoids

Authors Meng-Tsung Tsai , Shi-Chun Tsai , Tsung-Ta Wu

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2023.84.pdf
  • Filesize: 0.73 MB
  • 15 pages

Document Identifiers

Author Details

Meng-Tsung Tsai
  • Institute of Information Science, Academia Sinica, Taipei, Taiwan
Shi-Chun Tsai
  • Computer Science, National Yang Ming Chiao Tung University, Hsinchu, Taiwan
Tsung-Ta Wu
  • Computer Science, National Yang Ming Chiao Tung University, Hsinchu, Taiwan

Funding

This research was supported in part by the National Science and Technology Council under contract NSTC grants 108-2221-E-009-051-MY3, 109-2221-E-001-025-MY3, and 112-2221-E-001-007.

Acknowledgements

We sincerely thank anonymous reviewers for their helpful comments.

Cite AsGet BibTex

Meng-Tsung Tsai, Shi-Chun Tsai, and Tsung-Ta Wu. Dependent k-Set Packing on Polynomoids. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 84:1-84:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.MFCS.2023.84

Abstract

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Matroids and greedoids
Keywords
  • Hereditary Systems
  • Hypergraph Matchings
  • Compleixty Trichotomy

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ron Aharoni. Matchings in n-partite n-graphs. Graphs Comb., 1(1):303-304, 1985. Google Scholar
  2. Ron Aharoni, Eli Berger, Dani Kotlar, and Ran Ziv. Degree conditions for matchability in 3-partite hypergraphs. J. Graph Theory, 87(1):61-71, 2018. Google Scholar
  3. Ron Aharoni and Penny Haxell. Hall’s theorem for hypergraphs. J. Graph Theory, 35(2):83-88, 2000. Google Scholar
  4. N. Alon. A note on the decomposition of graphs into isomorphic matchings. Acta Mathematica Hungarica, 42(3-4):221-223, September 1983. Google Scholar
  5. János Barát and Dániel Gerbner. Edge-decomposition of graphs into copies of a tree with four edges. Electron. J. Comb., 21(1):1, 2014. Google Scholar
  6. A. Bialostocki and Y. Roditty. 3K2-decomposition of a graph. Acta Mathematica Hungarica, 40(3-4):201-208, September 1982. Google Scholar
  7. Ahmad Biniaz, Anil Maheshwari, Subhas C. Nandy, and Michiel H. M. Smid. An optimal algorithm for plane matchings in multipartite geometric graphs. In Algorithms and Data Structures - 14th International Symposium (WADS), pages 66-78. Springer, 2015. Google Scholar
  8. Robert S. Boyer and J. Strother Moore. MJRTY: A fast majority vote algorithm. In Automated Reasoning: Essays in Honor of Woody Bledsoe, pages 105-118. Kluwer Acad. Publishers, 1991. Google Scholar
  9. Andries Brouwer and R. Wilson. The decomposition of graphs into ladder graphs, January 1980. Google Scholar
  10. Krzysztof Brys and Zbigniew Lonc. Polynomial cases of graph decomposition: A complete solution of Holyer’s problem. Discret. Math., 309(6):1294-1326, 2009. Google Scholar
  11. Rainer Burkard, Mauro Dell'Amico, and Silvano Martello. Assignment problems: revised reprint. SIAM, 2012. Google Scholar
  12. Ho Yee Cheung, Lap Chi Lau, and Kai Man Leung. Graph connectivities, network coding, and expander graphs. SIAM J. Comput., 42(3):733-751, 2013. Google Scholar
  13. Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM J. Comput., 14(1):210-223, 1985. Google Scholar
  14. David E Daykin and Roland Häggkvist. Degrees giving independent edges in a hypergraph. Bulletin of the Australian Mathematical Society, 23(1):103-109, 1981. Google Scholar
  15. Dorit Dor and Michael Tarsi. Graph decomposition is NP-complete: A complete proof of Holyer’s conjecture. SIAM J. Comput., 26(4):1166-1187, 1997. Google Scholar
  16. M.E. Dyer and A.M. Frieze. On the complexity of partitioning graphs into connected subgraphs. Discrete Applied Mathematics, 10(2):139-153, 1985. Google Scholar
  17. Jack Edmonds. Minimum partition of a matroid into independent subsets. Journal of Research of the National Bureau of Standards, 69B:67-72, 1965. Google Scholar
  18. O. Favaron, Z. Lonc, and M. Truszczynski. Decomposition of graphs into graphs with three edges. Ars Combin., 20:125-146, 1985. Google Scholar
  19. Anka Gajentaan and Mark H. Overmars. On a class of O(n²) problems in computational geometry. Comput. Geom., 5:165-185, 1995. Google Scholar
  20. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  21. Eunice Gogo Mphako. Circuit and cocircuit partitions of binary matroids. Czechoslovak Mathematical Journal, 56(1):19-25, 2006. Google Scholar
  22. Oded Goldreich. Combinatorial property testing (a survey). Randomization Methods in Algorithm Design, 43:45-59, 1999. Google Scholar
  23. Ralph E Gomory and Tien Chung Hu. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics, 9(4):551-570, 1961. Google Scholar
  24. Philip Hall. On representatives of subsets. Classic Papers in Comb., pages 58-62, 1987. Google Scholar
  25. Jie Han and Peter Keevash. Finding perfect matchings in dense hypergraphs. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2366-2377. SIAM, 2020. Google Scholar
  26. Jie Han and Andrew Treglown. The complexity of perfect matchings and packings in dense hypergraphs. J. Comb. Theory, Ser. B, 141:72-104, 2020. Google Scholar
  27. Penny E. Haxell. A condition for matchability in hypergraphs. GCOM., 11(3):245-248, 1995. Google Scholar
  28. Ian James Holyer. The computational complexity of graph theory problems, 1981. Google Scholar
  29. Cor A. J. Hurkens and Alexander Schrijver. On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discret. Math., 2(1):68-72, 1989. Google Scholar
  30. Frank K Hwang. A method for detecting all defective members in a population by group testing. Journal of the American Statistical Association, 67(339):605-608, 1972. Google Scholar
  31. Per M. Jensen and Bernhard Korte. Complexity of matroid property algorithms. SIAM J. Comput., 11(1):184-190, 1982. Google Scholar
  32. Viggo Kann. Maximum bounded 3-dimensional matching is MaxSNP-complete. Inf. Process. Lett., 37(1):27-35, 1991. Google Scholar
  33. Peter Keevash, Fiachra Knox, and Richard Mycroft. Polynomial-time perfect matchings in dense hypergraphs. In Symp. on Theory of Computing (STOC), pages 311-320. ACM, 2013. Google Scholar
  34. Imdadullah Khan. Perfect matchings in 3-uniform hypergraphs with large vertex degree. SIAM J. Discret. Math., 27(2):1021-1039, 2013. Google Scholar
  35. Imdadullah Khan. Perfect matchings in 4-uniform hypergraphs. J. Comb. Theory, Ser. B, 116:333-366, 2016. Google Scholar
  36. Silvio Micali and Vijay V. Vazirani. An O(√VE) algorithm for finding maximum matching in general graphs. In Symp. on Fnd. of Computer Science (FOCS), pages 17-27. IEEE, 1980. Google Scholar
  37. James G. Oxley. Matroid theory. Oxford University Press, 1992. Google Scholar
  38. Vojtech Rödl, Andrzej Rucinski, and Endre Szemerédi. Perfect matchings in uniform hypergraphs with large minimum degree. Eur. J. Comb., 27(8):1333-1349, 2006. Google Scholar
  39. Paul D. Seymour. Packing and covering with matroid circuits. J. Comb. Theory, Ser. B, 28(2):237-242, 1980. Google Scholar
  40. Nicolas Teypaz and Christophe Rapine. Graph decomposition into paths under length constraints. Technical report, UniK University Graduate Center, University of Oslo, 2004. Google Scholar
  41. D.J.A. Welsh. Euler and bipartite matroids. Journal of Comb. Theory, 6(4):375-377, 1969. Google Scholar
  42. Douglas B. West. Combinatorial Mathematics. CUP, 2020. Google Scholar
  43. Sanming Zhou. Minimum partition of an independence system into independent sets. Discret. Optim., 6(1):125-133, 2009. Google Scholar
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