4 Search Results for "Akhoondian Amiri, Saeed"

Document
DOI: 10.4230/LIPIcs.MFCS.2020.6
Complexity of Computing the Anti-Ramsey Numbers for Paths

Authors: Saeed Akhoondian Amiri, Alexandru Popa, Mohammad Roghani, Golnoosh Shahkarami, Reza Soltani, and Hossein Vahidi

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
The anti-Ramsey numbers are a fundamental notion in graph theory, introduced in 1978, by Erdös, Simonovits and Sós. For given graphs G and H the anti-Ramsey number ar(G,H) is defined to be the maximum number k such that there exists an assignment of k colors to the edges of G in which every copy of H in G has at least two edges with the same color. Usually, combinatorists study extremal values of anti-Ramsey numbers for various classes of graphs. There are works on the computational complexity of the problem when H is a star. Along this line of research, we study the complexity of computing the anti-Ramsey number ar(G,P_k), where P_k is a path of length k. First, we observe that when k is close to n, the problem is hard; hence, the challenging part is the computational complexity of the problem when k is a fixed constant. We provide a characterization of the problem for paths of constant length. Our first main contribution is to prove that computing ar(G,P_k) for every integer k > 2 is NP-hard. We obtain this by providing several structural properties of such coloring in graphs. We investigate further and show that approximating ar(G,P₃) to a factor of n^{-1/2 - ε} is hard already in 3-partite graphs, unless P = NP. We also study the exact complexity of the precolored version and show that there is no subexponential algorithm for the problem unless ETH fails for any fixed constant k. Given the hardness of approximation and parametrization of the problem, it is natural to study the problem on restricted graph families. Along this line, we first introduce the notion of color connected coloring, and, employing this structural property, we obtain a linear time algorithm to compute ar(G,P_k), for every integer k, when the host graph, G, is a tree.
Cite as

