Realizing Graphs with Cut Constraints

Abstract

Given a finite non-decreasing sequence $d=(d_1,\dots ,d_n)$ of natural numbers, the Graph Realization problem asks whether $d$ is a graphic sequence, i.e., there exists a labeled simple graph such that $(d_1,\dots ,d_n)$ is the degree sequence of this graph. Such a problem can be solved in polynomial time due to the Erdős and Gallai characterization of graphic sequences. Since vertex degree is the size of a trivial edge cut, we consider a natural generalization of Graph Realization, where we are given a finite sequence $d=(d_1,\dots ,d_n)$ of natural numbers (representing the trivial edge cut sizes) and a list of nontrivial cut constraints $\mathcal{L}$ composed of pairs $(S_j,{\ell }_j)$ where $S_j\subset \{v_1,\dots ,v_n\}$, and ${\ell }_j$ is a natural number. In such a problem, we are asked whether there is a simple graph with vertex set $V=\{v_1,\dots ,v_n\}$ such that $v_i$ has degree $d_i$ and $\partial (S_j)$ is an edge cut of size ${\ell }_j$, for each $(S_j,{\ell }_j)\in \mathcal{L}$. We show that such a problem is polynomial-time solvable whenever each $S_j$ has size at most three. Conversely, assuming P $\ne$ NP, we prove that it cannot be solved in polynomial time when $\mathcal{L}$ contains pairs with sets of size four, and our hardness result holds even assuming that each $d_i$ of $d$ equals $1$.