DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2024.28

No Tiling of the 70 × 70 Square with Consecutive Squares

Authors: Jiří Sgall, János Balogh, József Békési, György Dósa, Lars Magnus Hvattum, and Zsolt Tuza

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract

The total area of the 24 squares of sizes 1,2,…,24 is equal to the area of the 70× 70 square. Can this equation be demonstrated by a tiling of the 70× 70 square with the 24 squares of sizes 1,2,…,24? The answer is "NO", no such tiling exists. This has been demonstrated by computer search. However, until now, no proof without use of computer was given. We fill this gap and give a complete combinatorial proof.

Cite as

Jiří Sgall, János Balogh, József Békési, György Dósa, Lars Magnus Hvattum, and Zsolt Tuza. No Tiling of the 70 × 70 Square with Consecutive Squares. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{sgall_et_al:LIPIcs.FUN.2024.28,
  author =	{Sgall, Ji\v{r}{\'\i} and Balogh, J\'{a}nos and B\'{e}k\'{e}si, J\'{o}zsef and D\'{o}sa, Gy\"{o}rgy and Hvattum, Lars Magnus and Tuza, Zsolt},
  title =	{{No Tiling of the 70 × 70 Square with Consecutive Squares}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.28},
  URN =		{urn:nbn:de:0030-drops-199362},
  doi =		{10.4230/LIPIcs.FUN.2024.28},
  annote =	{Keywords: square packing, Gardner’s problem, combinatorial proof}
}

Document

DOI: 10.4230/LIPIcs.IPEC.2016.3

H-Free Graphs, Independent Sets, and Subexponential-Time Algorithms

Authors: Gábor Bacsó, Dániel Marx, and Zsolt Tuza

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Abstract

It is an outstanding open question in algorithmic graph theory to determine the complexity of the MAXIMUM INDEPENDENT SET problem on P_t-free graphs, that is, on graphs not containing any induced path on t vertices. So far, polynomial-time algorithms are known only for t at most 5 [Lokshtanov et al., SODA 2014, 570-581, 2014]. Here we study the existence of subexponential-time algorithms for the problem: by generalizing an earlier result of Randerath and Schiermeyer for t=5 [Discrete App. Math., 158 (2010), 1041-1044], we show that for any t at least 5, there is an algorithm for MAXIMUM INDEPENDENT SET on P_t-free graphs whose running time is subexponential in the number of vertices. SCATTERED SET is the generalization of MAXIMUM INDEPENDENT SET where the vertices of the solution are required to be at distance at least $d$ from each other. We give a complete characterization of those graphs H for which SCATTERED SET on H-free graphs can be solved in time subexponential in the size of the input (that is, in the number of vertices plus the number of edges): * If every component of H is a path, then d-SCATTERED SET on H-free graphs with n vertices and m edges can be solved in time 2^{(n+m)^{1-O(1/|V(H)|)}}, even if d is part of the input. * Otherwise, assuming ETH, there is no 2^{o(n+m)} time algorithm for d-SCATTERED SET for any fixed d at least 3 on H-free graphs with n vertices and m edges.

Cite as

Gábor Bacsó, Dániel Marx, and Zsolt Tuza. H-Free Graphs, Independent Sets, and Subexponential-Time Algorithms. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bacso_et_al:LIPIcs.IPEC.2016.3,
  author =	{Bacs\'{o}, G\'{a}bor and Marx, D\'{a}niel and Tuza, Zsolt},
  title =	{{H-Free Graphs, Independent Sets, and Subexponential-Time Algorithms}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{3:1--3:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.3},
  URN =		{urn:nbn:de:0030-drops-69397},
  doi =		{10.4230/LIPIcs.IPEC.2016.3},
  annote =	{Keywords: independent set, scattered set, subexponential algorithms, H-free graphs}
}

Search Results

Documents authored by Tuza, Zsolt

No Tiling of the 70 × 70 Square with Consecutive Squares

Abstract

Cite as

H-Free Graphs, Independent Sets, and Subexponential-Time Algorithms

Abstract

Cite as

Thanks for your feedback!

Could not send message