A family of three-row boards shows that the unbounded ancestor chains handled by the algorithm are necessary even for optimal paintings, and a deterministic EPTAS and a randomized sampling variant with an explicit failure-probability bound are given.
Abstract
We give a deterministic algorithm for \textsc{Free-Flood-It} on rectangular grids $P_k\square P_n$ with at most three colors. For every fixed height $k$, it computes the minimum number of moves and an optimal sequence in $N^{O(k^2)}$ time, where $N=kn$. This resolves the previously open three-color case on complete $3\times n$ boards. The proof uses a representation of flooding strategies as paintings by connected regions. We show that an optimal painting can be chosen so that its regions form a rooted tree with strong restrictions on the colors along ancestral paths. These restrictions make the part of the tree visible in any fixed-size connected window admit only polynomially many descriptions. The remaining common ancestors may form an arbitrarily long chain. We retain that chain on a stack and use a finite context-free recurrence to minimize the total painting cost without enumerating all possible stack contents. Connectivity information at the boundary ensures that the resulting local descriptions assemble into one valid global painting. The argument also applies to graphs supplied with an ordering into connected layers of bounded size, provided every edge lies within one layer or joins consecutive layers. A family of three-row boards shows that the unbounded ancestor chains handled by the algorithm are necessary even for optimal paintings. For any fixed height and palette size, we also give a deterministic EPTAS and a randomized sampling variant with an explicit failure-probability bound. These approximation results use a separate algorithm with single-exponential dependence on the move budget.
We study the largest size $C(n)$ of a subset of the $n\times n$ integer grid containing no isosceles triple, including equally spaced collinear triples. We prove $C(n)=\Omega\left(n\sqrt{\log\log n/\log n}\right)$ by applying the sparse hypergraph coloring theorem of Cooper and Mubayi. Elementary geometry and primitive...
Finding large lattice subgraphs in sparse Erd\H{o}s--R\'enyi random graphs is a classical problem at the interface of random graph theory and algorithms. General bounded-degree embedding and universality theorems give powerful results for broad graph families, but when specialized to square grids they operate at densit...
Fix one colour class in the checkerboard colouring of an $n\times n$ integer grid, and let $M_4(n,\varepsilon)$ be the largest subset having at most two points in every row, column, and diagonal of slopes $\pm1$. We prove the near-saturation bound $M_4(n,\varepsilon)\leq2n-4$ for $n\geq6$. The proof uses first and seco...
Jujhar Aujla, T. Prellberg, Nirvair Sandhu· 1 citation
In this paper, we provide a novel approach to limiting Heesch numbers of a specific family of tiles. In particular, we show how a certain family of three--dimensional prisms has a finite Heesch number. In so doing, we initiate a structural study of ratio $q$ tilings by two prototiles, in which, loosely speaking, one ti...
Bansal, Huang, and Lee recently gave a polynomial-time algorithm that colors every $3$-colorable graph on $n$ vertices with $O(n^{0.19539})$ colors. We improve their bound to $O(n^{0.17794})$ colors. The improvement comes from a sharper rule for combining Gaussian covers. We prove the rule from Ehrhard's inequality by...
A majority C-colouring partitions a graph into classes in which every vertex has at least half of its neighbours. Write $M(G)$ for the maximum number of classes. We determine $M(K_q^{\square(2k+1)})=\left\lfloor\frac{q^{k+1}}{\lfloor q/2\rfloor+1}\right\rfloor\qquad(q\ge3,\ k\ge0).$ The lower bound follows from explici...
Ze-Hua Lu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.