A Complexity Analysis of the c-Closed Vertex Deletion Problem

Lisa Lehner, Christian Komusiewicz, Luca Pascal Staus · 2025

Read A Complexity Analysis of the c-Closed Vertex Deletion Problem by Lisa Lehner, Christian Komusiewicz, Luca Pascal Staus (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-2511-13301.txt.

Introduction

Lisa Lehner, Christian Komusiewicz, and Luca Pascal Staus analyze how hard it is to delete few vertices so a graph becomes c-closed. A graph earns that label when any two non-neighbors share at most c minus one common neighbors. The question is which graphs can be fixed by removing at most k vertices.

Among their findings is NP-hardness even for bipartite graphs with bounded degree, plus upper and lower bounds on kernel size for the parameter k. They add a new parameter based on bad pairs and give a kernel for it. Special graph classes fare better: unit interval graphs allow a fast exact method in a stated range.

Catalog record

CREATORLisa Lehner, Christian Komusiewicz, Luca Pascal Staus
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-13301

Browse the full library · About the Tower of Babel

Full text

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

A Complexity Analysis of the c-Closed Vertex Deletion Problem Lisa Lehner, Christian Komusiewicz, Luca Pascal Staus Abstract A graph is c c -closed when every pair of nonadjacent vertices has at most c − 1 c-1 common neighbors. In c c -Closed Vertex Deletion , the input is a graph G G and an integer k k and we ask whether G G can be transformed into a c c -closed graph by deleting at most k k vertices. We study the classic and parameterized complexity of c c -Closed Vertex Deletion . We obtain, for example, NP-hardness for the case that G G is bipartite with bounded maximum degree. We also show upper and lower bounds on the size of problem kernels for the parameter k k and introduce a new parameter, the number x x of vertices in bad pairs , for which we show a problem kernel of size OPEN 𝒪 ⁡ ( x 3 + x 2 ⋅ c ) ) \mathcal{O}(x^{3}+x^{2}\cdot c)) . Here, a pair of nonadjacent vertices is bad if they have at least c c common neighbors. Finally, we show that c c -Closed Vertex Deletion can be solved in polynomial time on unit interval graphs with depth at most c + 1 c+1 and that it is fixed-parameter tractable with respect to the neighborhood diversity of G G . 1 Introduction One of the most striking features of social networks is that they tend to show a high degree of triadic closure . This is the phenomenon that two agents which both interact with the same third agent are likely to interact directly, too. There are different ways to quantify this observation. For example, one can observe that social networks have high clustering coefficients, meaning that a large fraction of all connected vertex triples are triangles. A further formal definition capturing triadic closure is graph closure , introduced by Fox et al. [ 4 ] . Here, a network is called c -closed if all pairs of vertices with at least c common neighbors are adjacent and the closure of a network is the smallest number c such that the network is c -closed. The hypothesis driven by the triadic closure phenomenon is now that networks should have a relatively small closure number and this is indeed the case for real-world data [ 4 , 12 ] . Apart from giving further evidence to confirm theories about the mechanisms that underly the creation of real-world networks, this observation has consequences for the development of algorithms for real-world networks: Many hard computational problems are fixed-parameter tractable when parameterized by c or by combinations of c and other parameters. Informally, this means that these problems can be solved (more) efficiently when the input networks have a small closure number. For example, the enumeration of maximal cliques is fixed-parameter tractable with respect to the closure number c [ 4 ] . More precisely, all maximal cliques can be enumerated in 3^{c/3}\cdot n^{\mathcal{O}(1)} time, where n denotes the number of vertices in the graph. This result has been extended to the enumeration of different types of near-cliques [ 1 , 9 ] . Further algorithmic applications of c -closure were given for variants of Dominating Set [ 6 , 8 , 9 ] , Independent Set [ 8 , 9 ] , and Vertex Cover [ 7 , 10 ] and for problems related to finding certain small subgraphs [ 11 ] . A drawback of c -closure is that it is defined as the maximum of the sizes of common neighborhoods of nonadjacent vertices (plus one) which makes it sensitive to local changes: all it takes to drastically increase the c -closure of a graph is the absence of one edge between two vertices with many common neighbors. Ideally, we would like to obtain more robust positive algorithmic results that hold not only for c -closed graphs but also for those graphs which are almost c -closed. We follow the natural way of quantifying this by counting the number k of vertex deletions that are necessary to obtain a c -closed graph. Using simple arguments, one can show that positive results for Independent Set and Clique can be extended from c -closed graphs to almost c -closed graphs. Proposition 1 Let G=(V,E) be a graph and S a size- k vertex set in G such that G-S is c -closed. Then, we can (1) enumerate all maximal cliques of G in 2^{k}\cdot(3^{c/3})\cdot n^{\mathcal{O}(1)} time, and (2) determine in 2^{k}\cdot f(\ell+c)\cdot n^{\mathcal{O}(1)} time whether G contains an independent set of size at least \ell . Proof To determine whether G contains an independent set I on \ell vertices, we use the following known algorithm which can be formulated for vertex deletion sets S to any hereditary graph class for which independent sets can be found efficiently. Branch into all cases for S^{\prime}\coloneqq S\cap I . In each branch, first check whether S^{\prime} is an independent set. If this is the case, then delete all vertices from G-S that are adjacent to S^{\prime} (as they cannot be contained in an independent set that includes S^{\prime} ) and determine whether the resulting graph has an independent set of size \ell-|S^{\prime}| . Since the resulting graph is c -closed, this can be done in f(\ell+c)\cdot n^{\mathcal{O}(1)} time [ 8 ] . Since S has size k , we consider altogether 2^{k} cases for S^{\prime} which gives the claimed running time. To enumerate all maximal cliques of G proceed as follows. For each subset S^{\prime} of S , enumerate all maximal cliques K such that K\cap S=S^{\prime} . To do this, delete from G-S all vertices that are not adjacent to all vertices of S^{\prime} . Then enumerate all maximal cliques in the resulting graph. Since this graph is c -closed, this enumeration can be done in 3^{c/3}\cdot n^{\mathcal{O}(1)} time. For each enumerated clique K^{\prime} we check in polynomial time whether S^{\prime}\cup K^{\prime} is a maximal clique in G and output S^{\prime}\cup K^{\prime} if this is the case. The running time bound now follows from the fact that 2^{k} cases for S^{\prime} are considered. The correctness follows from the fact that only maximal cliques are output and that each maximal clique K is output when the branch S^{\prime}=K\cap S is considered. ∎ Hence, it may be worthwhile to find out whether a graph G is almost c -closed and to identify the respective vertex deletion set S in that case. Motivated by this, we investigate the complexity of the corresponding decision problem. c -Closed Vertex Deletion ( c -CVD ) Input: An undirected graph G=(V,E) and a positive integer k . Question: Is there a set S\subseteq V with |S|\leq k such that G-S is c -closed? Unless mentioned otherwise, throughout the paper we assume that c is constant. Known Results and Further Related Work. Since being c -closed is hereditary, c -CVD is NP-hard for every fixed value of c [ 14 ] . Assuming the exponential time hypothesis (ETH), one cannot even solve c -CVD in 2^{o(n+m)} time, where m is the number of edges in the graph [ 13 ] . The case c=1 is equivalent

Read the complete text