Daniel Lokshtanov

Madhumita Kundu, Daniel Lokshtanov, Soumi Nandi et al.

Geometric covering problems ask for a small family of geometric objects whose union covers a given point set. We study the more restrictive \emph{boundary covering} variant, where every point must lie on the boundary of a chosen object. Motivated by the framework of Langerman and Morin\,[Discret.\ Comput.\ Geom., 2005] for hyperspheres, we initiate the study of boundary covering by axis-parallel rectangles. We first consider the \emph{discrete} setting, where rectangles must be selected from a given family. We define \bcdaprfull\ (\bcdaprshort): given a point set \(P\subseteq\mathbb{R}^2\), a family \(\mathcal{R}\) of axis-parallel rectangles, and an integer \(k\), decide whether \(P\) can be covered by the boundaries of at most \(k\) rectangles from \(\mathcal{R}\). We prove that \bcdaprshort\ is \(\mathrm{W}[1]\)-hard parameterized by \(k\). We then study the \emph{continuous} variant, \prbcfull\ (\prbcshort), where rectangles may be placed freely. Given \(P\subseteq\mathbb{R}^2\) and \(k\), the goal is to decide whether \(P\) can be covered by the boundaries of at most \(k\) axis-parallel rectangles. In contrast to the discrete case, we show that \prbcshort\ is fixed-parameter tractable, with running time \(2^{\cO(k\log k)}\cdot n^{\cO(1)}\), where \(n=|P|\). Our algorithm relies on a structural analysis of how \(k\) rectangles interact with the point set, reducing \prbcshort\ to at most \(2^{\cO(k\log k)}\) instances of \ddmtcsp, each solvable in polynomial time. On the hardness side, we prove NP-completeness for boundary covering by axis-aligned \(L\)-shapes and use this reduction to establish NP-completeness of \prbcshort.

Huairui Chu, Ajaykrishnan E S, Daniel Lokshtanov et al.

In the Rectangle Stabbing problem, input is a set ${\cal R}$ of axis-parallel rectangles and a set ${\cal L}$ of axis parallel lines in the plane. The task is to find a minimum size set ${\cal L}^* \subseteq {\cal L}$ such that for every rectangle $R \in {\cal R}$ there is a line $\ell \in {\cal L}^*$ such that $\ell$ intersects $R$. Gaur et al. [Journal of Algorithms, 2002] gave a polynomial time $2$-approximation algorithm, while Dom et al. [WALCOM 2009] and Giannopolous et al. [EuroCG 2009] independently showed that, assuming FPT $\neq$ W[1], there is no algorithm with running time $f(k)(|{\cal L}||{\cal R}|)^{O(1)}$ that determines whether there exists an optimal solution with at most $k$ lines. We give the first parameterized approximation algorithm for the problem with a ratio better than $2$. In particular we give an algorithm that given ${\cal R}$, ${\cal L}$, and an integer $k$ runs in time $k^{O(k)}(|{\cal L}||{\cal R}|)^{O(1)}$ and either correctly concludes that there does not exist a solution with at most $k$ lines, or produces a solution with at most $\frac{7k}{4}$ lines. We complement our algorithm by showing that unless FPT $=$ W[1], the Rectangle Stabbing problem does not admit a $(\frac{5}{4}-ε)$-approximation algorithm running in $f(k)(|{\cal L}||{\cal R}|)^{O(1)}$ time for any function $f$ and $ε> 0$.

Emmanuel Arrighi, Henning Fernau, Daniel Lokshtanov et al.

In its most traditional setting, the main concern of optimization theory is the search for optimal solutions for instances of a given computational problem. A recent trend of research in artificial intelligence, called solution diversity, has focused on the development of notions of optimality that may be more appropriate in settings where subjectivity is essential. The idea is that instead of aiming at the development of algorithms that output a single optimal solution, the goal is to investigate algorithms that output a small set of sufficiently good solutions that are sufficiently diverse from one another. In this way, the user has the opportunity to choose the solution that is most appropriate to the context at hand. It also displays the richness of the solution space. When combined with techniques from parameterized complexity theory, the paradigm of diversity of solutions offers a powerful algorithmic framework to address problems of practical relevance. In this work, we investigate the impact of this combination in the field of Kemeny Rank Aggregation, a well-studied class of problems lying in the intersection of order theory and social choice theory and also in the field of order theory itself. In particular, we show that the Kemeny Rank Aggregation problem is fixed-parameter tractable with respect to natural parameters providing natural formalizations of the notions of diversity and of the notion of a sufficiently good solution. Our main results work both when considering the traditional setting of aggregation over linearly ordered votes, and in the more general setting where votes are partially ordered.

Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov et al.

We provide a randomized linear time approximation scheme for a generic problem about clustering of binary vectors subject to additional constrains. The new constrained clustering problem encompasses a number of problems and by solving it, we obtain the first linear time-approximation schemes for a number of well-studied fundamental problems concerning clustering of binary vectors and low-rank approximation of binary matrices. Among the problems solvable by our approach are \textsc{Low GF(2)-Rank Approximation}, \textsc{Low Boolean-Rank Approximation}, and various versions of \textsc{Binary Clustering}. For example, for \textsc{Low GF(2)-Rank Approximation} problem, where for an $m\times n$ binary matrix $A$ and integer $r>0$, we seek for a binary matrix $B$ of $GF_2$ rank at most $r$ such that $\ell_0$ norm of matrix $A-B$ is minimum, our algorithm, for any $ε>0$ in time $ f(r,ε)\cdot n\cdot m$, where $f$ is some computable function, outputs a $(1+ε)$-approximate solution with probability at least $(1-\frac{1}{e})$. Our approximation algorithms substantially improve the running times and approximation factors of previous works. We also give (deterministic) PTASes for these problems running in time $n^{f(r)\frac{1}{ε^2}\log \frac{1}ε}$, where $f$ is some function depending on the problem. Our algorithm for the constrained clustering problem is based on a novel sampling lemma, which is interesting in its own.