Minimum Weighted 1-Maximal Total Nearly Perfect Set Problem

Şakir Buğra Kollar, Department of Industrial Engineering, METU

Abstract

Given an undirected graph G=(V,E), a subset of the nodes S is called a total nearly perfect set (TNPS) if every node in G has at most element of S in its open neighborhood. A TNPS S of size k is said to be 1-maximal if it is not a proper subset of any other TNPS of size k+1. In a paper written by Hedetniemi [Unsolved Algorithmic Problems on Trees, AKCE International Journal of Graphs and Combinatorics, 3:1, 1-37 (2006)], the author asks for an algorithm to compute the minimum size of a 1-maximal TNPS in trees. We study the more general problem of finding a 1-maximal TNPS of minimum weight in a node-weighted graph and obtain some structural and algorithmic results for general graphs with additional results specifically for trees.

This is joint work Melodi Cebesoy and Mustafa Kemal Tural.

Şakir Buğra Kollar is currently a master’s student in the Industrial Engineering Department at Middle East Technical University where he has been working as a research assistant since February 2023. He received his BS degree from the same department in 2022.

Venue

Friday, March 31, 2023, 4.00 pm - Zoom