1 Search Results for "Kaspi, Moshe"


Document
Parameterized Complexity of Critical Node Cuts

Authors: Danny Hermelin, Moshe Kaspi, Christian Komusiewicz, and Barak Navon

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)


Abstract
We consider the following graph cut problem called Critical Node Cut (CNC): Given a graph G on n vertices, and two positive integers k and x, determine whether G has a set of k vertices whose removal leaves G with at most x connected pairs of vertices. We analyze this problem in the framework of parameterized complexity. That is, we are interested in whether or not this problem is solvable in f(kappa) * n^{O(1)} time (i.e., whether or not it is fixed-parameter tractable), for various natural parameters kappa. We consider four such parameters: - The size k of the required cut. - The upper bound x on the number of remaining connected pairs. - The lower bound y on the number of connected pairs to be removed. - The treewidth w of G. We determine whether or not CNC is fixed-parameter tractable for each of these parameters. We determine this also for all possible aggregations of these four parameters, apart from w+k. Moreover, we also determine whether or not CNC admits a polynomial kernel for all these parameterizations. That is, whether or not there is an algorithm that reduces each instance of CNC in polynomial time to an equivalent instance of size kappa^{O(1)}, where kappa is the given parameter.

Cite as

Danny Hermelin, Moshe Kaspi, Christian Komusiewicz, and Barak Navon. Parameterized Complexity of Critical Node Cuts. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 343-354, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{hermelin_et_al:LIPIcs.IPEC.2015.343,
  author =	{Hermelin, Danny and Kaspi, Moshe and Komusiewicz, Christian and Navon, Barak},
  title =	{{Parameterized Complexity of Critical Node Cuts}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{343--354},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.343},
  URN =		{urn:nbn:de:0030-drops-55950},
  doi =		{10.4230/LIPIcs.IPEC.2015.343},
  annote =	{Keywords: graph cut problem, NP-hard problem, treewidth}
}
  • Refine by Author
  • 1 Hermelin, Danny
  • 1 Kaspi, Moshe
  • 1 Komusiewicz, Christian
  • 1 Navon, Barak

  • Refine by Classification

  • Refine by Keyword
  • 1 NP-hard problem
  • 1 graph cut problem
  • 1 treewidth

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2015

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