Happy Set Problem on Subclasses of Co-comparability Graphs

Hiroshi Eto, Takehiro Ito, Eiji Miyano, Akira Suzuki, Yuma Tamura

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Citation (Scopus)

Abstract

In this paper, we investigate the complexity of the Maximum Happy Set problem on subclasses of co-comparability graphs. For a graph G and its vertex subset S, a vertex v∈ S is happy if all v’s neighbors in G are contained in S. Given a graph G and a non-negative integer k, Maximum Happy Set is the problem of finding a vertex subset S of G such that | S| = k and the number of happy vertices in S is maximized. In this paper, we first show that Maximum Happy Set is NP-hard even for co-bipartite graphs. We then give an algorithm for n-vertex interval graphs whose running time is O(k2n2); this improves the best known running time O(kn8) for interval graphs. We also design an algorithm for n-vertex permutation graphs whose running time is O(k3n2). These two algorithmic results provide a nice contrast to the fact that Maximum Happy Set remains NP-hard for chordal graphs, comparability graphs, and co-comparability graphs.

Original languageEnglish
Title of host publicationWALCOM
Subtitle of host publicationAlgorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Proceedings
EditorsPetra Mutzel, Md. Saidur Rahman, Slamin
PublisherSpringer Science and Business Media Deutschland GmbH
Pages149-160
Number of pages12
ISBN (Print)9783030967307
DOIs
Publication statusPublished - 2022
Event16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022 - Jember, Indonesia
Duration: 2022 Mar 242022 Mar 26

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13174 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022
Country/TerritoryIndonesia
CityJember
Period22/3/2422/3/26

Fingerprint

Dive into the research topics of 'Happy Set Problem on Subclasses of Co-comparability Graphs'. Together they form a unique fingerprint.

Cite this