Reconfiguration of Regular Induced Subgraphs

Hiroshi Eto, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi, Kunihiro Wasa

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

Abstract

We study the problem of checking the existence of a step-by-step transformation of d-regular induced subgraphs in a graph, where d≥ 0 and each step in the transformation must follow a fixed reconfiguration rule. Our problem for d= 0 is equivalent to Independent Set Reconfiguration, which is one of the most well-studied reconfiguration problems. In this paper, we systematically investigate the complexity of the problem, in particular, on chordal graphs and bipartite graphs. Our results give interesting contrasts to known ones for Independent Set Reconfiguration.

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
Pages35-46
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

Keywords

  • Combinatorial reconfiguration
  • Computational complexity
  • Regular induced subgraph

Fingerprint

Dive into the research topics of 'Reconfiguration of Regular Induced Subgraphs'. Together they form a unique fingerprint.

Cite this