Search Results

Documents authored by Nishimura, Naomi


Document
Kernelization Complexity of Solution Discovery Problems

Authors: Mario Grobler, Stephanie Maaz, Amer E. Mouawad, Naomi Nishimura, Vijayaragunathan Ramamoorthi, and Sebastian Siebertz

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)


Abstract
In the solution discovery variant of a vertex (edge) subset problem Π on graphs, we are given an initial configuration of tokens on the vertices (edges) of an input graph G together with a budget b. The question is whether we can transform this configuration into a feasible solution of Π on G with at most b modification steps. We consider the token sliding variant of the solution discovery framework, where each modification step consists of sliding a token to an adjacent vertex (edge). The framework of solution discovery was recently introduced by Fellows et al. [ECAI 2023] and for many solution discovery problems the classical as well as the parameterized complexity has been established. In this work, we study the kernelization complexity of the solution discovery variants of Vertex Cover, Independent Set, Dominating Set, Shortest Path, Matching, and Vertex Cut with respect to the parameters number of tokens k, discovery budget b, as well as structural parameters such as pathwidth.

Cite as

Mario Grobler, Stephanie Maaz, Amer E. Mouawad, Naomi Nishimura, Vijayaragunathan Ramamoorthi, and Sebastian Siebertz. Kernelization Complexity of Solution Discovery Problems. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{grobler_et_al:LIPIcs.ISAAC.2024.36,
  author =	{Grobler, Mario and Maaz, Stephanie and Mouawad, Amer E. and Nishimura, Naomi and Ramamoorthi, Vijayaragunathan and Siebertz, Sebastian},
  title =	{{Kernelization Complexity of Solution Discovery Problems}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{36:1--36:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.36},
  URN =		{urn:nbn:de:0030-drops-221630},
  doi =		{10.4230/LIPIcs.ISAAC.2024.36},
  annote =	{Keywords: solution discovery, kernelization, cut, independent set, vertex cover, dominating set}
}
Document
Reconfiguration of Graph Minors

Authors: Benjamin Moore, Naomi Nishimura, and Vijay Subramanya

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)


Abstract
Under the reconfiguration framework, we consider the various ways that a target graph H is a minor of a host graph G, where a subgraph of G can be transformed into H by means of edge contraction (replacement of both endpoints of an edge by a new vertex adjacent to any vertex adjacent to either endpoint). Equivalently, an H-model of G is a labeling of the vertices of G with the vertices of H, where the contraction of all edges between identically-labeled vertices results in a graph containing representations of all edges in H. We explore the properties of G and H that result in a connected reconfiguration graph, in which nodes represent H-models and two nodes are adjacent if their corresponding H-models differ by the label of a single vertex of G. Various operations on G or H are shown to preserve connectivity. In addition, we demonstrate properties of graphs G that result in connectivity for the target graphs K_2, K_3, and K_4, including a full characterization of graphs G that result in connectivity for K_2-models, as well as the relationship between connectivity of G and other H-models.

Cite as

Benjamin Moore, Naomi Nishimura, and Vijay Subramanya. Reconfiguration of Graph Minors. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 75:1-75:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{moore_et_al:LIPIcs.MFCS.2018.75,
  author =	{Moore, Benjamin and Nishimura, Naomi and Subramanya, Vijay},
  title =	{{Reconfiguration of Graph Minors}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{75:1--75:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.75},
  URN =		{urn:nbn:de:0030-drops-96573},
  doi =		{10.4230/LIPIcs.MFCS.2018.75},
  annote =	{Keywords: reconfiguration, graph minors, graph algorithms}
}
Document
Complete Volume
LIPIcs, Volume 89, IPEC'17, Complete Volume

Authors: Daniel Lokshtanov and Naomi Nishimura

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)


Abstract
LIPIcs, Volume 89, IPEC'17, Complete Volume

Cite as

12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@Proceedings{lokshtanov_et_al:LIPIcs.IPEC.2017,
  title =	{{LIPIcs, Volume 89, IPEC'17, Complete Volume}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017},
  URN =		{urn:nbn:de:0030-drops-86166},
  doi =		{10.4230/LIPIcs.IPEC.2017},
  annote =	{Keywords: Complexity Measures and Classes, Analysis of Algorithms and Problem Complexity, Discrete Mathematics}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Daniel Lokshtanov and Naomi Nishimura

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)


Abstract
Front Matter, Table of Contents, Preface, Conference Organization

Cite as

12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{lokshtanov_et_al:LIPIcs.IPEC.2017.0,
  author =	{Lokshtanov, Daniel and Nishimura, Naomi},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{0:i--0:xii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.0},
  URN =		{urn:nbn:de:0030-drops-85437},
  doi =		{10.4230/LIPIcs.IPEC.2017.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
On Directed Covering and Domination Problems

Authors: Tesshu Hanaka, Naomi Nishimura, and Hirotaka Ono

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)


Abstract
In this paper, we study covering and domination problems on directed graphs. Although undirected Vertex Cover and Edge Dominating Set are well-studied classical graph problems, the directed versions have not been studied much due to the lack of clear definitions. We give natural definitions for Directed r-In (Out) Vertex Cover and Directed (p,q)-Edge Dominating Set as directed generations of Vertex Cover and Edge Dominating Set. For these problems, we show that (1) Directed r-In (Out) Vertex Cover and Directed (p,q)-Edge Dominating Set are NP-complete on planar directed acyclic graphs except when r=1 or (p,q)=(0,0), (2) if r>=2, Directed r-In (Out) Vertex Cover is W[2]-hard and (c*ln k)-inapproximable on directed acyclic graphs, (3) if either p or q is greater than 1, Directed (p,q)-Edge Dominating Set is W[2]-hard and (c*ln k)-inapproximable on directed acyclic graphs, (4) all problems can be solved in polynomial time on trees, and (5) Directed (0,1),(1,0),(1,1)-Edge Dominating Set are fixed-parameter tractable in general graphs. The first result implies that (directed) r-Dominating Set on directed line graphs is NP-complete even if r=1.

Cite as

Tesshu Hanaka, Naomi Nishimura, and Hirotaka Ono. On Directed Covering and Domination Problems. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 45:1-45:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.ISAAC.2017.45,
  author =	{Hanaka, Tesshu and Nishimura, Naomi and Ono, Hirotaka},
  title =	{{On  Directed Covering and Domination Problems}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{45:1--45:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.45},
  URN =		{urn:nbn:de:0030-drops-82460},
  doi =		{10.4230/LIPIcs.ISAAC.2017.45},
  annote =	{Keywords: directed graph, vertex cover, dominating set, edge dominating set, fixed-parameter algorithms}
}
Document
Fixed Parameter Algorithms (Dagstuhl Seminar 03311)

Authors: Michael R. Fellows, Michael Hallett, Rold Niedermeier, and Naomi Nishimura

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

Michael R. Fellows, Michael Hallett, Rold Niedermeier, and Naomi Nishimura. Fixed Parameter Algorithms (Dagstuhl Seminar 03311). Dagstuhl Seminar Report 388, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)


Copy BibTex To Clipboard

@TechReport{fellows_et_al:DagSemRep.388,
  author =	{Fellows, Michael R. and Hallett, Michael and Niedermeier, Rold and Nishimura, Naomi},
  title =	{{Fixed Parameter Algorithms (Dagstuhl Seminar 03311)}},
  pages =	{1--7},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{388},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.388},
  URN =		{urn:nbn:de:0030-drops-152681},
  doi =		{10.4230/DagSemRep.388},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail