Search Results

Documents authored by Wesolek, Alexandra

Document
DOI: 10.4230/LIPIcs.ESA.2026.77
Tree-Independence Number of P₅-Free Graphs with No Large Bicliques

Authors: Václav Blažej, J. Pascal Gollin, Tomáš Hons, Tomáš Masařík, Martin Milanič, Paweł Rzążewski, Ondřej Suchý, and Alexandra Wesolek

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
The tree-independence number of a graph is the minimum, over all tree-decompositions of the graph, of the maximum size of an independent set contained in a bag. Graph classes of bounded tree-independence number have strong structural and algorithmic properties, but the parameter can be unbounded even in quite restricted classes. In particular, the presence of an induced biclique K_{𝓁,𝓁} forces tree-independence number at least 𝓁. This leads to the question whether large induced bicliques are the only obstruction to bounded tree-independence number in natural hereditary classes. A conjecture of Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht states that for all positive integers t and 𝓁, {P_t,K_{𝓁,𝓁}}-free graphs have bounded tree-independence number. We prove this conjecture for t = 5 by showing that every {P₅,K_{𝓁,𝓁}}-free graph has tree-independence number at most 4𝓁. We also obtain related bounds for the weaker parameter of α-degeneracy.
Cite as

Václav Blažej, J. Pascal Gollin, Tomáš Hons, Tomáš Masařík, Martin Milanič, Paweł Rzążewski, Ondřej Suchý, and Alexandra Wesolek. Tree-Independence Number of P₅-Free Graphs with No Large Bicliques. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 77:1-77:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{blazej_et_al:LIPIcs.ESA.2026.77,
  author =	{Bla\v{z}ej, V\'{a}clav and Gollin, J. Pascal and Hons, Tom\'{a}\v{s} and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Milani\v{c}, Martin and Rz\k{a}\.{z}ewski, Pawe{\l} and Such\'{y}, Ond\v{r}ej and Wesolek, Alexandra},
  title =	{{Tree-Independence Number of P₅-Free Graphs with No Large Bicliques}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{77:1--77:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.77},
  URN =		{urn:nbn:de:0030-drops-272138},
  doi =		{10.4230/LIPIcs.ESA.2026.77},
  annote =	{Keywords: tree-independence number, independence degeneracy, independence treewidth, P₅-free graphs}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.22
Reconfiguration of Plane Trees in Convex Geometric Graphs

Authors: Nicolas Bousquet, Lucas de Meyer, Théo Pierron, and Alexandra Wesolek

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
A non-crossing spanning tree of a set of points in the plane is a spanning tree whose edges pairwise do not cross. Avis and Fukuda in 1996 proved that there always exists a flip sequence of length at most 2n-4 between any pair of non-crossing spanning trees (where n denotes the number of points). Hernando et al. proved that the length of a minimal flip sequence can be of length at least (3/2) n. Two recent results of Aichholzer et al. and Bousquet et al. improved the Avis and Fukuda upper bound by proving that there always exists a flip sequence of length respectively at most 2n-log n and 2n-√n when the points are in convex position. We pursue the investigation of the convex case by improving the upper bound by a linear factor for the first time in 30 years. We prove that there always exists a flip sequence between any pair of non-crossing spanning trees T₁,T₂ of length at most c n where c ≈ 1.95. Our result is actually stronger since we prove that, for any two trees T₁,T₂, there exists a flip sequence from T₁ to T₂ of length at most c |T₁ ⧵ T₂|. We also improve the best lower bound in terms of the symmetric difference by proving that there exists a pair of trees T₁,T₂ such that a minimal flip sequence has length (5/3) |T₁ ⧵ T₂|, improving the lower bound of Hernando et al. by considering the symmetric difference instead of the number of vertices. We generalize this lower bound construction to non-crossing flips (where we close the gap between upper and lower bounds) and rotations.
Cite as

Nicolas Bousquet, Lucas de Meyer, Théo Pierron, and Alexandra Wesolek. Reconfiguration of Plane Trees in Convex Geometric Graphs. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.SoCG.2024.22,
  author =	{Bousquet, Nicolas and de Meyer, Lucas and Pierron, Th\'{e}o and Wesolek, Alexandra},
  title =	{{Reconfiguration of Plane Trees in Convex Geometric Graphs}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.22},
  URN =		{urn:nbn:de:0030-drops-199673},
  doi =		{10.4230/LIPIcs.SoCG.2024.22},
  annote =	{Keywords: Reconfiguration, Non-crossing trees, flip distance}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.23
Maximum Independent Set When Excluding an Induced Minor: K₁ + tK₂ and tC₃ ⊎ C₄

Authors: Édouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé, and Alexandra Wesolek

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Dallard, Milanič, and Štorgel [arXiv '22] ask if, for every class excluding a fixed planar graph H as an induced minor, Maximum Independent Set can be solved in polynomial time, and show that this is indeed the case when H is any planar complete bipartite graph, or the 5-vertex clique minus one edge, or minus two disjoint edges. A positive answer would constitute a far-reaching generalization of the state-of-the-art, when we currently do not know if a polynomial-time algorithm exists when H is the 7-vertex path. Relaxing tractability to the existence of a quasipolynomial-time algorithm, we know substantially more. Indeed, quasipolynomial-time algorithms were recently obtained for the t-vertex cycle, C_t [Gartland et al., STOC '21], and the disjoint union of t triangles, tC₃ [Bonamy et al., SODA '23]. We give, for every integer t, a polynomial-time algorithm running in n^O(t⁵) when H is the friendship graph K₁ + tK₂ (t disjoint edges plus a vertex fully adjacent to them), and a quasipolynomial-time algorithm running in n^{O(t² log n) + f(t)}, with f a single-exponential function, when H is tC₃ ⊎ C₄ (the disjoint union of t triangles and a 4-vertex cycle). The former generalizes the algorithm readily obtained from Alekseev’s structural result on graphs excluding tK₂ as an induced subgraph [Alekseev, DAM '07], while the latter extends Bonamy et al.’s result.
Cite as

Édouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé, and Alexandra Wesolek. Maximum Independent Set When Excluding an Induced Minor: K₁ + tK₂ and tC₃ ⊎ C₄. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.ESA.2023.23,
  author =	{Bonnet, \'{E}douard and Duron, Julien and Geniet, Colin and Thomass\'{e}, St\'{e}phan and Wesolek, Alexandra},
  title =	{{Maximum Independent Set When Excluding an Induced Minor: K₁ + tK₂ and tC₃ ⊎ C₄}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.23},
  URN =		{urn:nbn:de:0030-drops-186769},
  doi =		{10.4230/LIPIcs.ESA.2023.23},
  annote =	{Keywords: Maximum Independent Set, forbidden induced minors, quasipolynomial-time algorithms}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.13
A Tight Local Algorithm for the Minimum Dominating Set Problem in Outerplanar Graphs

Authors: Marthe Bonamy, Linda Cook, Carla Groenland, and Alexandra Wesolek

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
We show that there is a deterministic local algorithm (constant-time distributed graph algorithm) that finds a 5-approximation of a minimum dominating set on outerplanar graphs. We show there is no such algorithm that finds a (5-ε)-approximation, for any ε > 0. Our algorithm only requires knowledge of the degree of a vertex and of its neighbors, so that large messages and unique identifiers are not needed.
Cite as

Marthe Bonamy, Linda Cook, Carla Groenland, and Alexandra Wesolek. A Tight Local Algorithm for the Minimum Dominating Set Problem in Outerplanar Graphs. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bonamy_et_al:LIPIcs.DISC.2021.13,
  author =	{Bonamy, Marthe and Cook, Linda and Groenland, Carla and Wesolek, Alexandra},
  title =	{{A Tight Local Algorithm for the Minimum Dominating Set Problem in Outerplanar Graphs}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.13},
  URN =		{urn:nbn:de:0030-drops-148159},
  doi =		{10.4230/LIPIcs.DISC.2021.13},
  annote =	{Keywords: Outerplanar graphs, dominating set, LOCAL model, constant-factor approximation algorithm}
}

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