Search

The Terrain Guarding problem is a well-known variant of the famous Art Gallery problem. Only second to Art Gallery, it is the most well-studied visibility problem in Discrete and Computational Geometry, which has also attracted attention from the viewpoint of Parameterized complexity. In this paper, we focus on the parameterized complexity of Terrain Guarding (both discrete and continuous) with respect to two natural parameters. First we show that, when parameterized by the number r of reflex vertices in the input terrain, the problem has a polynomial kernel. We also show that, when parameterized by the number c of minima in the terrain, Discrete Orthogonal Terrain Guarding has an XP algorithm. [ABSTRACT FROM AUTHOR]

The b-Exact Multicover problem takes a universe U of n elements, a family F of m subsets of U, a function dem : U → { 1 , ... , b } and a positive integer k, and decides whether there exists a subfamily(set cover) F ′ of size at most k such that each element u ∈ U is covered by exactly dem(u) sets of F ′ . The b-Exact Coverage problem also takes the same input and decides whether there is a subfamily F ′ ⊆ F such that there are at least k elements that satisfy the following property: u ∈ U is covered by exactly dem(u) sets of F ′ . Both these problems are known to be NP-complete. In the parameterized setting, when parameterized by k, b-Exact Multicover is W[1]-hard even when b = 1. While b-Exact Coverage is FPT under the same parameter, it is known to not admit a polynomial kernel under standard complexity-theoretic assumptions, even when b = 1. In this paper, we investigate these two problems under the assumption that every set satisfies a given geometric property π. Specifically, we consider the universe to be a set of n points in a real space ℝ d , d being a positive integer. When d = 2 we consider the problem when π requires all sets to be unit squares or lines. When d > 2, we consider the problem where π requires all sets to be hyperplanes in ℝ d . These special versions of the problems are also known to be NP-complete. When parameterized by k, the b-Exact Coverage problem has a polynomial size kernel for all the above geometric versions. The b-Exact Multicover problem turns out to be W[1]-hard for squares even when b = 1, but FPT for lines and hyperplanes. Further, we also consider the b-Exact Max. Multicover problem, which takes the same input and decides whether there is a set cover F ′ such that every element u ∈ U is covered by at least dem(u) sets and at least k elements satisfy the following property: u ∈ U is covered by exactly dem(u) sets of F ′ . To the best of our knowledge, this problem has not been studied before, and we show that it is NP-complete (even for the case of lines). In fact, the problem turns out to be W[1]-hard in the general setting, when parameterized by k. However, when we restrict the sets to lines and hyperplanes, we obtain FPT algorithms. [ABSTRACT FROM AUTHOR]

Given a graph G, a q-open neighborhood conflict-free coloring or q-ONCF-coloring is a vertex coloring c: V (G) \rightarrow \{ 1, 2, . . ., q\} such that for each vertex v \in V (G) there is a vertex in N(v) that is uniquely colored from the rest of the vertices in N(v). When we replace N(v) by the closed neighborhood N[v], then we call such a coloring a q-closed neighborhood conflict-free coloring or simply q-CNCF-coloring. In this paper, we study the NP-hard decision questions of whether for a constant q an input graph has a q-ONCF-coloring or a q-CNCF-coloring. We will study these two problems in the parameterized setting. First of all, we study running time bounds on fixed-parameter tractable algorithms for these problems when parameterized by treewidth. We improve the existing upper bounds, and also provide lower bounds on the running time under the exponential time hypothesis and the strong exponential time hypothesis. Second, we study the kernelization complexity of both problems, using vertex cover as the parameter. We show that both (q \geq 2)-ONCF-coloring and (q \geq 3)-CNCF-coloring cannot have polynomial kernels when parameterized by the size of a vertex cover unless \sansN \sansP \subseteq \sansc \sanso \sansN \sansP/\sansp \sanso \sansl \sansy. On the other hand, we obtain a polynomial kernel for 2-CNCF-coloring parameterized by vertex cover. We conclude the study with some combinatorial results. Denote \chi ON(G) and \chi CN(G) to be the minimum number of colors required to ONCF-color and CNCFcolor G, respectively. Upper bounds on \chi CN(G) with respect to structural parameters like minimum vertex cover size, minimum feedback vertex set size, and treewidth are known. To the best of our knowledge only an upper bound on \chi ON(G) with respect to minimum vertex cover size was known. We provide tight bounds for \chi ON(G) with respect to minimum vertex cover size. Also, we provide the first upper bounds on \chi ON(G) with respect to minimum feedback vertex set size and treewidth. [ABSTRACT FROM AUTHOR]

