A 4/3-approximation algorithm for the Maximum Internal Spanning Tree Problem

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)131-140
Journal / PublicationJournal of Computer and System Sciences
Volume118
Online published12 Jan 2021
Publication statusPublished - Jun 2021

Abstract

In this paper, we study the Maximum Internal Spanning Tree Problem (MIST). Given an undirected simple graph G, the task for the Maximum Internal Spanning Tree problem is to find a spanning tree of G with maximum number of internal vertices. We present an approximation algorithm with performance ratio 4/3, which improves upon the best known performance ratio 3/2. Our algorithm benefits from a new observation for bounding the number of internal vertices of a spanning tree. We can also give an example to show that the performance ratio 4/3 is actually tight for this algorithm. Finally, we show that MIST is Max-SNP-hard.

Research Area(s)

  • Approximation algorithm, Maximum Internal Spanning Tree Problem, Performance ratio