Minimum Weighted 1-Maximal Total Nearly Perfect Set Problem

Melodi Cebesoy Uslu

Given an undirected graph G=(V,E), a subset S of the nodes is called a total nearly perfect set
(TNPS) if every node in G has at most one neighbor in S. 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 and Haynes [Unsolved Algorithmic Problems on Trees, AKCE International Journal
of Graphs and Combinatorics, 3:1, 1-37 (2006)], the authors ask 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 Şakir Buğra Kollar and Mustafa Kemal Tural.

Short Bio

Melodi Cebesoy Uslu graduated from the Industrial Engineering Department of TED University in
2017 and earned her master’s degree from the same department at Hacettepe University. She is
currently a PhD student in the Industrial Engineering Department at METU and works as a research
assistant at Hacettepe University. Her main research interests are multiple criteria decision making
and multi-objective robust optimization.

Venue

Friday, March 21^st, 2025, 4:00 pm