Search Results

Documents authored by Hanaka, Tesshu

Document
DOI: 10.4230/LIPIcs.MFCS.2024.58
Parameterized Vertex Integrity Revisited

Authors: Tesshu Hanaka, Michael Lampis, Manolis Vasilakis, and Kanae Yoshiwatari

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Vertex integrity is a graph parameter that measures the connectivity of a graph. Informally, its meaning is that a graph has small vertex integrity if it has a small separator whose removal disconnects the graph into connected components which are themselves also small. Graphs with low vertex integrity are very structured; this renders many hard problems tractable and has recently attracted interest in this notion from the parameterized complexity community. In this paper we revisit the NP-complete problem of computing the vertex integrity of a given graph from the point of view of structural parameterizations. We present a number of new results, which also answer some recently posed open questions from the literature. Specifically, we show that unweighted vertex integrity is W[1]-hard parameterized by treedepth; we show that the problem remains W[1]-hard if we parameterize by feedback edge set size (via a reduction from a Bin Packing variant which may be of independent interest); and complementing this we show that the problem is FPT by max-leaf number. Furthermore, for weighted vertex integrity, we show that the problem admits a single-exponential FPT algorithm parameterized by vertex cover or by modular width, the latter result improving upon a previous algorithm which required weights to be polynomially bounded.
Cite as

