2 papers
cs.DS2019
Subgraph Isomorphism on Graph Classes that Exclude a Substructure
Hans L. Bodlaender, Tesshu Hanaka, Yasuaki Kobayashi +4
We study Subgraph Isomorphism on graph classes defined by a fixed forbidden graph. Although there are several ways for forbidding a graph, we observe that it is reasonable to focus…
cs.DS2019
Independent Set Reconfiguration Parameterized by Modular-Width
Rémy Belmonte, Tesshu Hanaka, Michael Lampis +2
Independent Set Reconfiguration is one of the most well-studied problems in the setting of combinatorial reconfiguration. It is known that the problem is PSPACE-complete even for g…