Leírás
Parametrized complexity is a popular research topic in algorithmic graph theory. One can also consider parametrized complexity of degree sequence problems. While deciding if there is a simple graph realization of a degree sequence is easy, deciding if there is a 3-uniform hypergraph realization of a degree sequence is NP-complete. Therefore, it is natural to seek special classes of degree sequences for which the 3-uniform hypergraphicality problem remains easy. Our main result here is the following dichotomy theorem. Given $0<c_1\le c_2 < 1$, the parameterized 3-uniform Hypergraphic Degree Sequence problem, $\textsc{3uni-HDS}_{c_1,c_2}$, considers degree sequences $D$ of length $n$ such that all degrees are between $c_1 {n-1 \choose 2}$ and $c_2 {n-1\choose 2}$ and it asks if there is a 3-uniform hypergraph with degree sequence $D$. We prove that for any $0<c_2< 1$, there exists a unique, polynomial-time computable $c_1^*$ with the following properties. For any $ c_1\in (c_1^*,c_2]$, $\textsc{3uni-HDS}_{c_1,c_2}$ can be solved in linear time. In fact, for any $c_1\in (c_1^*,c_2]$ there exists an easy-to-compute $n_0$ such that any degree sequence $D$ of length $n\ge n_0$ and all degrees between $c_1 {n-1\choose 2}$ and $c_2 {n-1\choose 2}$ has a 3-uniform hypergraph realization if and only if the sum of the degrees can be divided by $3$. Further, $n_0$ grows polynomially with the inverse of $c_1-c_1^*$. On the other hand, we prove that for all $c_1<c_1^*$, $\textsc{3uni-HDS}_{c_1,c_2}$ is NP-complete. That is, there is a phase transition in the complexity of the hypergraphicality problem at $c_1^*$, going from linear time to NP-complete.
Analogously, we can define linearly bounded simple graph degree sequence classes, that is, degree sequence classes in which each degree sequence of length $n$ has degrees between $c_1 (n-1)$ and $c_2 (n-1)$. We developed constraints for $c_1$ and $c_2$ such that the so-obtained degree sequence classes are always graphic (fully graphic). Our main result here is that these degree sequence classes essentially coincide with the P-stable degree sequence classes. In a nutshell, stability of a degree sequence tells how much the number of realizations of the degree sequence can be changed by changing the degree sequence by 2 in the $L_1$ measure. P-stability means a polynomial factor. Our phase transition result here is that there is a jump of the stability from a fixed degree polynomial factor to an exponential factor at the critical minimum degree bound. We conjecture further phase transitions inside the P-stable regions, where the degree of the polynomials jump at the critical values. We are still seeking the algorithmic/complexity consequences of these phase transitions.
Joint work with Sara Logsdon, Arya Maheswari, Angelina Zhang, Péter L. Erdős and Lajos Soukup.
References
Logsdon, S., Maheswari, A., Miklós, I., Zhang, A. (2024) A dichotomy theorem on the complexity of 3-uniform hypergraphic degree sequence graphicality. https://arxiv.org/abs/2411.19049
Erdős, P.L., Miklós, I., Soukup, L. (2025) Fully graphic degree sequences and P-stable degree sequences, Advances in Applied Mathematics, 163A:102805.
ZOOOOOOOOOOM
https://zoom.us/j/2961946869?omn=93408758990