Tesshu Hanaka, Michael Lampis, Manolis Vasilakis, and Kanae Yoshiwatari. Parameterized Vertex Integrity Revisited. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.MFCS.2024.58,
  author =	{Hanaka, Tesshu and Lampis, Michael and Vasilakis, Manolis and Yoshiwatari, Kanae},
  title =	{{Parameterized Vertex Integrity Revisited}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{58:1--58:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.58},
  URN =		{urn:nbn:de:0030-drops-206141},
  doi =		{10.4230/LIPIcs.MFCS.2024.58},
  annote =	{Keywords: Parameterized Complexity, Treedepth, Vertex Integrity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.37
Shortest Beer Path Queries Based on Graph Decomposition

Authors: Tesshu Hanaka, Hirotaka Ono, Kunihiko Sadakane, and Kosuke Sugiyama

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
Given a directed edge-weighted graph G = (V, E) with beer vertices B ⊆ V, a beer path between two vertices u and v is a path between u and v that visits at least one beer vertex in B, and the beer distance between two vertices is the shortest length of beer paths. We consider indexing problems on beer paths, that is, a graph is given a priori, and we construct some data structures (called indexes) for the graph. Then later, we are given two vertices, and we find the beer distance or beer path between them using the data structure. For such a scheme, efficient algorithms using indexes for the beer distance and beer path queries have been proposed for outerplanar graphs and interval graphs. For example, Bacic et al. (2021) present indexes with size O(n) for outerplanar graphs and an algorithm using them that answers the beer distance between given two vertices in O(α(n)) time, where α(⋅) is the inverse Ackermann function; the performance is shown to be optimal. This paper proposes indexing data structures and algorithms for beer path queries on general graphs based on two types of graph decomposition: the tree decomposition and the triconnected component decomposition. We propose indexes with size O(m+nr²) based on the triconnected component decomposition, where r is the size of the largest triconnected component. For a given query u,v ∈ V, our algorithm using the indexes can output the beer distance in query time O(α(m)). In particular, our indexing data structures and algorithms achieve the optimal performance (the space and the query time) for series-parallel graphs, which is a wider class of outerplanar graphs.
Cite as

Tesshu Hanaka, Hirotaka Ono, Kunihiko Sadakane, and Kosuke Sugiyama. Shortest Beer Path Queries Based on Graph Decomposition. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.ISAAC.2023.37,
  author =	{Hanaka, Tesshu and Ono, Hirotaka and Sadakane, Kunihiko and Sugiyama, Kosuke},
  title =	{{Shortest Beer Path Queries Based on Graph Decomposition}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{37:1--37:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.37},
  URN =		{urn:nbn:de:0030-drops-193397},
  doi =		{10.4230/LIPIcs.ISAAC.2023.37},
  annote =	{Keywords: graph algorithm, shortest path problem, SPQR tree}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.64
Hedonic Games and Treewidth Revisited

Authors: Tesshu Hanaka and Michael Lampis

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We revisit the complexity of the well-studied notion of Additively Separable Hedonic Games (ASHGs). Such games model a basic clustering or coalition formation scenario in which selfish agents are represented by the vertices of an edge-weighted digraph G = (V,E), and the weight of an arc uv denotes the utility u gains by being in the same coalition as v. We focus on (arguably) the most basic stability question about such a game: given a graph, does a Nash stable solution exist and can we find it efficiently? We study the (parameterized) complexity of ASHG stability when the underlying graph has treewidth t and maximum degree Δ. The current best FPT algorithm for this case was claimed by Peters [AAAI 2016], with time complexity roughly 2^{O(Δ⁵t)}. We present an algorithm with parameter dependence (Δ t)^{O(Δ t)}, significantly improving upon the parameter dependence on Δ given by Peters, albeit with a slightly worse dependence on t. Our main result is that this slight performance deterioration with respect to t is actually completely justified: we observe that the previously claimed algorithm is incorrect, and that in fact no algorithm can achieve dependence t^{o(t)} for bounded-degree graphs, unless the ETH fails. This, together with corresponding bounds we provide on the dependence on Δ and the joint parameter establishes that our algorithm is essentially optimal for both parameters, under the ETH. We then revisit the parameterization by treewidth alone and resolve a question also posed by Peters by showing that Nash Stability remains strongly NP-hard on stars under additive preferences. Nevertheless, we also discover an island of mild tractability: we show that Connected Nash Stability is solvable in pseudo-polynomial time for constant t, though with an XP dependence on t which, as we establish, cannot be avoided.
Cite as

Tesshu Hanaka and Michael Lampis. Hedonic Games and Treewidth Revisited. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.ESA.2022.64,
  author =	{Hanaka, Tesshu and Lampis, Michael},
  title =	{{Hedonic Games and Treewidth Revisited}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.64},
  URN =		{urn:nbn:de:0030-drops-170025},
  doi =		{10.4230/LIPIcs.ESA.2022.64},
  annote =	{Keywords: Hedonic Games, Nash Equilibrium, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.3
(In)approximability of Maximum Minimal FVS

Authors: Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, and Nikolaos Melissinos

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
We study the approximability of the NP-complete Maximum Minimal Feedback Vertex Set problem. Informally, this natural problem seems to lie in an intermediate space between two more well-studied problems of this type: Maximum Minimal Vertex Cover, for which the best achievable approximation ratio is √n, and Upper Dominating Set, which does not admit any n^{1-ε} approximation. We confirm and quantify this intuition by showing the first non-trivial polynomial time approximation for Max Min FVS with a ratio of O(n^{2/3}), as well as a matching hardness of approximation bound of n^{2/3-ε}, improving the previous known hardness of n^{1/2-ε}. Along the way, we also obtain an O(Δ)-approximation and show that this is asymptotically best possible, and we improve the bound for which the problem is NP-hard from Δ ≥ 9 to Δ ≥ 6. Having settled the problem’s approximability in polynomial time, we move to the context of super-polynomial time. We devise a generalization of our approximation algorithm which, for any desired approximation ratio r, produces an r-approximate solution in time n^O(n/r^{3/2}). This time-approximation trade-off is essentially tight: we show that under the ETH, for any ratio r and ε > 0, no algorithm can r-approximate this problem in time n^{O((n/r^{3/2})^{1-ε})}, hence we precisely characterize the approximability of the problem for the whole spectrum between polynomial and sub-exponential time, up to an arbitrarily small constant in the second exponent.
Cite as

Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, and Nikolaos Melissinos. (In)approximability of Maximum Minimal FVS. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dublois_et_al:LIPIcs.ISAAC.2020.3,
  author =	{Dublois, Louis and Hanaka, Tesshu and Khosravian Ghadikolaei, Mehdi and Lampis, Michael and Melissinos, Nikolaos},
  title =	{{(In)approximability of Maximum Minimal FVS}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.3},
  URN =		{urn:nbn:de:0030-drops-133477},
  doi =		{10.4230/LIPIcs.ISAAC.2020.3},
  annote =	{Keywords: Approximation Algorithms, ETH, Inapproximability}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.13
Parameterized Algorithms for Maximum Cut with Connectivity Constraints

Authors: Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, and Yusuke Kobayashi

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
We study two variants of Maximum Cut, which we call Connected Maximum Cut and Maximum Minimal Cut, in this paper. In these problems, given an unweighted graph, the goal is to compute a maximum cut satisfying some connectivity requirements. Both problems are known to be NP-complete even on planar graphs whereas Maximum Cut on planar graphs is solvable in polynomial time. We first show that these problems are NP-complete even on planar bipartite graphs and split graphs. Then we give parameterized algorithms using graph parameters such as clique-width, tree-width, and twin-cover number. Finally, we obtain FPT algorithms with respect to the solution size.
Cite as

Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, and Yusuke Kobayashi. Parameterized Algorithms for Maximum Cut with Connectivity Constraints. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{eto_et_al:LIPIcs.IPEC.2019.13,
  author =	{Eto, Hiroshi and Hanaka, Tesshu and Kobayashi, Yasuaki and Kobayashi, Yusuke},
  title =	{{Parameterized Algorithms for Maximum Cut with Connectivity Constraints}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.13},
  URN =		{urn:nbn:de:0030-drops-114747},
  doi =		{10.4230/LIPIcs.IPEC.2019.13},
  annote =	{Keywords: Maximum cut, Parameterized algorithm, NP-hardness, Graph parameter}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.67
New Results on Directed Edge Dominating Set

Authors: Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Eun Jung Kim, and Michael Lampis

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

Abstract
We study a family of generalizations of Edge Dominating Set on directed graphs called Directed (p,q)-Edge Dominating Set. In this problem an arc (u,v) is said to dominate itself, as well as all arcs which are at distance at most q from v, or at distance at most p to u. First, we give significantly improved FPT algorithms for the two most important cases of the problem, (0,1)-dEDS and (1,1)-dEDS (that correspond to versions of Dominating Set on line graphs), as well as polynomial kernels. We also improve the best-known approximation for these cases from logarithmic to constant. In addition, we show that (p,q)-dEDS is FPT parameterized by p+q+tw, but W-hard parameterized just by tw, where tw is the treewidth of the underlying graph of the input. We then go on to focus on the complexity of the problem on tournaments. Here, we provide a complete classification for every possible fixed value of p,q, which shows that the problem exhibits a surprising behavior, including cases which are in P; cases which are solvable in quasi-polynomial time but not in P; and a single case (p=q=1) which is NP-hard (under randomized reductions) and cannot be solved in sub-exponential time, under standard assumptions.
Cite as

Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Eun Jung Kim, and Michael Lampis. New Results on Directed Edge Dominating Set. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 67:1-67:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{belmonte_et_al:LIPIcs.MFCS.2018.67,
  author =	{Belmonte, R\'{e}my and Hanaka, Tesshu and Katsikarelis, Ioannis and Kim, Eun Jung and Lampis, Michael},
  title =	{{New Results on Directed Edge Dominating Set}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{67:1--67:16},
  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.67},
  URN =		{urn:nbn:de:0030-drops-96490},
  doi =		{10.4230/LIPIcs.MFCS.2018.67},
  annote =	{Keywords: Edge Dominating Set, Tournaments, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.24
Parameterized Orientable Deletion

Authors: Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, and Florian Sikora

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
A graph is d-orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most d. d-orientability is a well-studied concept with close connections to fundamental graph-theoretic notions and applications as a load balancing problem. In this paper we consider the d-Orientable Deletion problem: given a graph G=(V,E), delete the minimum number of vertices to make G d-orientable. We contribute a number of results that improve the state of the art on this problem. Specifically: - We show that the problem is W[2]-hard and log n-inapproximable with respect to k, the number of deleted vertices. This closes the gap in the problem's approximability. - We completely characterize the parameterized complexity of the problem on chordal graphs: it is FPT parameterized by d+k, but W-hard for each of the parameters d,k separately. - We show that, under the SETH, for all d,epsilon, the problem does not admit a (d+2-epsilon)^{tw}, algorithm where tw is the graph's treewidth, resolving as a special case an open problem on the complexity of PseudoForest Deletion. - We show that the problem is W-hard parameterized by the input graph's clique-width. Complementing this, we provide an algorithm running in time d^{O(d * cw)}, showing that the problem is FPT by d+cw, and improving the previously best know algorithm for this case.
Cite as

Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, and Florian Sikora. Parameterized Orientable Deletion. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.SWAT.2018.24,
  author =	{Hanaka, Tesshu and Katsikarelis, Ioannis and Lampis, Michael and Otachi, Yota and Sikora, Florian},
  title =	{{Parameterized Orientable Deletion}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{24:1--24:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.24},
  URN =		{urn:nbn:de:0030-drops-88506},
  doi =		{10.4230/LIPIcs.SWAT.2018.24},
  annote =	{Keywords: Graph orientations, FPT algorithms, Treewidth, SETH}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.45
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}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact