6 Search Results for "Méndez, Gonzalo"

Document
DOI: 10.4230/LIPIcs.SWAT.2026.26
On the Parameterized Complexity of Min-Sum-Radii

Authors: Pankaj Kumar, Haiko Müller, Sebastian Ordyniak, and Melanie Schmidt

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
In the Min-Sum-Radii (MSR) clustering problem, we are given a finite set X of n points in a metric space. The objective is to find at most k clusters centered at a subset of these points such that every point of X is assigned to one of the clusters, minimizing the sum of the radii of the clusters. The problem is known to be NP-hard even on metrics induced by weighted planar graphs and metrics with constant doubling dimension, as shown by Gibson et al. (SWAT 2008). In this work, we investigate the parameterized complexity of MSR on metrics induced by undirected graphs. We distinguish between weighted graph metrics (with positive edge weights) and unweighted graph metrics (where all edges have unit weight). Weighted Graph Metrics. We show that MSR is W[1]-hard on metrics induced by weighted bipartite graphs, when parameterized by the combined parameter k the number of clusters and Δ the cost of the clustering. We then investigate the structural parameterized complexity of the problem. Drexler et al. [doi:10.48550/arXiv.2310.02130] showed that the MSR problem admits an XP algorithm on metrics induced by weighted graphs when parameterized by treewidth, and asked whether this can be improved to fixed-parameter tractability. We first answer their question in the negative, and more strongly show that MSR stays W[1]-hard on metrics induced by undirected weighted bipartite graphs when parameterized by the vertex cover number plus k. We then turn our attention to parameters for dense graphs and show that MSR remains W[1]-hard when parameterized by k+Δ even on cliques and complete bipartite graphs. On the positive side, we employ the known XP algorithm parameterized by treewidth, to show that the MSR problem is FPT when parameterized by the parameter treewidth plus Δ. Together, these results provide a complete picture of the parameterized complexity of MSR with respect to any combination of parameters k, Δ, as well as structural parameters for sparse graphs above vertex cover and known parameters for dense graphs (such as neighborhood diversity and modular width). Unweighted Graph Metrics. The story is rather different for unweighted graphs, since it is a long standing open question whether MSR on metrics induced by undirected graphs is solvable in polynomial-time. Although we cannot answer this question, we provide classical and parameterized hardness results for two very closely related problems, namely Exact-MSR (MSR and one wants to find exactly k clusters) and Allowed-Centers-MSR (MSR with an additional set of allowed cluster centers). We also show that MSR as well as these two problems are fixed-parameter tractable parameterized by the treedepth of the input graph.
Cite as

