PG Seminar (CSE-BUET): Hardness and Approximation Results for Extending Unique Neighborhood Networks:

Abstract: A graph G is called a unique neighborhood network (UNN) if it does not contain any vertex whose neighborhood is a subset of the neighborhood of another vertex in G. UNNs are used to model peer-authentication problems in communication networks and quantum cryptography. A natural problem in this context is to extend an existing UNN by adding a new vertex.
In this talk we will present our results on the minimum-cost UNN extension problem, where the input is a UNN G and the goal is to add a new vertex u to G by making u adjacent to a minimum set of vertices such that the unique neighborhood property is preserved. Here the cost is the number of edges added to u. In practice, this can be seen as inserting a new user into a network that is already modeled as a UNN, and the goal is to restore the UNN property with minimum cost. We propose a polynomial-time O(logn)-approximation for the problem and a linear-time algorithm for bounded-treewidth graphs. In contrast, we show that the minimum-cost UNN extension problem cannot be approximated within a factor of o(logn) in polynomial time unless P=NP. As a byproduct, we obtain a similar hardness of approximation for the minimum-cost UNN completion problem that seeks to minimize the number of edge insertions to transform a graph into a UNN. 

Student: Siam Habib (Std No. 0422052126)

Supervisor: Dr. Sadia Sharmin

Date and Time: 04-April-2026 (2:30 PM - 3:15 PM)

Venue: Graduate Seminar Room

 

Posted on: [2026-04-04 14:30:27]