34 Search Results for "Kanté, Mamadou M."

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.ITCS.2026.4
Pseudodeterministic Algorithms for Minimum Cut Problems

Authors: Aryan Agarwala and Nithin Varma

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
In this paper we present efficient pseudodeterministic algorithms for both the global minimum cut and minimum s-t cut problems. The running time of our algorithm for the global minimum cut problem is asymptotically better than the fastest sequential deterministic global minimum cut algorithm (Henzinger, Li, Rao, Wang; SODA 2024). Furthermore, we implement our algorithm in streaming, PRAM, and cut-query models, where no efficient deterministic global minimum cut algorithms are known.
Cite as

Aryan Agarwala and Nithin Varma. Pseudodeterministic Algorithms for Minimum Cut Problems. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agarwala_et_al:LIPIcs.ITCS.2026.4,
  author =	{Agarwala, Aryan and Varma, Nithin},
  title =	{{Pseudodeterministic Algorithms for Minimum Cut Problems}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.4},
  URN =		{urn:nbn:de:0030-drops-252917},
  doi =		{10.4230/LIPIcs.ITCS.2026.4},
  annote =	{Keywords: Minimum Cut, Pseudodeterministic Algorithms}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.30
A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers

Authors: Jesse Beisegel, Katharina Klost, Kristin Knorr, Fabienne Ratajczak, and Robert Scheffler

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

Abstract
We consider the problem of finding a Hamiltonian path or cycle with precedence constraints in the form of a partial order on the vertex set. We study the complexity for graph width parameters for which the ordinary problems Hamiltonian Path and Hamiltonian Cycle are in FPT. In particular, we focus on parameters that describe how many vertices and edges have to be deleted to become a member of a certain graph class. We show that the problems are W[1]-hard for such restricted cases as vertex distance to path and vertex distance to clique. We complement these results by showing that the problems can be solved in XP time for vertex distance to outerplanar and vertex distance to block. Furthermore, we present some FPT algorithms, e.g., for edge distance to block. Additionally, we prove para-NP-hardness when considered with the edge clique cover number.
Cite as

