Realizing Graphs with Cut Constraints

Vítor Gomes Chagas, Samuel Plaça de Paula, Greis Yvet Oropeza Quesquén, Lucas de Oliveira Silva, Uéverton dos Santos Souza · 2025

Read Realizing Graphs with Cut Constraints by Vítor Gomes Chagas, Samuel Plaça de Paula, Greis Yvet Oropeza Quesquén, Lucas de Oliveira Silva, Uéverton dos Santos Souza (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-09358.txt.

Introduction

Lucas de Oliveira Silva and four co-authors present a 2025 study of a harder version of a classic graph problem. The classic problem asks whether a list of numbers can be the connection counts, or degrees, of a graph's corners. That version is solvable fast. The new version adds cut constraints: for chosen groups of corners, the number of edges leaving the group must match a given size, on top of the degree list.

The authors prove the problem stays fast when every constrained group has at most three corners. With groups of four, it becomes as hard as problems believed to have no fast solution. The hardness holds even when every corner needs just one edge. The result draws a sharp line between the easy and hard forms of the problem.

Catalog record

CREATORVítor Gomes Chagas, Samuel Plaça de Paula, Greis Yvet Oropeza Quesquén, Lucas de Oliveira Silva, Uéverton dos Santos Souza
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-09358

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Realizing Graphs with Cut Constraints Vítor Gomes Chagas, Samuel Plaça de Paula, Greis Yvet Oropeza Quesquén, Lucas de Oliveira Silva, Uéverton dos Santos Souza Abstract Given a finite non-decreasing sequence d = ( d 1 , … , d n ) \texttt{d}=(d_{1},\ldots,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 , … , d n ) (d_{1},\ldots,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 , … , d n ) \texttt{d}=(d_{1},\ldots,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 , ℓ j ) (S_{j},\ell_{j}) where S j ⊂ { v 1 , … , v n } S_{j}\subset\{v_{1},\ldots,v_{n}\} , and ℓ j \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 , … , v n } V=\{v_{1},\ldots,v_{n}\} such that v i v_{i} has degree d i d_{i} and ∂ ( S j ) \partial(S_{j}) is an edge cut of size ℓ j \ell_{j} , for each ( S j , ℓ j ) ∈ ℒ (S_{j},\ell_{j})\in\mathcal{L} . We show that such a problem is polynomial-time solvable whenever each S j S_{j} has size at most three. Conversely, assuming P ≠ \neq 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 d_{i} of d equals 1 1 . 1 Introduction Graph realization is a fundamental combinatorial problem in the field of Graph Theory, and its studies have fostered interest in and understanding of the discrete structure of graphs. Nowadays, graph realization is a topic commonly covered in introductory Graph Theory courses, providing those new to the world of graphs with many insights into their combinatorial properties. The Handshaking Lemma, for example, is usually one of the first statements that beginners come across when they begin studying graphs. Although simple to understand, it is the gateway to a world of more intriguing graph-related questions. By observing that the sum of the degrees of all vertices is equal to twice the number of edges in the graph, it follows that not every sequence of n natural numbers can be the degree sequence of some graph with n vertices, and it becomes natural to ask when a sequence of n natural numbers admits a graph with n vertices whose degree sequence corresponds to the given sequence; the topic related to such a question is called graph realization . Given a sequence d of n natural numbers that satisfy the Handshaking Lemma (i.e., the sum of its values is even), it is a simple exercise to verify that it is possible to construct a multigraph (parallel edges and loops are allowed) whose degree sequence corresponds to d . However, this question becomes more intriguing when the goal is to realize a simple graph where parallel edges and loops are not allowed. A non-decreasing sequence \texttt{d}=(d_{1},\ldots,d_{n}) of natural numbers is said to be graphic if it is realizable by a simple graph, that is, if there exists a labeled simple graph G with n vertices such that d is its degree sequence. Formally, the classical Graph Realization problem is stated as follows: Input: A non-decreasing sequence \texttt{d}=(d_{1},\dots,d_{n}) of natural numbers. Question: Is d a graphic sequence? Graph Realization In 1960, Erdős and Gallai provided necessary and sufficient conditions for a sequence of non-negative integers to be graphic, proving the following theorem. Theorem 1.1 (Erdős and Gallai [ 15 ] ) A non-decreasing sequence \texttt{d}=(d_{1},\dots,d_{n}) of natural numbers is graphic if and only if 1. \sum\limits_{i=1}^{n}d_{i} is even, and 2. \sum\limits_{i=1}^{k}d_{i}\leq k(k-1)+\sum\limits_{i=k+1}^{n}\min\{d_{i},k\} , for every 1\leq k\leq n . It is not difficult to see that the conditions presented by Erdős and Gallai are necessary. However, the sufficiency proof provided by Erdős and Gallai is quite elaborated. Several alternative proofs for this sufficiency condition have been shown since then until recently, such as Harary [ 23 ] in 1969, Berge [ 9 ] in 1973, Choudum [ 13 ] in 1986, Aigner and Triesch [ 2 ] in 1994, Tripathi and Tyagi [ 34 ] in 2008, and Tripathi, Venugopalan, and West [ 35 ] in 2010. From Theorem 1.1 , it follows that Graph Realization can solved in polynomial time. Additionally, Tripathi, Venugopalan, and West [ 35 ] presented a simple constructive proof of Theorem 1.1 that allows us to obtain the graph to be realized in \mathcal{O}(n\cdot\sum_{i=1}^{n}d_{i}) time. Furthermore, algorithms like the one provided by Havel and Hakimi [ 24 , 21 ] , which iteratively reduce the degree sequence while maintaining its realizability, also give a constructive approach to finding such graphs if one exists. Havel and Hakimi’s algorithms run in \mathcal{O}(\sum_{i=1}^{n}d_{i}) time, which is optimal. Variants of the Graph Realization problem requiring that the realizing graph belongs to a particular graph class have also been studied in the literature. Examples of already studied classes included trees [ 20 ] , Split graphs [ 22 , 11 ] , Chordal, interval, and perfect graphs [ 12 ] . Besides that, sequence pairs representing the degree sequences of a bipartition in a realizing bipartite graph were also studied in [ 10 ] . Surprisingly, the question regarding Graph Realization for the class of bipartite graphs appears to remain open for over 40 years [ 6 , 33 ] . In addition, the problem of determining whether a given sequence defines a unique realizing simple graph was studied in [ 2 , 26 , 30 ] , and Bar-Noy, Peleg, and Rawitz [ 8 ] introduced the vertex-weighted variant of Graph Realization where we are given a sequence \texttt{d}=(d_{1},d_{2},\ldots,d_{n}) representing a “weighted degree” sequence, and a vector \texttt{w}=(w_{1},w_{2},\ldots,w_{n}) representing vertex weights, and asked whether there is a graph with vertex set V=\{v_{1},v_{2},\ldots,v_{n}\} such that for each v_{i} the sum of the weights of its neighbors is equal to d_{i} . In today’s interconnected world, many fields face the challenge of structuring systems with specific connectivity requirements. For instance, in social network analysis, building a network where individuals (vertices) have a fixed number of connections (degree) is crucial for analyzing influence, community structures, and information diffusion. Similarly, urban planners confront similar issues when designing road networks, where intersections must be connected with a specific number of roads to optimize traffic flow. These examples highlight the significance of addressing connectivity challenges in various fields where specific connectivity patterns must be achieved. One of the most studied problems in this context is the realization problem that deals with degree sequences. According to Bar-Noy, Böhnlein, Peleg, and Rawitz [ 7 ] , Graph Realization and its variants have interesting applications in network design, randomized

Read the complete text