The maximum happy induced subgraph problem: bounds and algorithms

Lewis, R. ORCID: https://orcid.org/0000-0003-1046-811X, Thiruvady, D. and Morgan, K. 2021. The maximum happy induced subgraph problem: bounds and algorithms. Computers and Operations Research 126 , 105114. 10.1016/j.cor.2020.105114

Preview

PDF - Accepted Post-Print Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (1MB) | Preview

Abstract

In this paper we consider a combinatorial optimisation problem that takes as input a graph in which some of the vertices have been preassigned to colours. The aim is to then identify the largest induced subgraph in which all remaining vertices are able to assume the same colour as all of their neighbours. This problem shares similarities with the graph colouring problem, vertex cut problems, and the maximum happy vertices problem. It is NP-hard in general. In this paper we derive a number of upper and lower bounds and also show how certain problem instances can be broken up into smaller subproblems. We also propose one exact and two heuristic algorithms for this problem and use these to investigate the factors that make some problem instances more difficult to solve than others.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Publisher:	Elsevier
ISSN:	0305-0548
Date of First Compliant Deposit:	15 October 2020
Date of Acceptance:	29 September 2020
Last Modified:	02 Dec 2024 08:00
URI:	https://orca.cardiff.ac.uk/id/eprint/135626

Citation Data

Cited 1 time in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item