Jesse Beisegel, Katharina Klost, Kristin Knorr, Fabienne Ratajczak, and Robert Scheffler. A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{beisegel_et_al:LIPIcs.IPEC.2025.30,
  author =	{Beisegel, Jesse and Klost, Katharina and Knorr, Kristin and Ratajczak, Fabienne and Scheffler, Robert},
  title =	{{A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{30:1--30:19},
  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.30},
  URN =		{urn:nbn:de:0030-drops-251623},
  doi =		{10.4230/LIPIcs.IPEC.2025.30},
  annote =	{Keywords: Hamiltonian path, Hamiltonian cycle, partial order, graph width parameter, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.31
Hamiltonicity Parameterized by Mim-Width Is (Indeed) Para-NP-Hard

Authors: Benjamin Bergougnoux and Lars Jaffke

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

Abstract
We prove that Hamiltonian Path and Hamiltonian Cycle are NP-hard on graphs of linear mim-width 26, even when a linear order of the input graph with mim-width 26 is provided together with input. This fills a gap left by a broken proof of the para-NP-hardness of Hamiltonicity problems parameterized by mim-width.
Cite as

Benjamin Bergougnoux and Lars Jaffke. Hamiltonicity Parameterized by Mim-Width Is (Indeed) Para-NP-Hard. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 31:1-31:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bergougnoux_et_al:LIPIcs.IPEC.2025.31,
  author =	{Bergougnoux, Benjamin and Jaffke, Lars},
  title =	{{Hamiltonicity Parameterized by Mim-Width Is (Indeed) Para-NP-Hard}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{31:1--31: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.31},
  URN =		{urn:nbn:de:0030-drops-251631},
  doi =		{10.4230/LIPIcs.IPEC.2025.31},
  annote =	{Keywords: Hamiltonian Path, Hamiltonian Cycle, Mim-Width, Para-NP-Hardness}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.19
Tight Bounds for Connected Odd Cycle Transversal Parameterized by Clique-Width

Authors: Narek Bojikian and Stefan Kratsch

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

Abstract
Recently, Bojikian and Kratsch [ICALP 2024] presented a novel approach to tackle connectivity problems parameterized by clique-width (cw), based on counting (modulo 2) the number of representations of partial solutions, while allowing for possibly multiple representations to exist for the same partial solution. Using this technique, they got a SETH-tight bound of 𝒪^*(3^{cw}) for the Steiner Tree problem, which was left open by Hegerfeld and Kratsch [ESA 2023]. We use the same technique to solve the Connected Odd Cycle Transversal problem in time 𝒪^*(12^{cw}). Moreover, we prove that our result is tight by providing a SETH-based lower bound excluding algorithms with running time 𝒪^*((12-ε)^{cw}). This answers another question of Hegerfeld and Kratsch [ESA 2023].
Cite as

Narek Bojikian and Stefan Kratsch. Tight Bounds for Connected Odd Cycle Transversal Parameterized by Clique-Width. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bojikian_et_al:LIPIcs.IPEC.2025.19,
  author =	{Bojikian, Narek and Kratsch, Stefan},
  title =	{{Tight Bounds for Connected Odd Cycle Transversal Parameterized by Clique-Width}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{19:1--19:15},
  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.19},
  URN =		{urn:nbn:de:0030-drops-251516},
  doi =		{10.4230/LIPIcs.IPEC.2025.19},
  annote =	{Keywords: Parameterized complexity, connected odd cycle transversal, clique-width}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.21
A Polynomial Delay Algorithm Generating All Potential Maximal Cliques in Triconnected Planar Graphs

Authors: Alexander Grigoriev, Yasuaki Kobayashi, Hisao Tamaki, and Tom C. van der Zanden

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

Abstract
We develop a new characterization of potential maximal cliques of a triconnected planar graph and, using this characterization, give a polynomial delay algorithm generating all potential maximal cliques of a given triconnected planar graph. Combined with the dynamic programming algorithm due to Bouchitté and Todinca, this algorithm leads to a treewidth algorithm for general planar graphs that runs in time linear in the number of potential maximal cliques and polynomial in the number of vertices.
Cite as

Alexander Grigoriev, Yasuaki Kobayashi, Hisao Tamaki, and Tom C. van der Zanden. A Polynomial Delay Algorithm Generating All Potential Maximal Cliques in Triconnected Planar Graphs. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grigoriev_et_al:LIPIcs.IPEC.2025.21,
  author =	{Grigoriev, Alexander and Kobayashi, Yasuaki and Tamaki, Hisao and van der Zanden, Tom C.},
  title =	{{A Polynomial Delay Algorithm Generating All Potential Maximal Cliques in Triconnected Planar Graphs}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{21:1--21:17},
  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.21},
  URN =		{urn:nbn:de:0030-drops-251530},
  doi =		{10.4230/LIPIcs.IPEC.2025.21},
  annote =	{Keywords: potential maximal cliques, treewidth, planar graphs, triconnected planar graphs, polynomial delay generation}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2025.2
Unboundedness Problems for Formal Languages (Invited Talk)

Authors: Georg Zetzsche

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
Informally, unboundedness problems are decision problems that ask about the existence of infinitely many words (satisfying certain properties) in a formal language. For example: Is a given language infinite? Or: Does a given language have super-polynomial growth? These came into focus in recent years because of their connections to downward closure computation and separability problems. Although unboundedness problems may seem difficult at first, it turns out that there are techniques that are at the same time conceptually very simple, but also apply to a surprisingly wide variety of language classes. The talk will survey recent results (and techniques) concerning unboundedness problems.
Cite as

Georg Zetzsche. Unboundedness Problems for Formal Languages (Invited Talk). In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 2:1-2:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{zetzsche:LIPIcs.FSTTCS.2025.2,
  author =	{Zetzsche, Georg},
  title =	{{Unboundedness Problems for Formal Languages}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{2:1--2:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.2},
  URN =		{urn:nbn:de:0030-drops-250810},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.2},
  annote =	{Keywords: Decidability, formal languages, unifying frameworks, downward closure, separability}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.49
On the Hardness of Order Finding and Equivalence Testing for ROABPs

Authors: C. Ramya and Pratik Shastri

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
The complexity of representing a polynomial by a Read-Once Oblivious Algebraic Branching Program (ROABP) is highly dependent on the chosen variable ordering. Bhargava et al. [Bhargava et al., 2024] prove that finding the optimal ordering is NP-hard, and provide some evidence (based on the Small Set Expansion hypothesis) that it is also hard to approximate the optimal ROABP width. In another work, Baraskar et al. [Baraskar et al., 2024] show that it is NP-hard to test whether a polynomial is in the GL_n orbit of a polynomial of sparsity at most s. Building upon these works, we show the following results: first, we prove that approximating the minimum ROABP width up to any constant factor is NP-hard, when the input is presented as a circuit. This removes the reliance on stronger conjectures in the previous work [Bhargava et al., 2024]. Second, we show that testing if an input polynomial given in the sparse representation is in the affine GL_n orbit of a width-w ROABP is NP-hard. Furthermore, we show that over fields of characteristic 0, the problem is NP-hard even when the input polynomial is homogeneous. This provides the first NP-hardness results for membership testing for a dense subclass of polynomial sized algebraic branching programs (VBP). Finally, we locate the source of hardness for the order finding problem at the lowest possible non-trivial degree, proving that the problem is NP-hard even for quadratic forms.
Cite as

C. Ramya and Pratik Shastri. On the Hardness of Order Finding and Equivalence Testing for ROABPs. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 49:1-49:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ramya_et_al:LIPIcs.FSTTCS.2025.49,
  author =	{Ramya, C. and Shastri, Pratik},
  title =	{{On the Hardness of Order Finding and Equivalence Testing for ROABPs}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{49:1--49:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.49},
  URN =		{urn:nbn:de:0030-drops-251296},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.49},
  annote =	{Keywords: ROABP, Order Finding, Equivalence Testing, NP-hardness, Hardness of Approximation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.38
Structural Parameters for Steiner Orientation

Authors: Tesshu Hanaka, Michael Lampis, Nikolaos Melissinos, Edouard Nemery, Hirotaka Ono, and Manolis Vasilakis

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
We consider the Steiner Orientation problem, where we are given as input a mixed graph G = (V,E,A) and a set of k demand pairs (s_i,t_i), i ∈ [k]. The goal is to orient the undirected edges of G in a way that the resulting directed graph has a directed path from s_i to t_i for all i ∈ [k]. We adopt the point of view of structural parameterized complexity and investigate the complexity of Steiner Orientation for standard measures, such as treewidth. Our results indicate that Steiner Orientation is a surprisingly hard problem from this point of view. In particular, our main contributions are the following: 1) We show that Steiner Orientation is NP-complete on instances where the underlying graph has feedback vertex number 2, treewidth 2, pathwidth 3, and vertex integrity 6. 2) We present an XP algorithm parameterized by vertex cover number vc of complexity n^O(vc²). Furthermore, we show that this running time is essentially optimal by proving that a running time of n^o(vc²) would refute the ETH. 3) We consider parameterizations by the number of undirected or directed edges (|E| or |A|) and we observe that the trivial 2^|E| n^O(1)-time algorithm for the former parameter is optimal under the SETH. Complementing this, we show that the problem admits a 2^O(|A|) n^O(1)-time algorithm. In addition to the above, we consider the complexity of Steiner Orientation parameterized by tw+k (FPT), distance to clique (FPT), and vc+k (FPT with a polynomial kernel).
Cite as

Tesshu Hanaka, Michael Lampis, Nikolaos Melissinos, Edouard Nemery, Hirotaka Ono, and Manolis Vasilakis. Structural Parameters for Steiner Orientation. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.ISAAC.2025.38,
  author =	{Hanaka, Tesshu and Lampis, Michael and Melissinos, Nikolaos and Nemery, Edouard and Ono, Hirotaka and Vasilakis, Manolis},
  title =	{{Structural Parameters for Steiner Orientation}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.38},
  URN =		{urn:nbn:de:0030-drops-249461},
  doi =		{10.4230/LIPIcs.ISAAC.2025.38},
  annote =	{Keywords: ETH, Steiner Orientation, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.21
On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers

Authors: Parinya Chalermsook, Ly Orgo, and Minoo Zarsav

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
This paper considers the Zarankiewicz problem in bipartite graphs with low-dimensional geometric representation (i.e., low Ferrers dimension). Let Z(n;k) be the maximum number of edges in a bipartite graph with n nodes and is free of a k-by-k biclique. Note that Z(n;k) ∈ Ω(nk) for all "natural" graph classes. Our first result reveals a separation between bipartite graphs of Ferrers dimension three and four: while we show that Z(n;k) ≤ 9n(k-1) for graphs of Ferrers dimension three, Z(n;k) ∈ Ω(n k ⋅ (log n)/(log log n)) for Ferrers dimension four graphs (Chan & Har-Peled, 2023) (Chazelle, 1990). To complement this, we derive a tight upper bound of 2n(k-1) for chordal bipartite graphs and 54n(k-1) for grid intersection graphs (GIG), a prominent graph class residing in four Ferrers dimensions and capturing planar bipartite graphs as well as bipartite intersection graphs of rectangles. Previously, the best-known bound for GIG was Z(n;k) ∈ O(2^{O(k)} n), implied by the results of Fox & Pach (2006) and Mustafa & Pach (2016). Our results advance and offer new insights into the interplay between Ferrers dimensions and extremal combinatorics.
Cite as

Parinya Chalermsook, Ly Orgo, and Minoo Zarsav. On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chalermsook_et_al:LIPIcs.GD.2025.21,
  author =	{Chalermsook, Parinya and Orgo, Ly and Zarsav, Minoo},
  title =	{{On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{21:1--21:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.21},
  URN =		{urn:nbn:de:0030-drops-250074},
  doi =		{10.4230/LIPIcs.GD.2025.21},
  annote =	{Keywords: Bipartite graph classes, extremal graph theory, geometric intersection graphs, Zarankiewicz problem, bicliques}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.12
Distributed Computation with Local Advice

Authors: Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, and Jukka Suomela

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Algorithms with advice have received ample attention in the distributed and online settings, and they have recently proven useful also in dynamic settings. In this work we study local computation with advice: the goal is to solve a graph problem Π with a distributed algorithm in T(Δ) communication rounds, for some function T that only depends on the maximum degree Δ of the graph, and the key question is how many bits of advice per node are needed. Some of our results regard Locally Checkable Labeling problems (LCLs), which is an important family of problems that includes various coloring and orientation problems on finite-degree graphs. These are constraint-satisfaction graph problems that can be defined with a finite set of valid input/output-labeled neighborhoods. Our main results are: 1) Any locally checkable labeling problem can be solved with only 1 bit of advice per node in graphs with sub-exponential growth (the number of nodes within radius r is sub-exponential in r; for example, grids are such graphs). Moreover, we can make the set of nodes that carry advice bits arbitrarily sparse. As a corollary, any locally checkable labeling problem admits a locally checkable proof with 1 bit per node in graphs with sub-exponential growth. 2) The assumption of sub-exponential growth is complemented by a conditional lower bound: assuming the Exponential-Time Hypothesis, there are locally checkable labeling problems that cannot be solved in general with any constant number of bits per node. 3) In any graph we can find an almost-balanced orientation (indegrees and outdegrees differ by at most one) with 1 bit of advice per node, and again we can make the advice arbitrarily sparse. As a corollary, we can also compress an arbitrary subset of edges so that a node of degree d stores only d/2 + 2 bits, and we can decompress it locally, in T(Δ) rounds. 4) In any graph of maximum degree Δ, we can find a Δ-coloring (if it exists) with 1 bit of advice per node, and again, we can make the advice arbitrarily sparse. 5) In any 3-colorable graph, we can find a 3-coloring with 1 bit of advice per node. As a corollary, in bounded-degree graphs there is a locally checkable proof that certifies 3-colorability with 1 bit of advice per node, while prior work shows that this is not possible with a proof labeling scheme (PLS), which is a more restricted setting where the verifier can only see up to distance 1. Our work shows that for many problems the key threshold is not whether we can achieve 1 bit of advice per node, but whether we can make the advice arbitrarily sparse. To formalize this idea, we develop a general framework of composable schemas that enables us to build algorithms for local computation with advice in a modular fashion: once we have (1) a schema for solving Π₁ and (2) a schema for solving Π₂ assuming an oracle for Π₁, we can also compose them and obtain (3) a schema that solves Π₂ without the oracle. It turns out that many natural problems admit composable schemas, all of them can be solved with only 1 bit of advice, and we can make the advice arbitrarily sparse.
Cite as

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, and Jukka Suomela. Distributed Computation with Local Advice. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.DISC.2025.12,
  author =	{Balliu, Alkida and Brandt, Sebastian and Kuhn, Fabian and Nowicki, Krzysztof and Olivetti, Dennis and Rotenberg, Eva and Suomela, Jukka},
  title =	{{Distributed Computation with Local Advice}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.12},
  URN =		{urn:nbn:de:0030-drops-248295},
  doi =		{10.4230/LIPIcs.DISC.2025.12},
  annote =	{Keywords: Distributed graph algorithms, LOCAL model, computation with advice, locally checkable labeling problems, proof labeling schemes, locally checkable proofs, graph coloring, exponential-time hypothesis}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.22
Constructing Long Paths in Graph Streams

Authors: Christian Konrad and Chhaya Trehan

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
In the graph stream model of computation, an algorithm processes the edges of an n-vertex input graph in one or more sequential passes while using a memory that is sublinear in the input size. The streaming model poses significant challenges for algorithmically constructing long paths. Many known algorithms that are tasked with extending an existing path as a subroutine require an entire pass over the input to add a single additional edge. This raises a fundamental question: Are multiple passes inherently necessary to construct paths of non-trivial lengths, or can a single pass suffice? To address this question, we systematically study the Longest Path problem in the one-pass streaming model. In this problem, given a desired approximation factor α, the objective is to compute a path of length at least lp(G)/α, where lp(G) is the length of a longest path in the input graph G. We study the problem in the insertion-only and the insertion-deletion streaming models, and we give algorithms as well as space lower bounds for both undirected and directed graphs. Our results are: 1) We show that for undirected graphs, in both the insertion-only and the insertion-deletion models, there are semi-streaming algorithms, i.e., algorithms that use space O(n poly log n), that compute a path of length at least d/3 with high probability, where d is the average degree of the input graph. These algorithms can also yield an α-approximation to Longest Path using space Õ(n²/α). 2) Next, we show that such a result cannot be achieved for directed graphs, even in the insertion-only model. We show that computing a (n^{1-o(1)})-approximation to Longest Path in directed graphs in the insertion-only model requires space Ω(n²). This result is in line with recent results that demonstrate that processing directed graphs is often significantly harder than undirected graphs in the streaming model. 3) We further complement our results with two additional lower bounds. First, we show that semi-streaming space is insufficient for small constant factor approximations to Longest Path for undirected graphs in the insertion-only model. Last, in undirected graphs in the insertion-deletion model, we show that computing an α-approximation requires space Ω(n²/α³).
Cite as