Pankaj Kumar, Haiko Müller, Sebastian Ordyniak, and Melanie Schmidt. On the Parameterized Complexity of Min-Sum-Radii. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.SWAT.2026.26,
  author =	{Kumar, Pankaj and M\"{u}ller, Haiko and Ordyniak, Sebastian and Schmidt, Melanie},
  title =	{{On the Parameterized Complexity of Min-Sum-Radii}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.26},
  URN =		{urn:nbn:de:0030-drops-260623},
  doi =		{10.4230/LIPIcs.SWAT.2026.26},
  annote =	{Keywords: Parameterized complexity, Min-Sum-Radii clustering}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.42
Computing Twin-Width via Treedepth and Vertex Integrity

Authors: Robert Ganian and Mathis Rocton

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Twin-width is a graph parameter that has become central to explaining the fixed-parameter tractability of first-order model checking across many graph classes. Despite its algorithmic importance, computing twin-width remains poorly understood: even recognizing graphs of twin-width at most four is NP-hard, and no fixed-parameter approximations parameterized by twin-width itself are known. A recent approach towards breaking this barrier focuses on first developing fixed-parameter algorithms for computing or approximating twin-width under parameterizations distinct from twin-width. Our first result establishes that approximating twin-width is fixed-parameter tractable when parameterized by treedepth, thereby breaking the long-standing barrier that all previous tractable parameterizations were based on deletion distance. The proof proceeds via oriented twin-width, yielding the first constructive evidence that this variant may be easier to handle algorithmically. As our second main result, we show that computing twin-width exactly is fixed-parameter tractable with respect to vertex integrity. This constitutes the first non-trivial parameterized algorithm for computing optimal contraction sequences.
Cite as

Robert Ganian and Mathis Rocton. Computing Twin-Width via Treedepth and Vertex Integrity. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 42:1-42:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.STACS.2026.42,
  author =	{Ganian, Robert and Rocton, Mathis},
  title =	{{Computing Twin-Width via Treedepth and Vertex Integrity}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{42:1--42:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle 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.2026.42},
  URN =		{urn:nbn:de:0030-drops-255318},
  doi =		{10.4230/LIPIcs.STACS.2026.42},
  annote =	{Keywords: twin-width, fixed-parameter algorithms, treedepth, vertex integrity}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.17
Treedepth Inapproximability and Exponential ETH Lower Bound

Authors: Édouard Bonnet, Daniel Neuen, and Marek Sokołowski

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
Treedepth is a central parameter to algorithmic graph theory. The current state-of-the-art in computing and approximating treedepth consists of a 2^{O(k²)} n-time exact algorithm and a polynomial-time O(OPT log^{3/2} OPT)-approximation algorithm, where the former algorithm returns an elimination forest of height k (witnessing that treedepth is at most k) for the n-vertex input graph G, or correctly reports that G has treedepth larger than k, and OPT is the actual value of the treedepth. On the complexity side, exactly computing treedepth is NP-complete, but the known reductions do not rule out a polynomial-time approximation scheme (PTAS), and under the Exponential Time Hypothesis (ETH) only exclude a running time of 2^o(√n) for exact algorithms. We show that 1.0003-approximating Treedepth is NP-hard, and that exactly computing the treedepth of an n-vertex graph requires time 2^Ω(n), unless the ETH fails. We further derive that there exist absolute constants δ, c > 0 such that any (1+δ)-approximation algorithm requires time 2^Ω(n/log^c n). We do so via a simple direct reduction from Satisfiability to Treedepth, inspired by a reduction recently designed for Treewidth [STOC '25].
Cite as

Édouard Bonnet, Daniel Neuen, and Marek Sokołowski. Treedepth Inapproximability and Exponential ETH Lower Bound. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 17:1-17:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.IPEC.2025.17,
  author =	{Bonnet, \'{E}douard and Neuen, Daniel and Soko{\l}owski, Marek},
  title =	{{Treedepth Inapproximability and Exponential ETH Lower Bound}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{17:1--17:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.17},
  URN =		{urn:nbn:de:0030-drops-251494},
  doi =		{10.4230/LIPIcs.IPEC.2025.17},
  annote =	{Keywords: treedepth, lower bounds, approximation}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.20
Routing Few Robots in a Crowded Network

Authors: Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, Dominik Leko, and M. S. Ramanujan

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
In Graph Coordinated Motion Planning, we are given a graph G some of whose vertices are occupied by robots, and we are asked to route k marked robots to their destinations while avoiding collisions and without exceeding a given budget 𝓁 on the number of robot moves. We continue the recent investigation of the problem [ICALP 2024], focusing on the parameter k that captures the task of routing a small number of robots in a possibly crowded graph. We prove that the problem is W[1]-hard parameterized by 𝓁 even for k = 1, but fixed-parameter tractable parameterized by k plus the treedepth of G. We complement the latter algorithm with an NP-hardness reduction which shows that both parameters are necessary to achieve tractability.
Cite as

Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, Dominik Leko, and M. S. Ramanujan. Routing Few Robots in a Crowded Network. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{deligkas_et_al:LIPIcs.WADS.2025.20,
  author =	{Deligkas, Argyrios and Eiben, Eduard and Ganian, Robert and Kanj, Iyad and Leko, Dominik and Ramanujan, M. S.},
  title =	{{Routing Few Robots in a Crowded Network}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{20:1--20:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.20},
  URN =		{urn:nbn:de:0030-drops-242516},
  doi =		{10.4230/LIPIcs.WADS.2025.20},
  annote =	{Keywords: graph coordinated motion planning, parameterized complexity, treedepth}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.45
Forbidden Patterns in Mixed Linear Layouts

Authors: Deborah Haun, Laura Merker, and Sergey Pupyrev

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

Abstract
An ordered graph is a graph with a total order over its vertices. A linear layout of an ordered graph is a partition of the edges into sets of either non-crossing edges, called stacks, or non-nesting edges, called queues. The stack (queue) number of an ordered graph is the minimum number of required stacks (queues). Mixed linear layouts combine these layouts by allowing each set of edges to form either a stack or a queue. The minimum number of stacks plus queues is called the mixed page number. It is well known that ordered graphs with small stack number are characterized, up to a function, by the absence of large twists (that is, pairwise crossing edges). Similarly, ordered graphs with small queue number are characterized by the absence of large rainbows (that is, pairwise nesting edges). However, no such characterization via forbidden patterns is known for mixed linear layouts. We address this gap by introducing patterns similar to twists and rainbows, which we call thick patterns; such patterns allow a characterization, again up to a function, of mixed linear layouts of bounded-degree graphs. That is, we show that a family of ordered graphs with bounded maximum degree has bounded mixed page number if and only if the size of the largest thick pattern is bounded. In addition, we investigate an exact characterization of ordered graphs whose mixed page number equals a fixed integer k via a finite set of forbidden patterns. We show that for k = 2, there is no such characterization, which supports the nature of our first result.
Cite as

Deborah Haun, Laura Merker, and Sergey Pupyrev. Forbidden Patterns in Mixed Linear Layouts. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 45:1-45:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{haun_et_al:LIPIcs.STACS.2025.45,
  author =	{Haun, Deborah and Merker, Laura and Pupyrev, Sergey},
  title =	{{Forbidden Patterns in Mixed Linear Layouts}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{45:1--45: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.45},
  URN =		{urn:nbn:de:0030-drops-228717},
  doi =		{10.4230/LIPIcs.STACS.2025.45},
  annote =	{Keywords: Ordered Graphs, linear Layout, mixed linear Layout, Stack Layout, Queue Layout}
}
Document
DOI: 10.4230/OASIcs.CMN.2015.54
Schemas for Narrative Generation Mined from Existing Descriptions of Plot

Authors: Pablo Gervás, Carlos León, and Gonzalo Méndez

Published in: OASIcs, Volume 45, 6th Workshop on Computational Models of Narrative (CMN 2015)

Abstract
Computational generation of literary artifacts very often resorts to template-like schemas that can be instantiated into complex structures. With this view in mind, the present paper reviews a number of existing attempts to provide an elementary set of patterns for basic plots. An attempt is made to formulate these descriptions of possible plots in terms of character functions, an abstraction of plot-bearing elements of a story originally formulated by Vladimir Propp. These character functions act as the building blocks of the Propper system, an existing framework for computational story generation. The paper explores the set of extensions required to the original set of character functions to allow for a basic representation of the analysed schemata, and a solution for automatic generation of stories based on this formulation of the narrative schemas. This solution uncovers important insights on the relative expressive power of the representation of narrative in terms of character functions, and their impact on the generative potential of the framework is discussed.
Cite as

Pablo Gervás, Carlos León, and Gonzalo Méndez. Schemas for Narrative Generation Mined from Existing Descriptions of Plot. In 6th Workshop on Computational Models of Narrative (CMN 2015). Open Access Series in Informatics (OASIcs), Volume 45, pp. 54-71, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{gervas_et_al:OASIcs.CMN.2015.54,
  author =	{Gerv\'{a}s, Pablo and Le\'{o}n, Carlos and M\'{e}ndez, Gonzalo},
  title =	{{Schemas for Narrative Generation Mined from Existing Descriptions of Plot}},
  booktitle =	{6th Workshop on Computational Models of Narrative (CMN 2015)},
  pages =	{54--71},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-93-4},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{45},
  editor =	{Finlayson, Mark A. and Miller, Ben and Lieto, Antonio and Ronfard, Remi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2015.54},
  URN =		{urn:nbn:de:0030-drops-52812},
  doi =		{10.4230/OASIcs.CMN.2015.54},
  annote =	{Keywords: Narrative generation, conceptual representation of narrative, character functions, plot, narrative schemas}
}
  • Refine by Type
  • 6 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 3 2025
  • 1 2015

  • Refine by Author
  • 2 Ganian, Robert
  • 1 Bonnet, Édouard
  • 1 Deligkas, Argyrios
  • 1 Eiben, Eduard
  • 1 Gervás, Pablo
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 4 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 3 treedepth
  • 1 Min-Sum-Radii clustering
  • 1 Narrative generation
  • 1 Ordered Graphs
  • 1 Parameterized complexity
  • 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