9 papers · 1 filter
Parameterized Complexity of Odd Domination and its Generalization
Toranosuke Kokai, Rin Saito, Tatsuhiro Suga +2
In the \textsc{Odd Domination} problem, given a graph and a positive integer , the task is to determine whether there exists a vertex subset of such that the closed…
On (In)approximability of MaxMin Independent Set Reconfiguration
Hung P. Hoang, Naoto Ohsaka, Rin Saito +1
In the Independent Set Reconfiguration problem under the Token Addition/Removal rule, given a graph and two independent sets and of , we want to transform into $…
Finding Shortest Reconfiguration Sequences on Independent Set Polytopes
Jean Cardinal, Kevin Mann, Akira Suzuki +3
We initiate the study of the shortest reconfiguration problem for independent sets under the adjacency relation derived from the independent set polytope. Given a graph and two ind…
Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
Rin Saito, Anouk Sommer, Tatsuhiro Suga +2
In the solution discovery problem for a search problem on graphs, we are given an initial placement of tokens on the vertices of a graph and asked whether this placement can be…
Spanning Trees with a Small Vertex Cover: the Complexity on Specific Graph Classes
Toranosuke Kokai, Akira Suzuki, Takahiro Suzuki +2
In the context of algorithm theory, various studies have been conducted on spanning trees with desirable properties. In this paper, we consider the \textsc{Minimum Cover Spanning T…
Coloring Reconfiguration under Color Swapping
Janosch Fuchs, Rin Saito, Tatsuhiro Suga +2
In the \textsc{Coloring Reconfiguration} problem, we are given two proper -colorings of a graph and asked to decide whether one can be transformed into the other by repeatedly a…
Changing Induced Subgraph Isomorphisms Under Extended Reconfiguration Rules
Tatsuhiro Suga, Akira Suzuki, Yuma Tamura +1
In a reconfiguration problem, we are given two feasible solutions of a combinatorial problem and our goal is to determine whether it is possible to reconfigure one into the other,…
Finding Induced Subgraphs from Graphs with Small Mim-Width
Yota Otachi, Akira Suzuki, Yuma Tamura
In the last decade, algorithmic frameworks based on a structural graph parameter called mim-width have been developed to solve generally NP-hard problems. However, it is known that…
On the complexity of list -packing for sparse graph classes
Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi +5
The problem of packing as many subgraphs isomorphic to as possible in a graph for a class of graphs is well studied in the literature. Both vertex-d…