Christian Konrad and Chhaya Trehan. Constructing Long Paths in Graph Streams. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{konrad_et_al:LIPIcs.ESA.2025.22,
  author =	{Konrad, Christian and Trehan, Chhaya},
  title =	{{Constructing Long Paths in Graph Streams}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{22:1--22:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.22},
  URN =		{urn:nbn:de:0030-drops-244902},
  doi =		{10.4230/LIPIcs.ESA.2025.22},
  annote =	{Keywords: Longest Path Problem, Streaming Algorithms, One-way Two-party Communication Complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.13
Tight Bounds for Some Classical Problems Parameterized by Cutwidth

Authors: Narek Bojikian, Vera Chekan, and Stefan Kratsch

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Cutwidth is a widely studied parameter and it quantifies how well a graph can be decomposed along small edge-cuts. It complements pathwidth, which captures decomposition by small vertex separators, and it is well-known that cutwidth upper-bounds pathwidth. The SETH-tight parameterized complexity of problems on graphs of bounded pathwidth (and treewidth) has been actively studied over the past decade while for cutwidth the complexity of many classical problems remained open. For Hamiltonian Cycle, it is known that a (2+√2)^{pw} n^𝒪(1) algorithm is optimal for pathwidth under SETH [Cygan et al. JACM 2018]. Van Geffen et al. [J. Graph Algorithms Appl. 2020] and Bojikian et al. [STACS 2023] asked which running time is optimal for this problem parameterized by cutwidth. We answer this question with (1+√2)^{ctw} n^𝒪(1) by providing matching upper and lower bounds. Second, as our main technical contribution, we close the gap left by van Heck [2018] for Partition Into Triangles (and Triangle Packing) by improving both upper and lower bound and getting a tight bound of ∛{3}^{ctw} n^𝒪(1), which to our knowledge exhibits the only known tight non-integral basis apart from Hamiltonian Cycle [Cygan et al. JACM 2018] and C₄-Hitting Set [SODA 2025]. We show that the cuts inducing a disjoint union of paths of length three (unions of so-called Z-cuts) lie at the core of the complexity of the problem - usually lower-bound constructions use simpler cuts inducing either a matching or a disjoint union of bicliques. Finally, we determine the optimal running times for Max Cut (2^{ctw} n^𝒪(1)) and Induced Matching (3^{ctw} n^𝒪(1)) by providing matching lower bounds for the existing algorithms - the latter result also answers an open question for treewidth by Chaudhary and Zehavi [WG 2023].
Cite as

Narek Bojikian, Vera Chekan, and Stefan Kratsch. Tight Bounds for Some Classical Problems Parameterized by Cutwidth. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bojikian_et_al:LIPIcs.ESA.2025.13,
  author =	{Bojikian, Narek and Chekan, Vera and Kratsch, Stefan},
  title =	{{Tight Bounds for Some Classical Problems Parameterized by Cutwidth}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.13},
  URN =		{urn:nbn:de:0030-drops-244815},
  doi =		{10.4230/LIPIcs.ESA.2025.13},
  annote =	{Keywords: Parameterized complexity, cutwidth, Hamiltonian cycle, triangle packing, max cut, induced matching}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.44
Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity

Authors: Koustav Bhanja and Asaf Petruschka

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We present a compact labeling scheme for determining whether a designated set of terminals in a graph remains connected after any f (or less) vertex failures occur. An f-FT Steiner connectivity labeling scheme for an n-vertex graph G = (V,E) with terminal set U ⊆ V provides labels to the vertices of G, such that given only the labels of any subset F ⊆ V with |F| ≤ f, one can determine if U remains connected in G-F. The main complexity measure is the maximum label length. The special case U = V of global connectivity has been recently studied by Jiang, Parter, and Petruschka [Yonggang Jiang et al., 2025], who provided labels of n^{1-1/f} ⋅ poly(f,log n) bits. This is near-optimal (up to poly(f,log n) factors) by a lower bound of Long, Pettie and Saranurak [Yaowei Long et al., 2025]. Our scheme achieves labels of |U|^{1-1/f} ⋅ poly(f, log n) for general U ⊆ V, which is near-optimal for any given size |U| of the terminal set. To handle terminal sets, our approach differs from [Yonggang Jiang et al., 2025]. We use a well-structured Steiner tree for U produced by a decomposition theorem of Duan and Pettie [Ran Duan and Seth Pettie, 2020], and bypass the need for Nagamochi-Ibaraki sparsification [Hiroshi Nagamochi and Toshihide Ibaraki, 1992].
Cite as

Koustav Bhanja and Asaf Petruschka. Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 44:1-44:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhanja_et_al:LIPIcs.ESA.2025.44,
  author =	{Bhanja, Koustav and Petruschka, Asaf},
  title =	{{Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{44:1--44:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.44},
  URN =		{urn:nbn:de:0030-drops-245123},
  doi =		{10.4230/LIPIcs.ESA.2025.44},
  annote =	{Keywords: Fault Tolerance, Labeling Schemes, Steiner Connectivity}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.15
Enumerating Minimal Dominating Sets and Variants in Chordal Bipartite Graphs

Authors: Emanuel Castelo, Oscar Defrain, and Guilherme C. M. Gomes

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

Abstract
Enumerating minimal dominating sets with polynomial delay in bipartite graphs is a long-standing open problem. To date, even the subcase of chordal bipartite graphs is open, with the best known algorithm due to Golovach, Heggernes, Kanté, Kratsch, Sæther, and Villanger running in incremental-polynomial time. We improve on this result by providing a polynomial delay and space algorithm enumerating minimal dominating sets in chordal bipartite graphs. Additionally, we show that the total and connected variants admit polynomial and incremental-polynomial delay algorithms, respectively, within the same class. This provides an alternative proof of a result by Golovach et al. for total dominating sets, and answers an open question for the connected variant. Finally, we give evidence that the techniques used in this paper cannot be generalized to bipartite graphs for (total) minimal dominating sets, unless P = NP, and show that enumerating minimal connected dominating sets in bipartite graphs is harder than enumerating minimal transversals in general hypergraphs.
Cite as

Emanuel Castelo, Oscar Defrain, and Guilherme C. M. Gomes. Enumerating Minimal Dominating Sets and Variants in Chordal Bipartite Graphs. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{castelo_et_al:LIPIcs.WADS.2025.15,
  author =	{Castelo, Emanuel and Defrain, Oscar and C. M. Gomes, Guilherme},
  title =	{{Enumerating Minimal Dominating Sets and Variants in Chordal Bipartite Graphs}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{15:1--15: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.15},
  URN =		{urn:nbn:de:0030-drops-242467},
  doi =		{10.4230/LIPIcs.WADS.2025.15},
  annote =	{Keywords: algorithmic enumeration, minimal dominating sets, connected dominating sets, total dominating sets, chordal bipartite graphs, sequential method, polynomial delay}
}
  • Refine by Type
  • 34 Document/PDF
  • 30 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 28 2025
  • 1 2022
  • 1 2020
  • 1 2019
  • Show More...

  • Refine by Author
  • 3 Kanté, Mamadou Moustapha
  • 3 Konrad, Christian
  • 3 Marino, Andrea
  • 3 Uno, Takeaki
  • 2 Beohar, Harsh
  • Show More...

  • Refine by Series/Journal
  • 32 LIPIcs
  • 2 OASIcs

  • Refine by Classification
  • 11 Mathematics of computing → Graph algorithms
  • 6 Theory of computation → Parameterized complexity and exact algorithms
  • 5 Mathematics of computing → Graph enumeration
  • 5 Theory of computation → Graph algorithms analysis
  • 3 Theory of computation → Modal and temporal logics
  • Show More...

  • Refine by Keyword
  • 3 Parameterized complexity
  • 2 Graph algorithms
  • 2 Hamiltonian cycle
  • 2 Streaming Algorithms
  • 2 polynomial delay
  • 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