In the Graph bipartization (or Odd Cycle Transversal) problem, the objective is to decide whether a given graph G can be made bipartite by the deletion of k vertices for some given k. The parameterized complexity of Odd Cycle Transversal was resolved in the breakthrough paper of Reed, Smith and Vetta [Operations Research Letters, 2004], who developed an algorithm running in time O (3 k k m n). The question of improving the dependence on the input size to linear, which was another long standing open problem in the area, was resolved by Iwata et al. [SICOMP 2016] and Ramanujan and Saurabh [TALG 2017], who presented O (4 k (m + n)) and 4 k k O (1) (m + n) algorithms respectively. In this paper, we obtain a faster algorithm that runs in time 3 k k O (1) (m + n) and hence preserves the linear dependence on the input size while nearly matching the dependence on k incurred by the algorithm of Reed, Smith and Vetta. [ABSTRACT FROM AUTHOR]

Abstract A harmonious coloring of a graph is a partitioning of its vertex set into parts such that, there are no edges inside each part, and there is at most one edge between any pair of parts. It is known that finding a minimum harmonious coloring number is NP-hard even in special classes of graphs like trees and split graphs. We initiate a study of parameterized and exact exponential time complexity of harmonious coloring. We consider various parameterizations like by solution size, by above or below known guaranteed bounds and by the vertex cover number of the graph. While the problem has a simple quadratic kernel when parameterized by the solution size, our main result is that the problem is fixed-parameter tractable when parameterized by the size of a vertex cover of the graph. This is shown by reducing the problem to multiple instances of fixed variable integer linear programming. We also observe that it is W [ 1 ] -hard to determine whether at most n − k or Δ + 1 + k colors are sufficient in a harmonious coloring of an n -vertex graph G , where Δ is the maximum degree of G and k is the parameter. Concerning exact exponential time algorithms, we develop a 2 n n O (1) algorithm for finding a minimum harmonious coloring in split graphs improving on the naive 2 O (n log ⁡ n) algorithm. [ABSTRACT FROM AUTHOR]

