2 Search Results for "Yazdanbod, Sadra"

Document
DOI: 10.4230/LIPIcs.STACS.2025.51
Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures

Authors: Felix Hommelsheim, Zhenwei Liu, Nicole Megow, and Guochuan Zhang

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We study the problem of guaranteeing the connectivity of a given graph by protecting or strengthening edges. Herein, a protected edge is assumed to be robust and will not fail, which features a non-uniform failure model. We introduce the (p,q)-Steiner-Connectivity Preservation problem where we protect a minimum-cost set of edges such that the underlying graph maintains p-edge-connectivity between given terminal pairs against edge failures, assuming at most q unprotected edges can fail. We design polynomial-time exact algorithms for the cases where p and q are small and approximation algorithms for general values of p and q. Additionally, we show that when both p and q are part of the input, even deciding whether a given solution is feasible is NP-complete. This hardness also carries over to Flexible Network Design, a research direction that has gained significant attention. In particular, previous work focuses on problem settings where either p or q is constant, for which our new hardness result now provides justification.
Cite as

Felix Hommelsheim, Zhenwei Liu, Nicole Megow, and Guochuan Zhang. Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 51:1-51:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hommelsheim_et_al:LIPIcs.STACS.2025.51,
  author =	{Hommelsheim, Felix and Liu, Zhenwei and Megow, Nicole and Zhang, Guochuan},
  title =	{{Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{51:1--51:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.51},
  URN =		{urn:nbn:de:0030-drops-228761},
  doi =		{10.4230/LIPIcs.STACS.2025.51},
  annote =	{Keywords: Network Design, Edge Failures, Graph Connectivity, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.65
The Computational Complexity of Genetic Diversity

Authors: Ruta Mehta, Ioannis Panageas, Georgios Piliouras, and Sadra Yazdanbod

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
A key question in biological systems is whether genetic diversity persists in the long run under evolutionary competition, or whether a single dominant genotype emerges. Classic work by [Kalmus, J. og Genetics, 1945] has established that even in simple diploid species (species with chromosome pairs) diversity can be guaranteed as long as the heterozygous (having different alleles for a gene on two chromosomes) individuals enjoy a selective advantage. Despite the classic nature of the problem, as we move towards increasingly polymorphic traits (e.g., human blood types) predicting diversity (and its implications) is still not fully understood. Our key contribution is to establish complexity theoretic hardness results implying that even in the textbook case of single locus (gene) diploid models, predicting whether diversity survives or not given its fitness landscape is algorithmically intractable. Our hardness results are structurally robust along several dimensions, e.g., choice of parameter distribution, different definitions of stability/persistence, restriction to typical subclasses of fitness landscapes. Technically, our results exploit connections between game theory, nonlinear dynamical systems, and complexity theory and establish hardness results for predicting the evolution of a deterministic variant of the well known multiplicative weights update algorithm in symmetric coordination games; finding one Nash equilibrium is easy in these games. In the process we characterize stable fixed points of these dynamics using the notions of Nash equilibrium and negative semidefiniteness. This as well as hardness results for decision problems in coordination games may be of independent interest. Finally, we complement our results by establishing that under randomly chosen fitness landscapes diversity survives with significant probability. The full version of this paper is available at http://arxiv.org/abs/1411.6322.
Cite as

Ruta Mehta, Ioannis Panageas, Georgios Piliouras, and Sadra Yazdanbod. The Computational Complexity of Genetic Diversity. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 65:1-65:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{mehta_et_al:LIPIcs.ESA.2016.65,
  author =	{Mehta, Ruta and Panageas, Ioannis and Piliouras, Georgios and Yazdanbod, Sadra},
  title =	{{The Computational Complexity of Genetic Diversity}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{65:1--65:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.65},
  URN =		{urn:nbn:de:0030-drops-64073},
  doi =		{10.4230/LIPIcs.ESA.2016.65},
  annote =	{Keywords: Dynamical Systems, Stability, Complexity, Optimization, Equilibrium}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2016

  • Refine by Author
  • 1 Hommelsheim, Felix
  • 1 Liu, Zhenwei
  • 1 Megow, Nicole
  • 1 Mehta, Ruta
  • 1 Panageas, Ioannis
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Complexity
  • 1 Dynamical Systems
  • 1 Edge Failures
  • 1 Equilibrium
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact