The previous “some papers I liked” blog was published at the end of April, so I figured it was time to share some new papers I found informative, well-written, and interesting. As before, I am sharing only those that are quite short and don’t require very extensive background in any particular field (they should be understandable to a CS/Math undergraduate student).

Computational complexity theory#

  • Evolomino is NP-complete. Andrei V. Nikolaev, link (11 pages) — The author shows that the pencil-and-paper game Evolomino is NP-complete (and even #P-complete) using simple and elegant gadgets.

  • Battle Sheep is PSPACE-complete. Kyle Burke and Hirotaka Ono, link (10 pages) — another game, which turns out to be even harder.

Discrete mathematics#

  • Counterexamples to two conjectures on Venn diagrams. Sofia Brenner, Linda Kleist, et al., link (14 pages) — Focusing on Hamiltonian cycles in Venn diagrams, the authors use a combination of computer power and pure reasoning to find many counterexamples to two quite old conjectures.

  • Path Eccentricity and Forbidden Induced Subgraphs. Sylwia Cichacz, Claire Hilaire, et al., link (11 pages) — The authors, as the title states, consider path eccentricity (the minimum integer $k$ such that there is a path in a graph $G$ where every vertex is at distance at most $k$ from this path) in some specific graphs. Normally, I wouldn’t care that much about a paper on this topic, but the first author used to teach me some basic algebra in my first year of CS, so, out of curiosity, I decided to read the abstract. The abstract was interesting enough for me to read most of the paper, and it turned out to be surprisingly accessible.

Algorithms#

  • Space-Efficient Hierholzer. Ziad Ismaili Alaoui, Detlef Plump, Sebastian Wild, link (10 pages) — As the title states, it’s about finding Euler circuits using $\mathcal{O}(|V|)$ space instead of $\mathcal{O}(|E|)$. The algorithm is not too hard, and it’s explained very clearly.

  • An algorithm for accurate and simple-looking metaphorical maps. Eleni Katsanou, Tamara Mchedlidze, et al., link (15 pages) — The authors devise an algorithm that produces great visualizations of planar graphs with weighted vertices. I only skimmed through the algorithm itself, but I really appreciated the results they present in the paper. They also created a demo website.

Other#

As a bonus, a 600-page book titled Games on Graphs. The authors consider not only games in the classic sense, but also multiplayer, stochastic, concurrent, and infinite ones. It’s highly theoretical, but I actually see that as an advantage. The preface states that the book should be accessible to an advanced master’s or PhD student, but in the pages I had time to read I didn’t find anything really out of reach — though the later parts may be harder. Some background in graph theory and automata theory is surely beneficial, though.