Kacper Kluk

Maria Chudnovsky, Jadwiga Czyżewska, Kacper Kluk et al.

Many natural computational problems, including e.g. Max Weight Independent Set, Feedback Vertex Set, or Vertex Planarization, can be unified under an umbrella of finding the largest sparse induced subgraph, that satisfies some property definable in CMSO$_2$ logic. It is believed that each problem expressible with this formalism can be solved in polynomial time in graphs that exclude a fixed path as an induced subgraph. This belief is supported by the existence of a quasipolynomial-time algorithm by Gartland, Lokshtanov, Pilipczuk, Pilipczuk, and Rzążewski [STOC 2021], and a recent polynomial-time algorithm for $P_6$-free graphs by Chudnovsky, McCarty, Pilipczuk, Pilipczuk, and Rzążewski [SODA 2024]. In this work we extend polynomial-time tractability of all such problems to $P_7$-free graphs of bounded clique number.

Kacper Kluk, Hung Le, Wojciech Nadara et al.

A furthest neighbor data structure on a metric space $(V,\mathrm{dist})$ and a set $P \subseteq V$ answers the following query: given $v \in V$, output $p \in P$ maximizing $\mathrm{dist}(v,p)$; in the approximate version, it is allowed to report any $p \in P$ with $\mathrm{dist}(v,p) \geq (1-\varepsilon)\max_{p' \in P} \mathrm{dist}(v,p')$ for an accuracy parameter $\varepsilon \in (0,1)$. A particular type of approximate furthest neighbor data structure is an $\varepsilon$-coreset: a small subset $Q \subseteq P$ such that for every query $v \in V$ there is a feasible answer $p \in Q$. Our main result is that in planar metrics there always exists an $\varepsilon$-coreset for furthest neighbors of size bounded polynomially in $(1/\varepsilon)$. This improves upon an exponential bound of Bourneuf and Pilipczuk [SODA'25] and resolves an open problem of de Berg and Theocharous [SoCG'24] for the case of polygons with holes. On the technical side, we develop a connection between $\varepsilon$-coreset for furthest neighbors and an invariant of a metric space that we call an $\varepsilon$-comatching index -- a sibling of $\varepsilon$-(semi-)ladder index, a.k.a, $\varepsilon$-scatter dimension, as defined by Abbasi et al [FOCS'23]. While the $\varepsilon$-(semi-)ladder index of planar metrics admits an exponential lower bound, we show that the $\varepsilon$-comatching index of planar metrics is polynomial, all in $1/\varepsilon$. The exponential separation between $\varepsilon$-(semi-)ladder and $\varepsilon$-comatching is rather surprising, and the proof is the main technical contribution of our work.