Damásdi, Gábor and Keszegh, Balázs and Pálvölgyi, Dömötör and Singh, Karamjeet (2025) The complexity of recognizing ABAB-free hypergraphs. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 27 (1). ISSN 1462-7264
|
Text
2409.01680.pdf - Draft Version Available under License Creative Commons Attribution. Download (158kB) | Preview |
Abstract
The study of geometric hypergraphs gave rise to the notion of ABAB-free hypergraphs. A hypergraph H is called ABAB-free if there is an ordering of its vertices such that there are no hyperedges A, B and vertices v1, v2, v3, v4 in this order satisfying v1, v3 ∈ A \\ B and v2, v4 ∈ B \\ A. In this paper, we prove that it is NP-complete to decide if a hypergraph is ABAB-free. We show a number of analogous results for hypergraphs with similar forbidden patterns, such as ABABA-free hypergraphs. As an application, we show that deciding whether a hypergraph is realizable as the incidence hypergraph of points and pseudodisks is also NP-complete. © 2025 Elsevier B.V., All rights reserved.
| Item Type: | Article |
|---|---|
| Additional Information: | HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary ELTE Eötvös Loránd University, Budapest, Hungary IIIT-D Indraprastha Institute of Information Technology, Delhi, India Export Date: 19 May 2025; Cited By: 0 |
| Uncontrolled Keywords: | GEOMETRY; hypergraphs; NP Complete; NP-hardness; Hyperedges; Hyper graph; Geometric hypergraphs; complexity; forbidden pattern; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 15 Sep 2025 09:18 |
| Last Modified: | 15 Sep 2025 09:18 |
| URI: | https://real.mtak.hu/id/eprint/224110 |
Actions (login required)
 |
Edit Item |
