20.500.12556/RUP-21787 Conformal hypergraphs duality and implications for the upper clique transversal problem Given a hypergraph H, the dual hypergraph of H is the hypergraph of all minimal transversals of H. The dual hypergraph is always Sperner, that is, no hyperedge contains another. A special case of Sperner hypergraphs are the conformal Sperner hypergraphs, which correspond to the families of maximal cliques of graphs. All these notions play an important role in many fields of mathematics and computer science, including combinatorics, algebra, database theory, etc. In this paper we study conformality of dual hypergraphs and prove several results related to the problem of recognizing this property. In particular, we show that the problem is in co-NP and can be solved in polynomial time for hypergraphs of bounded dimension. In the special case of dimension 3, we reduce the problem to 2-Satisfiability. Our approach has an implication in algorithmic graph theory: we obtain a polynomial-time algorithm for recognizing graphs in which all minimal transversals of maximal cliques have size at most k, for any fixed k. conformal hypergraph dual hypergraph hypergraph maximal clique upper clique transversal konformen hipergraf dualen hipergraf hipergraf maksimalna klika zgornja klična transverzala true false false Angleški jezik Slovenski jezik Članek v reviji 2025-09-25 15:26:24 2025-09-25 15:26:25 2025-10-16 03:05:08 0000-00-00 00:00:00 2025 0 0 str. 466-480 iss. 4 Vol. 109 Aug. 2025 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.179.1 1097-0118 10.1002/jgt.23238 230094851 RAZ_Boros_Endre_2025.pdf RAZ_Boros_Endre_2025.pdf 1 16CC9114F29E2DC8B7E968A81062A3E0 09d4cda1353fbc52a4d28eea5570bf11ac14551f4504796ff94b73d2361ae8be 7e0ff552-9a13-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=31675 https://onlinelibrary.wiley.com/doi/full/10.1002/jgt.23238 1 5b9bec76-9a13-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=31674 Fakulteta za matematiko, naravoslovje in informacijske tehnologije Inštitut Andrej Marušič 0 0 0