In the study of parameterized streaming complexity on graph problems, the main goal is to design streaming algorithms for parameterized problems such that O (f (k) log O (1) n) space is enough, where f is an arbitrary computable function depending only on the parameter k. However, in the past few years very few positive results have been established. Most of the graph problems that do have streaming algorithms of the above nature are ones where localized checking is required, like Vertex Cover or Maximum Matching parameterized by the size k of the solution we are seeking. Chitnis et al. (SODA'16) have shown that many important parameterized problems that form the backbone of traditional parameterized complexity are known to require Ω (n) bits of storage for any streaming algorithm; e.g. Feedback Vertex Set, Even Cycle Transversal, Odd Cycle Transversal, Triangle Deletion or the more general F -Subgraph Deletion when parameterized by solution size k. Our contribution lies in overcoming the obstacles to efficient parameterized streaming algorithms in graph deletion problems by utilizing the power of parameterization. We focus on the vertex cover size K as the parameter for the parameterized graph deletion problems we consider. In this work, we consider the four most well-studied streaming models: the Ea, Dea, Va (vertex arrival) and Al (adjacency list) models. Surprisingly, the consideration of vertex cover size K in the different models leads to a classification of positive and negative results for problems like F -Subgraph Deletion and F -Minor Deletion. [ABSTRACT FROM AUTHOR]

In this paper, we focus on Hitting-Set , a fundamental problem in combinatorial optimization, through the lens of sublinear time algorithms. Given access to the hypergraph through a subset query oracle in the query model, we give sublinear time algorithms for Hitting-Set with almost tight parameterized query complexity. In parameterized query complexity , we estimate the number of queries to the oracle based on the parameter k , the size of the Hitting-Set. The subset query oracle we use in this paper is called Generalized d -partite Independent Set query oracle (GPIS) and it was introduced by Bishnu et al. (ISAAC'18). GPIS is a generalization to hypergraphs of the Bipartite Independent Set query oracle (BIS) introduced by Beame et al. (ITCS'18 and TALG'20) for estimating the number of edges in graphs. Since its introduction GPIS query oracle has been used for estimating the number of hyperedges independently by Dell et al. (SODA'20 and SICOMP'22) and Bhattacharya et al. (STACS'22), and for estimating the number of triangles in a graph by Bhattacharya et al. (ISAAC'19 and TOCS'21). Formally, GPIS is defined as follows: GPIS oracle for a d-uniform hypergraph H takes as input d pairwise disjoint non-empty subsets A 1 , ... , A d of vertices in H and answers whether there is a hyperedge in H that intersects each set A i , where i ∈ { 1 , 2 , ... , d }. For d = 2 , the GPIS oracle is nothing but BIS oracle. We show that d - Hitting-Set , the hitting set problem for d -uniform hypergraphs, can be solved using O ˜ d (k d log ⁡ n) GPIS queries. Additionally, we also showed that d - Decision-Hitting-Set , the decision version of d - Hitting-Set can be solved with O ˜ d (min ⁡ { k d log ⁡ n , k 2 d 2 }) GPIS queries. We complement these parameterized upper bounds with an almost matching parameterized lower bound that states that any algorithm that solves d - Decision-Hitting-Set requires Ω (( k + d d )) GPIS queries. [ABSTRACT FROM AUTHOR]

We investigate the parameterized complexity of Generalized Red Blue Set Cover ( Gen-RBSC), a generalization of the classic Set Cover problem and the more recently studied Red Blue Set Cover problem. Given a universe U containing b blue elements and r red elements, positive integers $$k_\ell $$ and $$k_r$$ , and a family $$\mathcal F $$ of $$\ell $$ sets over U, the Gen-RBSC problem is to decide whether there is a subfamily $$\mathcal F '\subseteq \mathcal F $$ of size at most $$k_\ell $$ that covers all blue elements, but at most $$k_r$$ of the red elements. This generalizes Set Cover and thus in full generality it is intractable in the parameterized setting. In this paper, we study a geometric version of this problem, called Gen-RBSC-lines, where the elements are points in the plane and sets are defined by lines. We study this problem for an array of parameters, namely, $$k_\ell , k_r, r, b$$ , and $$\ell $$ , and all possible combinations of them. For all these cases, we either prove that the problem is W-hard or show that the problem is fixed parameter tractable (FPT). In particular, on the algorithmic side, our study shows that a combination of $$k_\ell $$ and $$k_r$$ gives rise to a nontrivial algorithm for Gen-RBSC-lines. On the hardness side, we show that the problem is para-NP-hard when parameterized by $$k_r$$ , and W[1]-hard when parameterized by $$k_\ell $$ . Finally, for the combination of parameters for which Gen-RBSC-lines admits FPT algorithms, we ask for the existence of polynomial kernels. We are able to provide a complete kernelization dichotomy by either showing that the problem admits a polynomial kernel or that it does not contain a polynomial kernel unless $$\text {co{-}NP}\subseteq \text {NP}/\text{ poly }$$ . [ABSTRACT FROM AUTHOR]

Let $${\mathcal {F}}$$ be a family of graphs. Given an n-vertex input graph G and a positive integer k, testing whether G has a vertex subset S of size at most k, such that $$G-S$$ belongs to $${\mathcal {F}}$$ , is a prototype vertex deletion problem. These type of problems have attracted a lot of attention in recent times in the domain of parameterized complexity. In this paper, we study two such problems; when $${\mathcal {F}}$$ is either the family of forests of cacti or the family of forests of odd-cacti. A graph H is called a forest of cacti if every pair of cycles in H intersect on at most one vertex. Furthermore, a forest of cacti H is called a forest of odd cacti, if every cycle of H is of odd length. Let us denote by $${\mathcal {C}}$$ and $${{\mathcal {C}}}_\mathsf{odd}$$ , the families of forests of cacti and forests of odd cacti, respectively. The vertex deletion problems corresponding to $${\mathcal {C}}$$ and $${{\mathcal {C}}}_\mathsf{odd}$$ are called Diamond Hitting Set and Even Cycle Transversal, respectively. In this paper we design randomized algorithms with worst case run time $$12^k n^{\mathcal {O}(1)}$$ for both these problems. Our algorithms considerably improve the running time for Diamond Hitting Set and Even Cycle Transversal, compared to what is known about them. [ABSTRACT FROM AUTHOR]

We study the parameterized complexity of Minimum Volume Packing and Strip Packing . In the two dimensional version the input consists of a set of rectangles S with integer side lengths. In the Minimum Volume Packing problem, given a set of rectangles S and a number k , the goal is to decide if the rectangles can be packed in a bounding box of volume at most k . In the Strip Packing problem we are given a set of rectangles S , numbers W and k ; the objective is to find if all the rectangles can be packed in a box of dimensions W × k . We prove that the 2-dimensional Volume Packing is in FPT by giving an algorithm that runs in ( 2 ⋅ 2 ) k ⋅ k O ( 1 ) time. We also show that Strip Packing is W[1]-hard even in two dimensions and give an FPT algorithm for a special case of Strip Packing . Some of our results hold for the problems defined in higher dimensions as well. [ABSTRACT FROM AUTHOR]

An undirected graph is said to be split if its vertex set can be partitioned into two sets such that the subgraph induced on one of them is a complete graph and the subgraph induced on the other is an independent set. We initiate a systematic study of parameterized complexity of the problem of deleting the minimum number of vertices or edges from a given input graph so that the resulting graph is split. We give efficient fixed-parameter algorithms and polynomial sized kernels for the problem. More precisely, In addition, we note that our algorithm for Split Edge Deletion adds to the small number of subexponential parameterized algorithms not obtained through bidimensionality (Demaine et al. in J. ACM 52(6): 866-893, ), and on general graphs. [ABSTRACT FROM AUTHOR]

We study the Steiner Tree problem on unit disk graphs. Given a n vertex unit disk graph G, a subset R ⊆ V (G) of t vertices and a positive integer k, the objective is to decide if there exists a tree T in G that spans over all vertices of R and uses at most k vertices from V \ R . The vertices of R are referred to as terminals and the vertices of V (G) \ R as Steiner vertices. First, we show that the problem is NP-hard. Next, we prove that the Steiner Tree problem on unit disk graphs can be solved in n O (t + k) time. We also show that the Steiner Tree problem on unit disk graphs parameterized by k has an FPT algorithm with running time 2 O (k) n O (1) . In fact, the algorithms are designed for a more general class of graphs, called clique-grid graphs Fomin (Discret. Comput. Geometry 62(4):879–911, 2019). We mention that the algorithmic results can be made to work for Steiner Tree problem on disk graphs with bounded aspect ratio. Finally, we prove that Steiner Tree problem on disk graphs parameterized by k, is W[1]-hard. [ABSTRACT FROM AUTHOR]

We study exact algorithms for Metric TSP in Rd. In the early 1990s, algorithms with nO(\surd n) running time were presented for the planar case, and some years later an algorithm with nO(n1 1/d) running time was presented for any d \geqslant 2. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on Metric TSP, except for a lower bound stating that the problem admits no 2o(n1 1/d) algorithm unless ETH fails. In this paper we settle the complexity of Metric TSP, up to constant factors in the exponent and under ETH, by giving an algorithm with running time 2O(n1 1/d). [ABSTRACT FROM AUTHOR]

Conflict-free coloring of hypergraphs is a very well studied question of theoretical and practical interest. For a hypergraph H = (U,F), a conflict-free coloring of H refers to a vertex coloring where every hyperedge has a vertex with a unique color, distinct from all other vertices in the hyperedge. In this paper, we initiate a study of a natural maximization version of this problem, namely, Max-CFC: For a given hypergraph H and a fixed r = 2, color the vertices of U using r colors so that the number of hyperedges that are conflict-free colored is maximized. By previously known hardness results for conflict-free coloring, this maximization version is NPhard. We study this problem in the context of both exact and parameterized algorithms. In the parameterized setting, we study this problem with respect to a natural parameter--the solution size. In particular, the question we study is the following: p-CFC: For a given hypergraph, can we conflict-free color at least k hyperedges with at most r colors, the parameter being the solution size k. We show that this problem is fixed parameter tractable by designing an algorithm with running time 2O(k log log k+k log r)(n + m)O(1) using a novel connection to the Unique Coverage problem and applying the method of color coding in a nontrivial manner. For the special case for hypergraphs induced by graph neighborhoods we give a polynomial kernel. Finally, we give an exact algorithm for Max-CFC running in O(2n+m) time. All our algorithms, with minor modifications, work for a stronger version of conflict-free coloring, Unique Maximum Coloring. [ABSTRACT FROM AUTHOR]