Hypergraph Representation via Axis-Aligned Point-Subspace Cover

DOI10.1007/978-3-030-96731-4_27MaRDI QIDQ6384033arXivFDO

Authors Oksana Firman, Joachim Spoerhase

Publication date 26 November 2021

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-96731-4_27

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

arXiv classification

cs.DMmath.CO

Abstract: We propose a new representation of $k$-partite, $k$-uniform hypergraphs (i.e. a hypergraph with a partition of vertices into $k$ parts such that each hyperedge contains exactly one vertex of each type; we call them $k$-hypergraphs for short) by a finite set $P$ of points in $mathbb{R}^d$ and a parameter $ellleqd-1$. Each point in $P$ is covered by $k=dchooseell$ many axis-aligned affine $ell$-dimensional subspaces of $mathbb{R}^d$, which we call $ell$-subspaces for brevity. We interpret each point in $P$ as a hyperedge that contains each of the covering $ell$-subspaces as a vertex. The class of $(d,ell)$-hypergraphs is the class of $k$-hypergraphs that can be represented in this way, where $k=dchooseell$. The resulting classes of hypergraphs are fairly rich: Every $k$-hypergraph is a $(k,k-1)$-hypergraph. On the other hand, $(d,ell)$-hypergraphs form a proper subclass of the class of all $dchooseell$-hypergraphs for $ell<d-1$. In this paper we give a natural structural characterization of $(d,ell)$-hypergraphs based on vertex cuts. This characterization leads to a polynomial-time recognition algorithm that decides for a given $dchooseell$-hypergraph whether or not it is a $(d,ell)$-hypergraph and that computes a representation if existing. We assume that the dimension $d$ is constant and that the partitioning of the vertex set is prescribed.

This page was built for publication: Hypergraph Representation via Axis-Aligned Point-Subspace Cover

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6384033)