Saeed Akhoondian Amiri, Alexandru Popa, Mohammad Roghani, Golnoosh Shahkarami, Reza Soltani, and Hossein Vahidi. Complexity of Computing the Anti-Ramsey Numbers for Paths. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 6:1-6:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{akhoondianamiri_et_al:LIPIcs.MFCS.2020.6,
  author =	{Akhoondian Amiri, Saeed and Popa, Alexandru and Roghani, Mohammad and Shahkarami, Golnoosh and Soltani, Reza and Vahidi, Hossein},
  title =	{{Complexity of Computing the Anti-Ramsey Numbers for Paths}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.6},
  URN =		{urn:nbn:de:0030-drops-126781},
  doi =		{10.4230/LIPIcs.MFCS.2020.6},
  annote =	{Keywords: Coloring, Anti-Ramsey, Approximation, NP-hard, Algorithm, ETH}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.143
Congestion-Free Rerouting of Flows on DAGs

Authors: Saeed Akhoondian Amiri, Szymon Dudycz, Stefan Schmid, and Sebastian Wiederrecht

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Changing a given configuration in a graph into another one is known as a reconfiguration problem. Such problems have recently received much interest in the context of algorithmic graph theory. We initiate the theoretical study of the following reconfiguration problem: How to reroute k unsplittable flows of a certain demand in a capacitated network from their current paths to their respective new paths, in a congestion-free manner? This problem finds immediate applications, e.g., in traffic engineering in computer networks. We show that the problem is generally NP-hard already for k=2 flows, which motivates us to study rerouting on a most basic class of flow graphs, namely DAGs. Interestingly, we find that for general k, deciding whether an unsplittable multi-commodity flow rerouting schedule exists, is NP-hard even on DAGs. Our main contribution is a polynomial-time (fixed parameter tractable) algorithm to solve the route update problem for a bounded number of flows on DAGs. At the heart of our algorithm lies a novel decomposition of the flow network that allows us to express and resolve reconfiguration dependencies among flows.
Cite as

Saeed Akhoondian Amiri, Szymon Dudycz, Stefan Schmid, and Sebastian Wiederrecht. Congestion-Free Rerouting of Flows on DAGs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 143:1-143:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{akhoondianamiri_et_al:LIPIcs.ICALP.2018.143,
  author =	{Akhoondian Amiri, Saeed and Dudycz, Szymon and Schmid, Stefan and Wiederrecht, Sebastian},
  title =	{{Congestion-Free Rerouting of Flows on DAGs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{143:1--143:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.143},
  URN =		{urn:nbn:de:0030-drops-91471},
  doi =		{10.4230/LIPIcs.ICALP.2018.143},
  annote =	{Keywords: Unsplittable Flows, Reconfiguration, DAGs, FPT, NP-Hardness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.7
Routing with Congestion in Acyclic Digraphs

Authors: Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, and Roman Rabinovich

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
We study the version of the k-disjoint paths problem where k demand pairs (s_1,t_1), ..., (s_k,t_k) are specified in the input and the paths in the solution are allowed to intersect, but such that no vertex is on more than c paths. We show that on directed acyclic graphs the problem is solvable in time n^{O(d)} if we allow congestion k-d for k paths. Furthermore, we show that, under a suitable complexity theoretic assumption, the problem cannot be solved in time f(k)n^{o(d*log(d))} for any computable function f.
Cite as

Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, and Roman Rabinovich. Routing with Congestion in Acyclic Digraphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 7:1-7:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{amiri_et_al:LIPIcs.MFCS.2016.7,
  author =	{Amiri, Saeed Akhoondian and Kreutzer, Stephan and Marx, D\'{a}niel and Rabinovich, Roman},
  title =	{{Routing with Congestion in Acyclic Digraphs}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{7:1--7:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.7},
  URN =		{urn:nbn:de:0030-drops-64244},
  doi =		{10.4230/LIPIcs.MFCS.2016.7},
  annote =	{Keywords: algorithms, disjoint paths, congestion, acyclic digraphs, XP, W\lbrack1\rbrack-hard}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.34
Graph Searching Games and Width Measures for Directed Graphs

Authors: Saeed Akhoondian Amiri, Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, and Sebastian Siebertz

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
In cops and robber games a number of cops tries to capture a robber in a graph. A variant of these games on undirected graphs characterises tree width by the least number of cops needed to win. We consider cops and robber games on digraphs and width measures (such as DAG-width, directed tree width or D-width) corresponding to them. All of them generalise tree width and the game characterising it. For the DAG-width game we prove that the problem to decide the minimal number of cops required to capture the robber (which is the same as deciding DAG-width), is PSPACE-complete, in contrast to most other similar games. We also show that the cop-monotonicity cost for directed tree width games cannot be bounded by any function. As a consequence, D-width is not bounded in directed tree width, refuting a conjecture by Safari. A large number of directed width measures generalising tree width has been proposed in the literature. However, only very little was known about the relation between them, in particular about whether classes of digraphs of bounded width in one measure have bounded width in another. In this paper we establish an almost complete order among the most prominent width measures with respect to mutual boundedness.
Cite as

Saeed Akhoondian Amiri, Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, and Sebastian Siebertz. Graph Searching Games and Width Measures for Directed Graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 34-47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{akhoondianamiri_et_al:LIPIcs.STACS.2015.34,
  author =	{Akhoondian Amiri, Saeed and Kaiser, Lukasz and Kreutzer, Stephan and Rabinovich, Roman and Siebertz, Sebastian},
  title =	{{Graph Searching Games and Width Measures for Directed Graphs}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{34--47},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.34},
  URN =		{urn:nbn:de:0030-drops-49020},
  doi =		{10.4230/LIPIcs.STACS.2015.34},
  annote =	{Keywords: cops and robber games, directed graphs, DAG-width}
}
  • Refine by Author
  • 3 Akhoondian Amiri, Saeed
  • 2 Kreutzer, Stephan
  • 2 Rabinovich, Roman
  • 1 Amiri, Saeed Akhoondian
  • 1 Dudycz, Szymon
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Graph theory
  • 1 Networks → Network algorithms
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 1 Algorithm
  • 1 Anti-Ramsey
  • 1 Approximation
  • 1 Coloring
  • 1 DAG-width
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2015
  • 1 2016
  • 1 2018
  • 1 2020

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact