Édouard Bonnet
email: edouard.bonnet@ens-lyon.fr

Parameterized Hardness of Art Gallery Problems

Keywords: CCS Concepts:, Randomness, geometry and discrete structures → Computational geometry;, Design and analysis Computational Geometry, Art Gallery, Parameterized Complexity, Intractability, ETH lower bound

Given a simple polygon P on n vertices, two points x, y in P are said to be visible to each other if the line segment between x and y is contained in P. The Point Guard Art Gallery problem asks for a minimum set S such that every point in P is visible from a point in S. The Vertex Guard Art Gallery problem asks for such a set S subset of the vertices of P. A point in the set S is referred to as a guard. For both variants, we rule out any f (k)n o(k /log k ) algorithm, where k := |S | is the number of guards, for any computable function f , unless the Exponential Time Hypothesis fails. These lower bounds almost match the n O (k ) algorithms that exist for both problems.

INTRODUCTION

Two points x, y in a simple polygon P are said to be visible to each other if the line segment between x and y is contained in P. The Point Guard Art Gallery problem asks for a minimum set S such that every point in P is visible from a point in S. The Vertex Guard Art Gallery problem asks for such a set S subset of the vertices of P. In both cases, such a set S is a guarding set and its elements are called guards. In the decision versions, given a simple polygon and an integer, one has to decide if there is a guarding set for the polygon of cardinality at most the integer. In what follows, n refers to the number of vertices of P and k to the allowed number of guards.

The art gallery problem is arguably one of the most well-known problems in discrete and computational geometry. Since its introduction by Viktor Klee in 1976, numerous research papers were published on the subject. O'Rourke's early book from 1987 [START_REF] O'rourke | Art gallery theorems and algorithms[END_REF] has over two thousand citations, and each year, top conferences publish new results on the topic. Many variants of the art gallery problem, based on different definitions of visibility, restricted classes of polygons, different 1:2 Édouard Bonnet and Tillmann Miltzow shapes of guards, have been defined and analyzed. One of the first results is the elegant proof of Fisk that ⌊n/3⌋ guards are always sufficient and sometimes necessary for a polygon with n vertices [START_REF] Fisk | A short proof of Chvátal's watchman theorem[END_REF].

The art gallery problem was shown NP-hard by Aggarwal in his PhD thesis [START_REF]The art gallery theorem: its variations, applications and algorithmic aspects[END_REF] and by Lee and Lin [START_REF] Lee | Computational complexity of art gallery problems[END_REF]. Eidenbenz et al. [START_REF] Eidenbenz | Inapproximability results for guarding polygons and terrains[END_REF] even showed APX-hardness for the most standard variants. See also [START_REF] Brodén | Guarding lines and 2-link polygons is apx-hard[END_REF][START_REF] Katz | On guarding the vertices of rectilinear domains[END_REF][START_REF] Krohn | Approximate guarding of monotone and rectilinear polygons[END_REF] for other hardness constructions. Very recently, Abrahamsen et al. [START_REF] Abrahamsen | The art gallery problem is ∃R-complete[END_REF] showed that Point Guard Art Gallery is ∃R-complete. In particular, this problem is unlikely to be in NP. This is maybe intuitive, if we consider simple instances of the art gallery problem, which need irrational numbers for an optimal guard placement [START_REF] Abrahamsen | Irrational guards are sometimes needed[END_REF]. In contrast, Dobbins, Holmsen and Miltzow [START_REF] Dobbins | Smoothed analysis of the art gallery problem[END_REF] showed how to find a solution with rational coordinates using the concept of smoothed analysis. Due to those negative results, most papers focus on finding approximation algorithms and on variants or restrictions that are polynomially tractable [START_REF] Ghosh | Approximation algorithms for art gallery problems in polygons[END_REF][START_REF] King | Fast vertex guarding for polygons with and without holes[END_REF][START_REF] Kirkpatrick | An O (lдlдO PT )-approximation algorithm for multi-guarding galleries[END_REF][START_REF] Krohn | Approximate guarding of monotone and rectilinear polygons[END_REF][START_REF] Motwani | Covering orthogonal polygons with star polygons: The perfect graph approach[END_REF]. For the Point Guard Art Gallery problem on simple polygons, there is an O(log OPT)-approximation under some assumptions (integer coordinates and some special general position of the vertices) [START_REF] Bonnet | An approximation algorithm for the art gallery problem[END_REF]. The approximation relies on the construction of ε-nets and ideas from Efrat and Har-Peled [START_REF] Efrat | Guarding galleries and terrains[END_REF]. For polygons with h holes, there is a polynomial approximation algorithm with ratio O(log OPT • log h) which guards all but a δ -fraction of the polygon [START_REF] Elbassioni | Finding small hitting sets in infinite range spaces of bounded vc-dimension[END_REF]. Recently, a constant-factor approximation was announced for Vertex Guard Art Gallery [START_REF] Bhattacharya | Constant approximation algorithms for guarding simple polygons using vertex guards[END_REF]. However, a mistake was later found [START_REF] Ashur | A Constant-Factor Approximation Algorithm for Vertex Guarding a WV-Polygon[END_REF]. Another approach is to find heuristics to solve large instances of the art gallery problem [START_REF] De Rezende | Engineering art galleries[END_REF]. Naturally, the fundamental drawback of this approach is the lack of performance guarantees.

In the last twenty-five years, another fruitful approach gained popularity: parameterized complexity. The underlying idea is to study algorithmic problems with dependence on a natural parameter.

If the dependence on the parameter is practical and the parameter is small for real-life instances, we attain algorithms that give optimal solutions with reasonable running times. For a gentle introduction to parameterized complexity, we recommend Niedermeier's book [START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF]. For a thorough reading highlighting complexity classes, we suggest the book by Downey and Fellows [START_REF] Downey | Parameterized complexity[END_REF]. For a recent book on the topic with an emphasis on algorithms, we advise to read the book by Cygan et al. [START_REF] Cygan | Parameterized Algorithms[END_REF]. An approach based on logic is given by Flum and Grohe [START_REF] Flum | Parameterized complexity theory, volume XIV of texts in theoretical computer science[END_REF]. Despite the recent successes of parameterized complexity, only very few results on the art gallery problem are known prior to this paper.

The first such result is the trivial algorithm for the vertex guard variant to check if a solution of size k exists in a polygon with n vertices. The algorithm runs in O(n k +2 ) time, by checking all possible subsets of size k of the vertices. The second not so well-known result is the fact that one can find in time n O (k ) a set of k guards for the point guard variant, if it exists [START_REF] Efrat | Guarding galleries and terrains[END_REF], using tools from real algebraic geometry [START_REF] Basu | Algorithms in real algebraic geometry[END_REF]. This was first observed by Sharir [START_REF] Efrat | Guarding galleries and terrains[END_REF]Acknowledgment]. Despite the fact that the first algorithm is extremely basic and the second algorithm, even with remarkably sophisticated tools, uses almost no problem specific insights, no better exact parameterized algorithms are known.

The Exponential Time Hypothesis (ETH) asserts that there is no 2 o(N ) time algorithm for Sat on N variables. The ETH is used to attain more precise conditional lower bounds than the mere NPhardness. A simple reduction from Set Cover by Eidenbenz et al. shows that there is no f (k)n o (k ) algorithm for these problems, when we consider polygons with holes [START_REF] Eidenbenz | Inapproximability results for guarding polygons and terrains[END_REF]Sec.4], unless the ETH fails. However, polygons with holes are very different from simple polygons. For instance, they have unbounded VC-dimension while simple polygons have bounded VC-dimension [START_REF] Gibson | The VC-dimension of visibility on the boundary of a simple polygon[END_REF][START_REF] Gilbers | A new upper bound for the VC-dimension of visibility regions[END_REF][START_REF] Kalai | Guarding galleries where every point sees a large area[END_REF][START_REF] Valtr | Guarding galleries where no point sees a small area[END_REF].

We present the first lower bounds for the parameterized art gallery problems restricted to simple polygons. Here, the parameter is the optimal number k of guards to cover the polygon. Theorem 1.1 (Parameterized hardness point guard). Point Guard Art Gallery is not solvable in time f (k)n o(k /log k ) , even on simple polygons, where n is the number of vertices of the polygon and k is the number of guards allowed, for any computable function f , unless the ETH fails.

Parameterized Hardness of Art Gallery Problems 1:3 Theorem 1.2 (Parameterized hardness vertex guard). Vertex Guard Art Gallery is not solvable in time f (k)n o(k /log k ) , even on simple polygons, where n is the number of vertices of the polygon and k is the number of guards allowed, for any computable function f , unless the ETH fails.

These results imply that the previous noted algorithms are essentially tight, and suggest that there are no significantly better parameterized algorithms. Our reductions are from Subgraph Isomorphism and therefore an f (k)n o(k ) -algorithm for the art gallery problem would also imply improved algorithms for Subgraph Isomorphism and for CSP parameterized by treewidth, which would be considered a major breakthrough [START_REF] Marx | Can you beat treewidth?[END_REF]. Let us also mention that our results imply that both variants are W [1]-hard parameterized by the number of guards.

After the conference version of this paper appeared, the parameterized complexity of the art gallery and related problems was investigated further. The parameterized complexity of the terrain guarding problem was studied [START_REF] Ashok | Exact algorithms for terrain guarding[END_REF]. The terrain guarding problem is a particular case of the art gallery problem, where instead of a polygon, one should guard an x-monotone curve. This restriction is still NP-hard [START_REF] King | Terrain Guarding is NP-Hard[END_REF], even on rectilinear (that is, every edge is horizontal or vertical) terrains [START_REF] Bonnet | Orthogonal Terrain Guarding is NP-complete[END_REF]. The authors of [START_REF] Ashok | Exact algorithms for terrain guarding[END_REF] present an n O ( √ k ) -time algorithm (hence 2 O (n 1/2 log n) ) for guarding general n-vertex terrains with k guards, and an FPT k O (k ) n O (1) -time algorithm for guarding the vertices of rectilinear terrains. Note that there is no 2 o(n 1/3 ) algorithm for terrain guarding, unless the ETH fails [START_REF] Bonnet | Orthogonal Terrain Guarding is NP-complete[END_REF].

The art gallery problem parameterized by the number of reflex vertices is considered by Agrawal et al. [START_REF] Agrawal | The Parameterized Complexity of Guarding Almost Convex Polygons[END_REF]. The authors present an FPT algorithm for Vertex Guard Art Gallery under this parameterization. See also [START_REF] Agrawal | FPT Algorithms for Conflict-free Coloring of Graphs and Chromatic Terrain Guarding[END_REF] for FPT algorithms on the (strong) conflict-free coloring of terrains.

PROOF IDEAS

In order to achieve these results, we slightly extend some known hardness results of geometric set cover/hitting set problems and combine them with problem-specific insights of the art gallery problem. One of the first problem-specific insights is the ability to encode Hitting Set on interval graphs. The reader can refer to Figure 1 for the following description. Assume that we have some fixed points p 1 , . . . , p n with increasing y-coordinates in the plane. We can build a pocket "far enough to the right" that can be seen only from {p i , . . . , p j } for any 1 ⩽ i < j ⩽ n. Let I 1 , . . . , I n be n intervals with endpoints a 1 , . . . , a 2n . Then, we construct 2n points p 1 , . . . , p 2n representing a 1 , . . . , a 2n . Further, we construct one pocket "far enough to the right" for each interval as described above. This way, we reduce Hitting Set on interval graphs to a restricted version of the art gallery problem. This observation is not so useful in itself since Hitting Set on interval graphs can be solved in polynomial time. The situation changes rapidly if we consider Hitting Set on 2-track interval graphs, as described in the preliminaries. Unfortunately, we are not able to just "magically" link (see Figure 2) some specific pairs of points in the polygon of the art gallery instance. Instead, we construct linking gadgets, which work "morally" as follows. We are given two set of points P and Q and a bijection σ between P and Q. The linking gadget is built in a way that it can be covered by two points (p, q) of P × Q, if and only if q = σ (p). The Structured 2-Track Hitting Set problem will be specifically designed so that the linking gadget is the main remaining ingredient to show hardness.

This intermediate problem is a convenient starting point for parameterized reductions to other geometric problems. For instance, the parameterized hardness of Red-Blue Points Separation, where given a set of blue points and a set of red points in the plane, one has to find at most k lines so that no cell of the arrangement is bichromatic, was obtained by a reduction from Structured 2-Track Hitting Set [START_REF] Bonnet | On the parameterized complexity of red-blue points separation[END_REF].

Organization. The rest of the paper is organized as follows. In Section 3, we introduce some notations, discuss the encoding of the polygon, give some useful ETH-based lower bounds, and prove a technical lemma. In Section 4, we prove the lower bound for Structured 2-Track Hitting Set (Theorem 4.2). Lemma 4.1 contains the key arguments. From this point onward, we can reduce from Structured 2-Track Hitting Set. In Section 5, we show the lower bound for the Point Guard Art Gallery problem (Theorem 1.1). We design a linking gadget, show its correctness, and show how several linking gadgets can be combined consistently. In Section 6, we tackle the Vertex Guard Art Gallery problem (Theorem 1.2). We have to design a very different linking gadget, that has to be combined with other gadgets and ideas.

PRELIMINARIES

For any two integers x ⩽ y, we set [x, y] := {x, x + 1, . . . , y -1, y}, and for any positive integer Parameterized Hardness of Art Gallery Problems 1:5

Given n points v 1 , . . . , v n ∈ R 2 , we define a polygonal closed curve c by seg(v 1 , v 2 ), . . . , seg(v n-1 , v n ), seg(v n , v 1

Vertex Guard Art Gallery

Input: A simple polygon P on n vertices in the plane and a natural number k.

Question: Does there exist a set of k vertex guards for P?

For any two distinct points v and w in the plane we denote by ray(v, w) the ray starting at v and passing through w, and by ℓ(v, w) the supporting line passing through v and w. For any point x in a polygon P, V P (x), or simply V (x), denotes the visibility region of x within P, that is the set of all the points y ∈ P seen by x. We say that two vertices v and w of a polygon P are neighbors or consecutive if vw is an edge of P. A sub-polygon P ′ of a simple polygon P is defined by any l distinct consecutive vertices v 1 , v 2 , . . . , v l of P (that is, for every i ∈ [l -1], v i and v i+1 are neighbors in P) such that v 1 v l does not cross any edge of P. In particular, P ′ is a simple polygon.

Encoding. We assume that the vertices of the polygon are either given by integers or by rational numbers. We also assume that the output is given either by integers or by rational numbers. The instances we generate as a result of Theorem 1.1 and Theorem 1.2 have rational coordinates. We can represent each coordinate by specifying the nominator and denominator. The number of bits is bounded by O(log n) in both cases. We can transform the coordinates to integers by multiplying every coordinate with the least common multiple of all denominators. However, this leads to integers using O(n log n) bits.

ETH-based lower bounds. The Exponential Time Hypothesis (ETH) is a conjecture by Impagliazzo et al. [START_REF] Impagliazzo | Complexity of k-SAT[END_REF] asserting that there is no 2 o(n) -time algorithm for 3-SAT on instances with n variables.

The k-Multicolored-Cliqe problem has as input a graph G = (V , E), where the set of vertices is

partitioned into V 1 , . . . , V k . It asks if there exists a set of k vertices v 1 ∈ V 1 , . . . , v k ∈ V k such that
these vertices form a clique of size k. We will use the following lower bound proved by Chen et al. [START_REF] Chen | Strong computational lower bounds via parameterized complexity[END_REF].

Theorem 3.1 ([14]

). There is no f (k)n o(k ) algorithm for k-Multicolored-Clique, for any computable function f , unless the ETH fails.

(k)n o(k /log k )
where k is the number of edges of the solution, for any computable function f , unless the ETH fails.

Naturally, this result still holds when restricted to connected input graphs. In that case, k ⩾ l -1.

Bounding the coordinates. We say a point p = (p x , p y ) ∈ Z 2 has coordinates bounded by

L if |p x |, |p y | ⩽ L.
Given two vectors v, w, we denote their scalar product as v • w. This technical lemma will prove useful to ensure that the polygon built in Section 5 can be described with integer coordinates.

Lemma 3.3. Let p 1 , q 1 , p 2 , q 2 be four points with integer coordinates bounded by L. Then the intersection point d = (d x , d y ) of the supporting lines ℓ 1 = ℓ(p 1 , q 1 ) and ℓ 2 = ℓ(p 2 , q 2 ) is a rational point.

The nominator and denominator of d x and d y are bounded by O(L 2 ).

Proof. The fact that d lies on ℓ i can be expressed as v i • d = b i , with some appropriate vector v i and number b i , for i = 1, 2. To be precise v i = (-p i x + q i x , p i y -q i y ) and b i = v i • p i , for i = 1, 2. We define the matrix A = (v1 , v 2 ) and the vector b = (b 1 , b 2 ). Then both conditions can be expressed as A • d = b. We denote by A i the matrix i with the i-th column replaced by b. And by det(M) the determinant of the matrix M. By Cramer's rule, it holds that d x = det(A 1 ) det(A) and d y = det(A 2 ) det(A) . □

PARAMETERIZED HARDNESS OF STRUCTURED 2-TRACK HITTING SET

The purpose of this section is to show Theorem 4.2. As we will see at the end of the section, there already exist quite a few parameterized hardness results for set cover/hitting set problems restricted to instances with some geometric flavor. The crux of the proof of Theorem 4.2 lies in Lemma 4.1.

We introduce a few notation and vocabulary to state and prove this lemma.

Given a finite totally ordered set Y = {y 1 , . . . , Given a set S of subsets of X , k-Set Cover asks to find k sets of S whose union is X . We first show an ETH lower bound and W[1]-hardness for k-Set Cover restricted to two-block instances.

y |Y | } (that is, for any i, j ∈ [|Y |], y i ≤ y j iff i ⩽ j), a subset S ⊆ Y is a Y -interval if S = {y | y i ≤ y ≤ y j }
We reduce from Multicolored k-Cliqe for simplicity sake (then from Multicolored Subgraph Isomorphism to improve the ETH lower bound). On a high-level, we encode adjacencies in the Multicolored k-Cliqe instance by pairs of disjoint sets particularly effective to cover X . On the contrary, pairs of non-adjacent vertices will be mapped to pairs of sets overlapping and missing an important part of X . This trick will be a recurring theme throughout the paper.

G = (V 1 ∪ . . . ∪ V k , E) be an instance of Multicolored k-Cliqe with V = i ∈[k ] V i , ∀i ∈ [k], V i = {v i 1 , . . . , v i t }, m = |E|, and n = |V | = tk. For each pair i < j ∈ [k] 1 , E i j denotes the set of edges E(V i , V j ) between V i and V j .
For each E i j we give an arbitrary order to the edges: e i j 1 , . . . , e i j |E i j | . We build an equivalent instance (X , S) of k-Set Cover with 4 k 2 + 4m + tk(k + 1) + 4k elements and 4m + 2kt sets, and such that (X , S) is two-block. We call A and B the two sets of the partition of X that realizes that (X , S) is two-block.

For each of the color class V i , we add tk + 2 elements to A with the following order:

x b (i), x(i, 1, 1), . . . , x(i, 1, t),
x(i, 2, 1), . . . , x(i, 2, t), . . .

x(i, i -1, 1), . . . , x(i, i -1, t), x(i, i + 1, 1), . . . , x(i, i + 1, t), . . . x(i, k + 1, 1), . . . , x(i, k + 1, t),
x e (i),

Parameterized Hardness of Art Gallery Problems 1:7

and call X (i) the set containing those elements. We also set

X (i, j) := {x(i, j, 1), x(i, j, 2), . . . , x(i, j, t)} (hence, X (i) = j i X (i, j) ∪ {x b (i), x e (i)}).
For each E i j , we add to B the 3|E i j | + 2 of a set Y (i, j) ordered: y b (i, j), y(i, j, 1), . . . , y(i, j, 3|E i j |), y e (i, j).

For each pair i < j ∈ [k] and for each edge

e i j c = v i a v j b in E i j (with a, b ∈ [t] and c ∈ [|E i j |]
), we add to S the two sets S(e i j c , v i a ) := {x(i, j, a), x(i, j, a + 1), . . . , x(i, j, t), x(i, j + 1, 1), . . . , x(i, j + 1, a -1)} ∪ {y(i, j, c), . . . , y(i, j, c

+ |E i j | -1)} and S(e i j c , v j b ) := {x(j, i, b), x(j, i, b + 1), . . . , x(j, i, t), x(j, i + 1, 1), . . . x(j, i + 1, b -1)} ∪ {y(i, j, c + |E i j |), . . . , y(i, j, c + 2|E i j | -1)}.
Observe that in case j = i + 1, then all the elements of the form x(j, i + 1, •) in set S(e i j c , v j b ) are in fact of the form x(j, i + 2, •). We may also notice that in case a = 1 (resp. b = 1), then there is no element of the form x(i, j

+ 1, •) (resp. x(j, i + 1, •)) in set S(e i j c , v i a ) (resp. in set S(e i j c , v j b )). For each pair i < j ∈ [k], we also add to A the |E i j | + 2 elements of a set Z (i, j) ordered: z b (i, j), z(i, j, 1), . . . , z(i, j, |E i j |), z e (i, j),
and for each edge e i j c in E i j (with c ∈ [|E i j |]), we add to S the two sets S(e i j c , ⊢) = {z b (i, j), z(i, j, 1), . . . , z(i, j, |E i j | -c} ∪ {y b (i, j), y(i, j, 1) . . . y(i, j, c -1)} and S(e i j c , ⊣) = {z(i, j, |E i j | -c + 1), . . . , z(i, j, |E i j |, z e (i, j)} ∪ {y(i, j, c + 2|E i j |) . . . y(i, j, 3|E i j |)
, y e (i, j)}. Finally, for each i ∈ [k], we add to B the t + 2 elements of a set W (i) ordered: w b (i), w(i, 1), . . . , w(i, t), w e (i), and for all a ∈ [t], we add the sets

S(i, a, ⊢) := {x b (i), x(i, 1, 1), . . . , x(i, 1, a -1)} ∪ {w b (i), w(i, 1), . . . , w(i, t -a + 1)} and S(i, a, ⊣) := {x(i, k + 1, a), . . . , x(i, k + 1, t), x e (i)} ∪ {w(i, t -a + 2), . . . , w(i, t), w e (i)}.
No matter the order in which we put the X (i)'s and Z (i, j)'s in A (respectively the Y (i, j)'s and W (i)'s in B), the sets we defined are all unions of an A-interval with a B-interval, provided we keep the elements within each X (i), Z (i, j), Y (i, j), and W (i) consecutive (and naturally, in the order we specified). Though, to clarify the construction, we fix the following orders for A and for B:

X (1), . . . , X (k), Z (1, 2), . . . , Z (1, k), Z (2, 3), . . . , Z (2, k), . . . , Z (k -2, k -1), Z (k -2, k), Z (k -1, k) Y (1, 2), . . . , Y (1, k), Y (2, 3), . . . , Y (2, k), . . . , Y (k -2, k -1), Y (k -2, k), Y (k -1, k),W (1), . . . ,W (k).
We ask for a set cover with 2k2 sets. This ends the construction (see Figure 4 for an illustration of the construction for the instance graph of Figure 3).

For each i ∈ [k], let us denote by S b (i) (resp. S e (i)), all the sets in S that contains element x b (i) (resp. x e (i)). For each pair i j ∈ [k], we denote by S(i, j) all the sets in S that contains element x(i, j, t). Finally, for each pair i < j ∈ [k], we denote by S(i, j, ⊢) (resp S(i, j, ⊣)) all the sets in S that contains element y b (i, j) (resp. y e (i, j)). One can observe that the S b (i)'s, S e (i)'s, S(i, j)'s, S(i, j, ⊢)'s, and S(i, j, ⊣)'s partition

S into k + k + k(k -1) + 2 k 2 = 2k 2 partite sets 2 .
Thus, as each of the 2k 2 partite sets S ′ has a private element which is only contained in sets of S ′ , a solution has to contain one set in each partite set.

1:8 Édouard Bonnet and Tillmann Miltzow

G v 1 1 v 1 2 V 1 v 2 1 v 2 2 V 2 v 3 1 v 3 2 V 3
Fig. 3. A simple instance of Multicolored k-Clique. The elements in bold: vertices v 1 2 and v 2 2 , edge v 1 2 v 2 2 , and half of the edges v 1 2 v 3 1 and v 2 2 v 3 1 correspond to the selection of sets depicted in Figure 4.

x b (1) x(1, 2, 1) x(1, 2, 2) x(1, 3, 1) x(1, 3, 2) x(1, 4, 1) x(1, 4 , 2)
x e (1)

x b (2) x(2, 1, 1) x(2, 1, 2) x(2, 3, 1) x(2, 3, 2) x(2, 4, 1) x(2, 4 , 2)
x e (2) . . .

z b (1, 2) z(1, 2, 1) z(1, 2 , 2)
z e (1, 2)
. . .

y b (1, 2) y(1, 2, 1) y(1, 2, 2) y(1, 2, 3) y(1, 2, 4) y(1, 2, 5) y(1, 2 , 6
)

y e (1, 2)
. . .

w b (1) w(1, 1) w(1, 2
)

w e (1) w b (2) w(2, 1) w(2,
2) Assume there is a multicolored clique

w e (2) . . . S(1, 1, ⊢) 1 1 1 1 S(1, 2, ⊢) 1 1 1 1 S(v 1 1 v 2 2 , v 1 1 ) 1 1 1 1 S(v 1 2 v 2 2 , v 1 2 ) 1 1 1 1 S(v 1 1 v 3 2 , v 1 1 ) 1 1 S(v 1 2 v 3 1 , v 1 2 ) 1 1 S(1, 1, ⊣) 1 1 1 1 S(1, 2, ⊣) 1 1 1 1 S(2, 1, ⊢) 1 1 1 1 S(2, 2, ⊢) 1 1 1 1 S(v 2 2 v 1 1 , v 2 2 ) 1 1 1 1 S(v 2 2 v 1 2 , v 2 2 ) 1 1 1 1 S(v 2 1 v 3 1 , v 2 1 ) 1 1 S(v 2 2 v 3 1 , v 2 2 ) 1 1 S(2, 1, ⊣) 1 1 1 1 S(2, 2, ⊣) 1 1 1 1 S(v 1 2 v 2 2 , ⊢) 1 1 1 S(v 1 1 v 2 2 , ⊢) 1 1 1 S(v 1 2 v 2 2 , ⊣) 1 1 1 1 1 S(v 1 1 v 2 2 , ⊣) 1 1 1 1 1
C = {v 1 a 1 , . . . , v k a k } in G. We show that T = {S(v i a i v j a j , v i a i ) | i < j ∈ [k]} ∪ {S(v i a i v j a j , v j a j ) | i < j ∈ [k]} ∪ {S(i, a i , ⊢) | i ∈ [k]} ∪ {S(i, a i , ⊣) | i ∈ [k]} ∪ {S(v i a i v j a j , ⊢) | i < j ∈ [k]} ∪ {S(v i a i v j a j , ⊣) | i < j ∈ [k]} is a set cover of (S, X ) of size 2k 2 .
As C is a clique, T is well defined and it contains 2

k 2 + 2k + 2 k 2 = 2k 2 sets. For each i ∈ [k], the elements x(i, 1, a i ), . . . , x(i, 1, t), . . . , x(i, k + 1, 1), . . . , x(i, k + 1, a i -1) are covered by the sets S(v 1 a 1 v i a i , v i a i ), S(v 2 a 2 v i a i , v i a i ), . . . , S(v i a i v k a k , v i a i ). Indeed, S(v j a j v i a i , v i a i ) (or S(v i a i v j a j , v i a i ) if j > i
) covers all the elements x(i, j, a i ), . . . , x(i, j, t), x(i, j + 1, 1), . . . , x(i, j + 1, a i -1) (again, in case i + 1 = j, replace j+1 by i+1). For each i ∈ [k], the elements x b (i), x(i, 1, 1), . . . , x(i, 1, a i -1), x(i, k + 1, a i ), . . . , x(i, k + 1, t), x e (i) and of W (i) are covered by S(i, a i , ⊢) and S(i, a i , ⊣). For all i < j ∈ [k], say v i a i v j a j is the c-th edge e i j c in the arbitrary order of E i j . Then, the elements y(i, j, c), y(i, j, c + 1), . . . , y(i, j, c + 2|E i j | -1) are covered by S(v i a i v j a j , v i a i ) and S(v i a i v j a j , v j a j ). Finally, the elements y b (i, j), y(i, j, 1), . . . , y(i, j, c -1), y(i, j, c +2|E i j |), . . . , y(i, j, 3|E i j |), y e (i, j) and of Z (i, j) are covered by S(v i a i v j a j , ⊢) and S(v i a i v j a j , ⊣).

Assume now that the set-system (X , S) admits a set cover T of size 2k 2 . As mentioned above, this solution T should contain exactly one set in each partite set (of the partition of S). For each

i ∈ [k],
to cover all the elements of W (i), one should take S(i, a i , ⊢) and S(i, a ′ i , ⊣) with a i ⩽ a ′ i . Now, each set of S(i, j) has their A-intervals containing exactly t elements. This means that the only way of covering the tk + 2 elements of X (i) is to take S(i, a i , ⊢) and S(i, a ′ i , ⊣) with a i ⩾ a ′ i (therefore

a i = a ′ i )
, and to take all the k -1 sets of S(i, j) (for j ∈ [k] \ {i}) of the form S(v i a i v j s j , v i a i ), for some

s j ∈ [t]
. So far, we showed that a potential solution of k-Set Cover should stick to the same vertex v i a i in each color class. We now show that if one selects S(v i a i v j s j , v i a i ), one should be consistent with this choice and also selects S(v i a i v j s j , v j s j ). In particular, it implies that, for each i ∈ [k], s i should be equal to a i . For each i j ∈ [k], to cover all the elements of Z (i, j), one should take S(e i j c i j , ⊢)

and S(e i j c ′ i j , ⊣) with c i j ⩾ c ′ i j . Now, each set of S(i, j) and each set of S(j, i) has their B-intervals containing exactly |E i j | elements. This means that the only way of covering the 3|E i j | + 2 elements of Y (i, j) is to take S(e i j c i j , ⊢) and S(e i j

c ′ i j , ⊣) with c i j ⩽ c ′ i j (therefore, c i j = c ′ i j
), and to take the sets

S(v i a i v j a j , v i a i ) and S(v i a i v j a j , v j a j ). Therefore, if there is a solution to the k-Set Cover instance, then there is a multicolored clique {v 1 a 1 , . . . , v k a k } in G.
In this reduction, there is a quadratic blow-up of the parameter. Under the ETH, it would only forbid, by Theorem 3.1, an algorithm solving k-Set Cover on two-block instances in time

f (k)(N + M) o( √ k ) .
We can do the previous reduction from Multicolored Subgraph Isomorphism and suppress X (i, j), X (j, i), Z (i, j), and Y (i, j), and the sets defined over these elements, whenever

E i j is
(C 1 , C 2 , . . . , C k ) where C j = {a j 1 , a j 2 , . . . , a j t } for each j ∈ [k]. A is ordered: a 1 1 , a 1 2 , . . . , a 1 t , a 2 1 , a 2 2 , . . . , a 2 t , . . . , a k 1 , a k 2 , . . . , a k t . We define C ′ j := ϕ(C j ) and b j i := ϕ(a j i ) for all i ∈ [t] and j ∈ [k]. We now impose that ϕ is such that, for each j ∈ [k], the set C ′ j is a B-interval.
That is, B is ordered:

C ′ σ (1) , C ′ σ (2) , . . . , C ′ σ (k ) for some permutation on [k], σ ∈ S k . For each j ∈ [k]
, the order of the elements within C ′ j can be described by a permutation σ j ∈ S t such that the ordering of C ′ j is: 1) , b j σ j (2) , . . . , b j σ j (t ) . In what follows, it will be convenient to see an instance of Structured 2-Track Hitting Set as a tuple

b j σ j (
I = (k ∈ N, t ∈ N, σ ∈ S k , σ 1 ∈ S t , . . . , σ k ∈ S t , S A , S B
), where we recall that S A is a set of A-intervals and S B is a set of B-intervals. The size |I| of I is defined

as kt + |S A | + |S B |. We denote by [a j i , a j ′ i ′ ] (resp. [b j i , b j ′ i ′ ]) all the elements a ∈ A (resp. b ∈ B) such that a j i ≤ A a ≤ A a j ′ i ′ (resp. b j i ≤ B b ≤ B b j ′ i ′ ). a 1 1 a 1 2 a 1 3 a 1 4 a 1 5 a 1 6 C 1 a 2 1 a 2 2 a 2 3 a 2 4 a 2 5 a 2 6 C 2 a 3 1 a 3 2 a 3 3 a 3 4 a 3 5 a 3 6 C 3 a 4 1 a 4 2 a 4 3 a 4 4 a 4 5 a 4 6 C 4 A b 3 4 b 3 2 b 3 3 b 3 6 b 3 1 b 3 5 C ′ 3 b 1 2 b 1 4 b 1 1 b 1 5 b 1 6 b 1 3 C ′ 1 b 4 3 b 4 6 b 4 5 b 4 2 b 4 1 b 1 4 C ′ 4 b 2 1 b 2 5 b 2 2 b 2 4 b 2 6 b 2 3 C ′ 2 B σ σ 1 ≤ A : ≤ B :
Fig. 5. An illustration of a Structured 2-Track Hitting Set instance, with k = 4 and t = 6. The permutation σ ∈ S k is represented with thick edges. Among σ 1 ∈ S t , . . . , σ k ∈ S t , we only represented σ 1 , for the sake of legibility. We also only represented four intervals of the instance, three

A-intervals, [a 1 5 , a 2 2 ] = {a 1 5 , a 1 6 , a 2 1 , a 2 2 }, [a 1 6 , a 2 4 ], [a 3 5 , a 4
2 ], and one B-interval We call A ′ (resp. B ′ ) the set of all the elements of the form x S,A (resp. x S, B ). We shall now specify an order of A ′ and B ′ so that the instance is structured. Keep in mind that elements in the Structured track and the second track. A (unit) 2-track interval may be referred to as an object. Two 2-track intervals intersect if they intersect in either the first or the second track. We observe here that many dominating problems with some geometric flavor can be restated with the terminology of 2-track (unit) interval graphs.

[b 1 6 , b 4 3 ] = {b 1 6 , b 1 3 , b 4 3 }. Again a solution is a set of k 2-elements {(a 1 i(1) , b 1 i(1) ), . . . , (a k i(k ) , b k i(k ) )}, each from a distinct color class, such that a 1 i(1) , . . . , a k i(k ) is a hitting set of S A ,
In particular, a result very close to Theorem 4.2 was obtained recently: for any computable function f , unless the ETH fails.

We still had to give an alternative proof of this result because we will need the additional property that the instance can be further assumed to have the structure depicted in Figure 5. This will be crucial for showing the hardness result for Vertex Guard Art Gallery.

Other results on dominating problems in 2-track unit interval graphs include: The result of Dom et al. is formalized differently in their paper [START_REF] Dom | The parameterized complexity of stabbing rectangles[END_REF], where the problem is defined as stabbing axis-parallel rectangles with axis-parallel lines.

PARAMETERIZED HARDNESS OF THE POINT GUARD VARIANT

As exposed in Section 2, we give a reduction from the Structured 2-Track Hitting Set problem.

The main challenge is to design a linker gadget that groups together specific pairs of points in the polygon. The following introductory lemma inspires the linker gadgets for both Point Guard Art Gallery and Vertex Guard Art Gallery.

Lemma 5.1. The only minimum hitting sets of the set-system S = {S i = {1, 2, . . . , i, i

+ 1, i + 2, . . . , n} | i ∈ [n]} ∪ {S i = {1, 2, . . . , i, i + 1, i + 2, . . . , n} | i ∈ [n]} are {i, i}, for each i ∈ [n].
Proof. First, for each i ∈ [n], one may easily observe that {i, i} is a hitting set of S. Now, because of the sets S n and S n one should pick one element i and one element j for some i, j ∈

[n]. If i < j,
then set S i is not hit, and if i > j, then S j is not hit. Therefore, i should be equal to j. □

Henceforth we keep this bar notation to denote pairs of homologous objects (points, vertices)

that we wish to link together.

Theorem 1.1 (Parameterized hardness point guard). Point Guard Art Gallery is not solvable in time f (k)n o(k /log k ) , even on simple polygons, where n is the number of vertices of the polygon and k is the number of guards allowed, for any computable function f , unless the ETH fails.

Proof. Given an instance

I = (k ∈ N, t ∈ N, σ ∈ S k , σ 1 ∈ S t , . . . , σ k ∈ S t , S A , S B ) of
Structured 2-Track Hitting Set, we build a simple polygon P with O(kt

+ |S A | + |S B |) vertices,
such that I is a YES-instance iff P can be guarded by 3k points.

Outline. We recall that A's order is: a 1 1 , . . . , a 1 t , . . . , a k 1 , . . . , a k t and B's order is determined by σ and the σ j 's (see Figure 5). The global strategy of the reduction is to allocate, for each color class j ∈ [k], 2t special points in the polygon α j 1 , . . . , α j t and β j 1 , . . . , β j t . Placing a guard in α j i (resp.

β j i )
shall correspond to picking a 2-element whose first (resp. second) component is a j i (resp. b j i ). The points α j i 's and β j i 's ordered by increasing y-coordinates will match the order of the a j i 's along the order ≤ A and then of the b j i 's along ≤ B . Then, far in the horizontal direction, we will place pockets to encode each A-interval of S A , and each B-interval of S B (see Figure 6).

The critical issue will be to link point α j i to point β j i . Indeed, in the Structured 2-Track Hitting Set problem, one selects 2-elements (one per color class), so we should prevent one from placing two guards in α j i and β j i ′ with i i ′ . The so-called point linker gadget will be grounded in Lemma 5.1.

Due to a technicality, we will need to introduce a copy α j i of each α j i . In each part of the gallery encoding a color class j ∈ [k], the only way of guarding all the pockets with only three guards will be to place them in α j i , α j i , and β j i for some i ∈ [t] (see Figure 8). Hence, 3k guards will be necessary and sufficient to guard the whole P iff there is a solution to the instance of Structured 2-Track Hitting Set.

We now get into the details of the reduction. We will introduce several characteristic lengths and compare them; when l 1 ≪ l 2 means that l 1 should be thought as really small compared to l 2 , and l 1 ≈ l 2 means that l 1 and l 2 are roughly of the same order. The motivation is to guide the intuition of the reader without bothering her/him too much about the details. At the end of the construction, we will specify more concretely how those lengths are chosen.

Construction. We start by formalizing the positions of the α j i 's and β j i 's. We recall that we want the points α j i 's and β j i 's ordered by increasing y-coordinates, to match the order of the a j i 's and b j i 's along ≤ A and ≤ B , with first all the elements of A and then all the elements of B. Starting from some y-coordinate y 1 (which is the one given to point α 1 1 ), the y-coordinates of the α j i 's are regularly spaced out by an offset y; that is, the y-coordinate of α j i is y 1 +(i +(j -1)t)y. Between the y-coordinate of the last element in A (i.e., a k t whose y-coordinate is y 1 + (kt -1)y) and the first element in B, there is a large offset L, such that the y-coordinate of

β j i is y 1 + (kt -1)y + L + (ind(b j i ) -1)y (for any j ∈ [k] and i ∈ [t]) where ind(b j i ) is the index of b j i along the order ≤ B , that is the number of b ∈ B such that b ≤ B b j i .
For each color class j ∈ [k], let x j := x 1 + (j -1)D for some x-coordinate x 1 and value D, and y j := y 1 + (j -1)ty. The allocated points α j 1 , α j 2 , α j 3 , . . . , α j t are on a line at coordinates: (x j , y j ), (x j +

x, y j +y), (x j + 2x, y j + 2y), . . . , (x j + (t -1)x, y j + (t -1)y), for some value x. We place, to the left of those points, a rectangular pocket P j,r of width, say, y and length, say 3 , tx such that the uppermost longer side of the rectangular pocket lies on the line ℓ(α j 1 , α j t ) (see Figure 7). The y-coordinates of β j 1 , β j 2 , β j 3 , . . . , β j t have already been defined. We set, for each i ∈ [t], the x-coordinate of β j i to

x j + (i -1)x, so that β j i and α j i share the same x-coordinate. One can check that it is consistent with 3 the exact width and length of this pocket are not relevant; the reader may just think of P j,r as a thin pocket which forces to place a guard on a thin strip whose uppermost boundary is ℓ(α the previous paragraph. We also observe that, by the choice of the y-coordinate for the β j i 's, we have both encoded the permutations σ j 's and permutation σ (see Figure 9 or Figure 7).

Our construction almost exclusively rely on so-called triangular pockets. Henceforth, for a vertex v and two points p and p ′ , we call a triangular pocket rooted at vertex v and supported by ray(v, p)

and ray(v, p ′ ) a sub-polygon w, v, w ′ (a triangle) such that ray(v, w) passes through p, ray(v, w ′ ) passes through p ′ , while w and w ′ are close to v (sufficiently close not to interfere with the rest of the construction). We say that v is the root of the triangular pocket, that we often denote by P(v).

We also say that the pocket P(v) points towards p and p ′ .

We now encode the A-intervals and B-intervals with triangular pockets. At the x-coordinate

x k + (t -1)x + F , for some large value F , we put between y-coordinates y 1 and y k + (kt -1)y, for each A-interval I q = [a j i , a j ′ i ′ ] ∈ S A we put one triangular pocket P(z A,q ) rooted at vertex z A,q and supported by ray(z A,q , α j i ) and ray(z A,q , α j ′ i ′ ). Intuitively, if y ≪ x ≪ D ≪ F , the only α j ′′ i ′′ seeing vertex z A,q should be all the points such that a j i ≤ A a j ′′ i ′′ ≤ A a j ′ i ′ (see Figure 9 and Figure 6). We place those |S A | pockets along the y-axis, and space them out by distance s. To guarantee that we have enough room to place all those pockets, s ≪ y shall later hold. Similarly, we place at the same

x-coordinate x k + (t -1)
x + F each of the |S B | triangular pockets P(z B,q ) rooted at vertex z B,q and supported by ray(z B,q , β j i ) and ray(z B,q ,

β j ′ i ′ ) for B-interval [b j i , b j ′ i ′ ] ∈ S B ;
and we space out those pockets by distance s along the y-axis between x-coordinates y 1 + (kt -1)y +L and y 1 + 2(kt -1)y +L.

We do not specify an order to the z A,q 's (resp. the z B,q 's) along the y-axis since we do not need that to prove the reduction correct. The different values (s, x, y, D, L, and F ) introduced so far compare in the following way: s ≪ y ≪ x ≪ D ≪ F , and x ≪ L ≪ F (see Figure 9).

We now describe the linker gadget, or how to force consistent pairs of guards α j i and its associate

β j i .
The idea is that pairs of guards α j i , β j i will be very effective since the two points see disjoint sets of pockets, whereas pairs α j i , β j i ′ (with i i ′ ) will overlap on some pockets, and miss some other pockets completely.

For each j ∈ [k], let us mentally draw ray(α j t , β j 1 ) and consider points slightly to the left of this ray at a distance, say, L ′ from point α j t . Let us call R j left that informal region of points. Any point in R j left sees, from right to left, in this order α j 1 , α j 2 up to α j t , and then, β j 1 , β j 2 up to β j t . This observation relies on the fact that y ≪ x ≪ L. So, from the distance, the points β j 1 , . . . , β j t look almost flat. It makes the following construction possible. In R j left , for each i ∈ [t -1], we place a triangular pocket P(c j i ) rooted at vertex c j i and supported by ray(c j i , α j i+1 ) and ray(c j i , β j i ). We place also a triangular pocket P(c j t ) rooted at c j t supported by ray(c j t , β j 1 ) and ray(c j t , β j t ). We place the vertices

c j i (i ∈ [t])
at the same y-coordinate and we space them out by distance x along the x-axis (see Figure 7).

Similarly, let us informally refer to the region slightly to the right of ray(α j 1 , β j t ) at a distance L ′ from point α j 1 , as R j right . Any point R j right sees, from right to left, in this order β j 1 , β j 2 up to β j t , and then, α j 1 , α j 2 up to α j t . Therefore, one can place in R j left , for each i ∈ [t -1], a triangular pocket P(d j i ) rooted at d j i supported by ray(d j i , β j i+1 ) and ray(c j i , α j i ). We place also a triangular pocket P(d j t ) rooted at d j t supported by ray(d j t , α j 1 ) and ray(d j t , α j t ). Again, those t pockets can be put at the same y-coordinate and spaced out horizontally by x (see Figure 7). We denote by P j,α, β the set of pockets {P(c j 1 ), . . . , P(c j t ), P(d j 1 ), . . . , P(d j t )} and informally call it the weak point linker (or simply, weak linker) of α j 1 , . . . , α j t and β j 1 , . . . , β j t . We may call the pockets of R j left (resp. R j right ) left pockets (resp. right pockets).

As we will show later, if one wants to guard with only two points all the pockets of P j,α, β = {P(c j 1 ), . . . , P(c j t ), P(d j 1 ), . . . , P(d j t )} and one first decides to put a guard on point α j i (for some

α 1 α 2 α 3 α 4 α 5 α 6 β 1 β 2 β 3 β 4 β 5 β 6 d 1 c 1 d 2 c 2 d 3 c 3 d 4 c 4 d 5 c 5 d 6 c 6
Fig. 7. Weak point linker gadget P j,α, β with t = 6. We omit the superscript j in all the labels.

i ∈ [t]), then one is not forced to put the other guard on point β j i but only on an area whose uppermost point is β j i (see the shaded areas below the b j i 's in Figure 7). Now, if β j 1 , . . . , β j t would all lie on a same line ℓ, we could shrink the shaded area of each β j i (Figure 7) down to the single point β j i by adding a thin rectangular pocket on ℓ (similarly to what we have for α j 1 , . . . , α j t ). Naturally we need that β j 1 , . . . , β j t are not on the same line, in order to encode σ j .

The remedy we suggest is to make a triangle of weak linkers. For each j ∈ [k], we allocate t points α j 1 , α j 2 , . . . , α j t on a horizontal line, spaced out by distance x, say, ≈ D 2 to the right and ≈ L to the up of β j t . We put a thin horizontal rectangular pocket P j,r of the same dimension as P j,r such that the lowermost longer side of P j,r is on the line ℓ(α j 1 , α j t ). We add the 2t pockets corresponding to a weak linker P j,α,α between α j 1 , . . . , α j t and α j 1 , . . . , α j t as well as the 2t pockets of a weak linker P j,α, β between α j 1 , . . . , α j t and β j 1 , . . . , β j t as pictured in Figure 8. We denote by P j the union P j,r ∪ P j,r ∪ P j,α, β ∪ P j,α,α ∪ P j,α, β of all the pockets involved in the encoding of color class j. Now, say, one wants to guard all the pockets of P j with only three points, and chooses to put a guard on α j i (for some i ∈ [t]). Because of the pockets of P j,α,α ∪ P j,r , one is forced to place a second guard precisely on α j i . Now, because of the weak linker P j,α, β the third guard should be on a region whose uppermost point is β j i , while, because of P j,α, β the third guard should be on a region whose lowermost point is β j i . The conclusion is that the third guard should be put precisely on β j i . This triangle of weak linkers is called the linker of color class j. The k linkers are placed accordingly to Figure 9. This ends the construction.

Specification of the distances. We can specify the coordinates of positions of all the vertices by fractions of integers. These integers are polynomially bounded in n. If we want to get integer coordinates, we can transform the rational coordinates to integer coordinates by multiplying all of them with the least common multiple of all the denominators, which is not polynomially bounded anymore. The length of the integers in binary is still polynomially bounded.

Parameterized Hardness of Art Gallery Problems 1:15

P j,α, β P j,α,α P j,α, β
Fig. 8. Point linker gadget P j : a triangle of (three) weak point linkers P j,α, β , P j,α,α , P j,α, β , and two rectangular pockets forcing one guard on the lines ℓ(α

j 1 , α j 2 ) = ℓ(α j 1 , α j t ) and ℓ(α j 1 , α j 2 ) = ℓ(α j 1 , α j t ).
We can safely set s to one, as it is the smallest length, we specified. We will put |S A | pockets on track 1 and |S B | pockets on track 2. It is sufficient to have an opening space of one between them. Thus, the space on the right side of P, for all pockets of track 1 is bounded by 2 • |S A |. Thus setting y to |S A | + |S B | secures us that we have plenty of space to place all the pockets. We specify

F = (|S A | + |S B |)Dk = y • D • k.
We have to show that this is large enough to guarantee that the pockets on track 1 distinguish the picked points only by the y-coordinate. Let p and q be two points among the α j i . Their vertical distance is upper bounded by Dk and their horizontal distance is lower bounded by y. Thus the slope of ℓ = ℓ(p, q) is at least y Dk . At the right side of P the line ℓ will be at least F y Dk above the pockets of track 1. Note

F y Dk = yDk • y Dk > y 2 > |S A | 2 > 2 • |S A |.
The same argument shows that F is sufficiently large for track 2.

The remaining lengths x, L, L ′ , and D can be specified in a similar fashion. For the construction of the pockets, let s ∈ S A be an A-interval with endpoints a and b, represented by some points p and q and assume the opening vertices v and w of the triangular pocket are already specified. Then the two lines ℓ(p, v) and ℓ(q, w) will meet at some point x to the right of v and w. By Lemma 3.3, x has rational coordinates and the integers to represent them can be expressed by the coordinates of p, q, v, and w. This way, all the pockets can be explicitly constructed using rational coordinates as claimed above.

Correctness. We now show that the reduction is correct. The following lemma is the main argument for the easier implication: if I is a YES-instance, then the gallery that we build can be guarded with 3k points.

Lemma 5.2. ∀j ∈ [k], ∀i ∈ [t], the three associate points α j i , α j i , β j i guard P j entirely.

1:16

Édouard Bonnet and Tillmann Miltzow Proof. The rectangular pockets P j,r and P j,r are entirely seen by α j i and α j i , respectively. The pockets P(c j 1 ), P(c j 2 ), . . . P(c j i-1 ) and P(d j i ), P(d j i+1 ), . . . P(d j t ) are all entirely seen by α j i , while the pockets P(c j i ), P(c j i+1 ), . . . P(c j t ) and P(d j 1 ), P(d j 2 ), . . . P(d j i-1 ) are all entirely seen by β j i . This means that α j i and β j i jointly see all the pockets of P j,α, β . Similarly, α j i and α j i jointly see all the pockets of P j,α,α , and α j i and β j i jointly see all the pockets of P j,α, β . Therefore, α j i , α j i , β j i jointly see all the pockets of P j . □

F F D P 1,α,β P 2,α,β P 3,α,β P 1,α,α P 2,α,α P 3,α,α P 1,α,β P 2,α,β P 3,α,β L
Assume that I is a YES-instance and let {(a

1 s 1 , b 1 s 1 ), . . . , (a k s k , b k s k )} be a solution. We claim that G = {α 1 s 1 , α 1 s 1 , β 1 s 1 , . . . , α k s k , α k s k , β k s k }
guard the whole polygon P. By Lemma 5.2, ∀j ∈ [k], P j is guarded. For each A-interval (resp. B-interval) in S A (resp. S B ) there is at least one 2-element (a j s j , b j s j ) such that a j s j ∈ S A (resp. b j s j ∈ S B ). Thus, the corresponding pocket is guarded by α j s j (resp. β j s j ). The rest of the polygon P (which is not part of pockets) is guarded by, for instance,

{α 1 s 1 , . . . , α k s k }.
So, G is indeed a solution and it contains 3k points.

We now assume that there is a set G of 3k points guarding P. We will then show that I is a YES-instance. We observe that no point of P sees inside two triangular pockets one being in P j,α,γ and the other in P j ′ ,α,γ ′ with j j ′ and γ , γ ′ ∈ {β, α }. Further, V (r (P j,α, β ∪ P j,α,α )) ∩V (r (P j ′ ,α, β ∪ P j ′ ,α,α )) = ∅ when j j ′ , where r maps a set of triangular pockets to the set of their root. Also, for each j ∈ [k], seeing P j,α, β and P j,α,α entirely requires at least 3 points. This means that for each j ∈ [k], one should place three guards in V (r (P j,α, β ∪ P j,α,α )). Furthermore, one can observe that, among those three points, one should guard a triangular pocket P j ′ ,r and another should guard P j ′′ ,r . Thus a set S 1 , consisting of three guards of G, sees P 1 and two rectangular pockets P j ′ ,r and P j ′′ ,r .

Let us call ℓ 1 (resp. ℓ ′ 1 ) the line corresponding to the extension of the uppermost (resp. lowermost) longer side of P 1,r (resp. P 1,r ). The only points of P that can see a rectangular pocket P j ′ ,r and at least t pockets of P 1,α,α are on ℓ 1 : more specifically, they are the points α α 1 i ′ is not seen, or i > i ′ and the right pocket pointing towards α 1 i+1 and α 1 i is not seen). We denote by s 1 this shared value. Now, to see the left pocket P(c 1 s 1 ) and the right pocket P(d 1 s 1 -1 ) (that should still be seen), the third guard should be to the left of ℓ(c 1 s 1 , β 1 s 1 ) and to the right of ℓ(d 1 s 1 -1 , β 1 s 1 ) (see shaded area of Figure 7). That is, the third guard of S 1 should be on a region in which β 1 s 1 is the uppermost point. The same argument with the pockets of P 1,α, β implies that the third guard should also be on a region in which β 1 s 1 is the lowermost point. Thus, the third guard of S 1 has to be the

point β 1 s 1 . Therefore S 1 = {α 1 s 1 , α 1 s 1 , β 1 s 1 }, for some s 1 ∈ [t].
As none of those three points see any pocket P j,α, β with j > 1 (we already mentioned that no pocket of P j,α, β and P j,α,α with j > 1 can be seen by those points), we can repeat the argument for the second color class; and so forth up to color class k. Thus, G is of the form

{α 1 s 1 , α 1 s 1 , β 1 s 1 , . . . , α k s k , α k s k , β k s k }.
As G also guards all the pockets of tracks 1 and 2, the set of k Linker gadget. This gadget encodes the 2-elements. We build a sub-polygon that can be seen entirely by pairs of convex vertices if and only if they correspond to the same 2-element.

For each j ∈ [k], permutation σ j will be encoded by a sub-polygon P j that we call vertex linker, or simply linker (see Figure 10). We regularly set t consecutive vertices α j 1 , α j 2 , . . . , α j t in this order, along the x-axis. Opposite to this segment, we place t vertices β j σ j (1) , β j σ j (2) , . . . , β j σ j (t ) in this order, along the x-axis, too. The β j σ j (1) , . . . , β j σ j (t ) , contrary to α j 1 , . . . , α j t , are not consecutive; we will later add some reflex vertices between them. At mid-distance between α j 1 and β j σ j (1) , to the left, we put a reflex vertex r j ↓ . To the left of this reflex vertex, we place a vertical wall d j e j (r j ↓ , d j , and e j are three consecutive vertices of P), so that ray(α j 1 , r j ↓ ) and ray(α j t , r j ↓ ) both intersect seg(d j , e j ). That implies that for each i ∈ [t], ray(α j i , r j ↓ ) intersects seg(d j , e j ). We denote by p j i this intersection. The greater i, the closer p j i is to d j . Similarly, at mid-distance between α j t and β j σ j (t ) , to the right, we put a reflex vertex r j ↑ and place a vertical wall x j y j (r j ↑ , x j , and y j are consecutive), so that ray(α j 1 , r j ↑ )

and ray(α j t , r j ↑ ) both intersect seg(x j , y j ). For each i ∈ [t], we denote by q j i the intersection between ray(α j i , r j ↑ ) and seg(x j , y j ). The smaller i, the closer q j i is to x j .

1:18 Édouard Bonnet and Tillmann Miltzow

For each i ∈ [t], we put around β j i two reflex vertices, one in ray(β j i , p j i ) and one in ray(β j i , q j i ).

Later we may refer to these reflex vertices as intermediate reflex vertices. In Figure 10, we merged some reflex vertices but the essential part is that V (β j i )∩ seg(d j , e j ) = seg(d j , p j i ) and V (β j i )∩ seg(x j , y j ) = seg(x j , q j i ). Finally, we add a triangular pocket rooted at д j and supported by ray(д j , α j 1 )

and ray(д j , α j t ), as well as a triangular pocket rooted at b j and supported by ray(д j , β j σ j (1) ) and ray(д j , β j σ j (t ) ). This ends the description of the vertex linker (see Figure 10).

α 1 α 2 α 3 α 4 α 5 α 6 β 4 β 2 β 5 β 3 β 6 β 1 r ↓ d e f a c r ↑ x y h д b p 1 p 2 p 3 p 4 q 3 q 4 q 5 q 6
Fig. 10. Vertex linker gadget P j . We omitted the superscript j in all the labels. Here, σ j (1) = 4, σ j (2) = 2, σ j (3) = 5, σ j (4) = 3, σ j (5) = 6, σ j (6) = 1.

The following lemma formalizes how exactly the vertices α j i and β j i are linked: say, one chooses to put a guard on a vertex α j i , then the only way to see P j entirely, by putting a second guard on a vertex of {β j 1 , . . . , β j t } is to place it on the vertex β j i .

Lemma 6.1. For any j ∈ [k], the sub-polygon P j is seen entirely by {α j v , β j w } iff v = w.

Proof. The regions of P j not seen by α j v (i.e., P j \ V (α j v )) consist of the triangles d j r j ↓ p j v , x j r j ↑ q j v and partially the triangle a j b j c j . The triangle a j b j c j is anyway entirely seen by the vertex β j i , for

any i ∈ [t]. It remains to prove that d j r j ↓ p j v ∪ x j r j ↑ q j v ⊆ V (β j w ) iff v = w. It holds that d j r j ↓ p j v ∪ x j r j ↑ q j v ⊆ V (β j v
) since, by construction, the two reflex vertices neighboring β j v are such that β j v sees seg(d j , p j α ) (hence, the whole triangle d j r j ↓ p j v ) and seg(x j , q j α ) (hence, the whole triangle x j r j ↑ q j v ). Now, let us assume that v w. If v < w, the interior of the segment seg(p v , p w ) is not seen by {α j v , β j w }, and if v > w, the interior of the segment seg(q v , q w ) is not seen by {α j v , β j w }. □

The issue we now have is that one could decide to place a guard on a vertex α j i and a second guard on a reflex vertex between β j σ j (w ) and β j σ j (w +1) (for some w ∈ [t -1]). This is indeed another Parameterized Hardness of Art Gallery Problems 1:19 way to guard the whole P j . We will now describe a sub-polygon F j (for each j ∈ [k]) called filter gadget (see Figure 11) satisfying the property that all its (triangular) pockets can be guarded by adding only one guard on a vertex of F j iff there is already a guard on a vertex β j i of P j . Therefore, the filter gadget will prevent one from placing a guard on a reflex vertex of P j . The functioning of the gadget is again based on Lemma 5.1.

Filter gadget. Let d j 1 , . . . , d j t be t consecutive vertices of a regular, say, 20t-gon, so that the angle made by ray(d j 1 , d j 2 ) and the y-axis is a bit below 45 • , while the angle made by ray(d j t -1 , d j t ) and the y-axis is a bit above 45 • . The vertices d j 1 , . . . , d j t therefore lie equidistantly on a circular arc C.

We now mentally draw two lines ℓ h and ℓ v ; ℓ h is a horizontal line a bit below d j 1 , while ℓ v is a vertical line a bit to the right of d j t . We put, for each i ∈ [t], a vertex x j i at the intersection of ℓ h and the tangent to C passing through d j i . Then, for each i ∈ [t -1], we set a triangular pocket P(x j i )

rooted at x j i and supported by ray(x j i , d j 1 ) and ray(x j i , β j σ j (i+1) ). For convenience, each point β j σ j (i) is denoted by c j i on Figure 11. We also set a triangular pocket P(x j t ) rooted at x j t and supported by ray(x j t , d j 1 ) and ray(x j t , d j t ). Similarly, we place, for each i ∈ [t -1], a vertex y j i at the intersection of ℓ v and the tangent to C passing through d j i+1 . Finally, we set a triangular pocket P(y j i ) rooted at y j i and supported by ray(y j i , β j σ j (i) ) and ray(y j i , d j t ), for each i ∈ [t -1] (see Figure 11). We denote by

P(F j ) the 2t -1 triangular pockets of F j . d 1 d 2 d 3 d 4 d 5 d 6 x 1 x 2 x 3 x 4 x 5 x 6 c 1 c 2 c 3 c 4 c 5 c 6 y 1 y 2 y 3 y 4 y 5
Fig. 11. The filter gadget F j . Again, we omit the superscript j on the labels. Vertices c 1 , c 2 , . . . , c t are not part of F j and are in fact the vertices β j σ j (1) , β j σ j (2) , . . . , β j σ j (t ) and the vertices in between the c i 's are the reflex vertices that we have to filter out. Lemma 6.2. For each j ∈ [k], the only ways to see P(F j ) and the triangle a j b j c j entirely with only two guards on vertices of P j ∪ P(F j ) is to place them on vertices c j i and d j i (for any i ∈ [t]).

Proof. Proving this lemma will, in particular, entail that it is not possible to see P(F j ) entirely with only two vertices if one of them is a reflex vertex between c j i and c j i+1 . We recall that such a vertex is called an intermediate reflex vertex (in color class j). Because of the pocket a j b j c j , one should put a guard on a c j i (for some i ∈ [t]) or on an intermediate reflex vertex in class j. As vertices a j , b j , and c j do not see anything of P(F j ), placing the first guard at one of those three vertices cannot work as a consequence of what follows.

Say, the first guard is placed at c j i (= β j σ (i) ). The pockets P(x j 1 ), P(x j 2 ), . . . , P(x j i-1 ) and P(y j i ), P(y j i+1 ), . . . , P(x j t -1 ) are entirely seen, while the vertices x j i , x j i+1 , . . . , x j t and y j 1 , y j 2 , . . . , y j i-1 are not. The only vertex that sees simultaneously all those vertices is d j i . The vertex d j i even sees the whole pockets P(x j i ), P(x j i+1 ), . . . , P(x j t ) and P(y j 1 ), P(y j 2 ), . . . , P(y j i-1 ). Therefore, all the pockets P(F j ) are fully seen. Now, say, the first guard is put on an intermediate reflex vertex r between c j i and c j i+1 (for some i ∈ [t -1]). Both vertices x j i and y j i , as well as x j t , are not seen by r and should therefore be seen by the second guard. However, no vertex simultaneously sees those three vertices. □

Putting the pieces together. The permutation σ is encoded the following way. We position the vertex linkers P 1 , P 2 , . . . , P k such that P i+1 is below and slightly to the left of P i . Far below and to the right of the P i 's, we place the F i 's such that the uppermost vertex of F σ (i) is close and connected to the leftmost vertex of F σ (i+1) , for all i ∈ [t -1]. We add a constant number of vertices in the vicinity of each P j , so that the only filter gadget that vertices β j 1 , . . . , β j t can see is F j (see Figure 12). Similarly to the point guard version, we place vertically and far from the α j i 's, one triangular pocket P(z A,q ) rooted at vertex z A,q and supported by ray(z A,q , α j i ) and ray(z A,q , α j ′ i ′ ),

for each A-interval I q = [a j i , a j ′ i ′ ] ∈ S A (Track 1). Finally, we place vertically and far from the d j i 's, one triangular pocket P(z B,q ) rooted at vertex z B,q and supported by ray(z B,q , d j i ) and ray(z B,q , d j ′ i ′ ),

for each B-interval I q = [b j σ j (i) , b j ′ σ j ′ (i ′ ) ] ∈ S B (Track 2). We make sure that, all projected on the x-axis, F σ (1) is to the right of P 1 and to the left of Track 1, so that, for every i ∈ [t], the vertex d σ (1) i sees the top edge of the gallery entirely. This ends the construction (see Figure 12).

Correctness. We now prove the correctness of the reduction. Assume that I is a YES-instance and let {(a 1 s 1 , b 1 s 1 ), . . . , (a k s k , b k s k )} be a solution. We claim that the set of vertices G = {α 1 s 1 ,

β 1 s 1 , d 1 σ -1 1 (s 1 ) , . . . , α k s k , β k s k , d k σ -1
k (s k ) } guards the whole polygon P. Let z j := d j σ -1 j (s j ) for notational convenience. By Lemma 6.1, for each j ∈ [k], the sub-polygon P j is entirely seen, since there are guards on α j s j and β j s j . By Lemma 6.2, for each j ∈ [k], all the pockets of F j are entirely seen, since there are guards on β j s j = c j σ -1 j (s j ) and d j σ -1 j (s j ) = z j . For each A-interval (resp. B-interval) in S A (resp. S B ) there is at least one 2-element (a j s j , b j s j ) such that a j s j ∈ S A (resp. b j s j ∈ S B ). Thus, the corresponding pocket is guarded by α j s j (resp. β j s j ). The rest of the polygon is seen by, for instance, z σ (1) and z σ (k ) .

We now assume that there is a set G of 3k vertices guarding P. We will show that I is a YESinstance. For each j ∈ [k], vertices b j , д j , and x j t are seen by three pairwise-disjoint sets of vertices.

The first two sets are contained in the vertices of sub-polygon P j and the third one is contained in the vertices of F j . Therefore, to see P j ∪ P(F j ) entirely, three vertices are necessary. Summing that over the k color classes, this corresponds already to 3k vertices which is the size of G. Thus, G contains a set S j of exactly 3 guards among the vertices of P j ∪ P(F j ). The guard of S j responsible for seeing д j does not see b j nor any pockets of P(F j ). Hence there are only two guards of S j performing the latter task. Therefore, by Lemma 6.2, there should be an s j ∈ [t] such that both d j s j and c j s j = β j σ j (s j ) are in G. The only vertices seeing д j are f j , д j , h j and a j 1 , . . . , a j t . As d j s j and the 3k -3 guards of G \ S j do not see the edges d j e j and x j y j at all, by Lemma 6.1, among a j 1 , . . . , a j t the only possibility for the third guard of S j is α j σ j (s j ) . We can assume that the third guard of S j is indeed α j σ j (s j ) , since f j , д j , h j do not see any pockets outside of P j (whereas α j σ j (s j ) , in principle, does in Track 1).

So far, we showed that G is of the form {α 1 σ 1 (s 1 ) , β 1 σ 1 (s 1 ) , d 1 s 1 , . . . , α j σ j (s j ) , β j σ j (s j ) , d j s j , . . . , α k σ k (s k ) ,

β k σ k (s k ) , d k s k }.

a 1 a 2 a 3 a 4 a 5 a 6 p 1 p 2 p 3 p 4 p 5 p 6 Fig. 1 .

 61 Fig. 1. Reduction from Hitting Set on interval graphs to a restricted version of the art gallery problem.

Fig. 2 .

 2 Fig. 2. Two instances of Hitting Set "magically" linked.

  x, [x] := [1, x]. Given two points a, b in the plane, we define seg(a, b) as the line segment with endpoints a, b.

Lemma 4 . 1 .

 41 k-Set Cover restricted to two-block instances with N elements and M sets is W [1]-hard and not solvable in time f (k)(N + M) o(k /log k ) for any computable function f , unless the ETH fails. Proof. We reduce from Multicolored k-Cliqe which remains W [1]-hard when each color class has the same number t of vertices. Let

Fig. 4 .

 4 Fig. 4. The sets of S b (1), S b (2), S e (1), S e (2), S(1, 2, ⊢), S(1, 2, ⊣), S(1, 2), S(2, 1) for the graph of Figure 3. The sets of S(1, 3) and S(2, 3) are also represented but only their part in A.

  empty. One can check that the produced set cover instance is still two-block and that the way of proving correctness does not change. Therefore, by Theorem 3.2, k-Set Cover restricted to two-block instances cannot be solved in time f (k)(N + M) o(k /log k ) for any computable function f , unless the ETH fails. □ In the 2-Track Hitting Set problem, the input consists of an integer k, two totally ordered ground sets A and B of the same cardinality, and two sets S A of A-intervals, and S B of B-intervals. In addition, the elements of A and B are in one-to-one correspondence ϕ : A → B and each pair (a, ϕ(a)) is called a 2-element. The goal is to find, if possible, a set S of k 2-elements such that the first projection of S is a hitting set of S A , and the second projection of S is a hitting set of S B . Structured 2-Track Hitting Set is the same problem with color classes over the 2-elements, and a restriction on the one-to-one mapping ϕ. Given two integers k and t, A is partitioned into

and b 1 i( 1 )Theorem 4 . 2 .

 1142 , . . . , b k i(k ) is a hitting set of S B . We show the ETH lower bound and W[1]-hardness for Structured 2-Track Hitting Set. The reduction is from k-Set Cover on two-block instances. We transform the unions of two intervals into 2-elements, and the elements of the k-Set Cover instance into A-intervals or B-intervals of the Structured 2-Track Hitting Set instance. Structured 2-Track Hitting Set is W [1]-hard. Furthermore it is not solvable in time f (k)|I| o(k /log k ) for any computable function f , unless the ETH fails. Proof. This result is a consequence of Lemma 4.1. Let (A ⊎ B, S) be a hard two-block instance of k-Set Cover, obtained from the previous reduction. We recall that each set S of S is the union of an A-interval with a B-interval: S = S A ⊎ S B . We transform each set S into a 2-element (x S,A , x S, B ), and each element u of the k-Set Cover instance into a set T u of the Structured 2-Track Hitting Set instance. We put element x S,A (resp. x S, B ) into set T u whenever u ∈ S ∩A = I A (resp. u ∈ S ∩ B = I B ).

2 -

 2 Track Hitting Set instance corresponds to sets in the k-Set Cover instance. We order the elements of A ′ accordingly to the following ordering of the sets of the k-Set Cover instance:S b (1), S(1, 2), . . ., S(1, k), S e (1), S b (2), S(2, 1), . . ., S(2, k), S e (2), . . ., S b (k), S(k, 1), . . ., S(k, k -1), S e (k), S(1, 2, ⊢), S(1, 2, ⊣), S(1, 3, ⊢), S(1, 3, ⊣), . . ., S(k -1, k, ⊢), S(k -1, k, ⊣).We order the elements of B ′ accordingly to the following ordering of the sets of the k-Set Cover instance:S(1, 2, ⊢), S(1, 2), S(2, 1), S(1, 2, ⊣), S(1, 3, ⊢), S(1, 3), S(3, 1), S(1, 3, ⊣), . . ., S(k -1, k, ⊢), S(k -1, k), S(k, k -1), S(k -1, k, ⊣), S b[START_REF] Abrahamsen | Irrational guards are sometimes needed[END_REF], S e (1), . . ., S b (k), S e (k). Within all those sets of sets, we order by increasing left endpoint (and then, in case of a tie, by increasing right endpoint). One can now check that with those two orders ≤ A ′ and ≤ B ′ , all the sets T u 's are A ′ -interval or B ′ -interval. Also, one can check that the 2-Track Hitting Set instance is structured by taking as color classes the partite sets S b (i)'s, S e (i)'s, S(i, j)'s, S(i, j, ⊢)'s, and S(i, j, ⊣)'s. Now, taking one 2-element in each color class to hit all the sets T u corresponds to taking one set in each partite set of S to dominate all the elements of the k-Set Cover instance. □ 2-track (unit) interval graphs are the intersection graphs of (unit) 2-track intervals, where a (unit) 2-track interval is the union of a (unit) interval in each of two parallel lines, called the first Parameterized Hardness of Art Gallery Problems 1:11

Theorem 4 . 3 (

 43 [START_REF] Marx | Optimal parameterized algorithms for planar facility location problems using voronoi diagrams[END_REF]). Given the representation of a 2-track unit interval graph, the problem of selecting k objects to dominate all the intervals is W [1]-hard, and not solvable in time f (k)n o(k /log k )

Theorem 4 . 4 (

 44 [START_REF] Jiang | On the parameterized complexity of some optimization problems related to multiple-interval graphs[END_REF]). Given the representation of a 2-track unit interval graph, the problem of selecting k objects to dominate all the objects is W [1]-hard.

Theorem 4 . 5 (

 45 [START_REF] Dom | The parameterized complexity of stabbing rectangles[END_REF]). Given the representation of a 2-track unit interval graph, the problem of selecting k intervals to dominate all the objects is W [1]-hard.

6 Fig. 6 .

 66 Fig. 6. Interval gadgets encoding {p 1 , p 2 , p 3 }, {p 2 , p 3 , p 4 , p 5 }, {p 4 , p 5 }, and {p 4 , p 5 , p 6 }.

  Algor., Vol. 1, No. 1, Article 1. Publication date: January 2020. Parameterized Hardness of Art Gallery Problems 1:13

Fig. 9 .

 9 Fig.9. The overall picture of the reduction with k = 3. The combination of P j,α, β , P j,α,α , P j,α, β , P j,r , and P j,r forces to place pairs of guards at α j i(j) , β j i(j) , analogously to the Structured 2-Track Hitting Set semantics. The y-coordinates of these points encode the total orders over A and B. The A-intervals are encoded by triangular pockets in track 1, while the B-intervals are encoded in track 2.

2 -

 2 elements {(a 1 s 1 , b 1 s 1 ), . . . , (a k s k , b k s k )} hits all the A-intervals of S A , and the B-intervals of S B . □ 6 PARAMETERIZED HARDNESS OF THE VERTEX GUARD VARIANT We now turn to the vertex guard variant and show the same hardness result. Again, we reduce from Structured 2-Track Hitting Set and our main task is to design a linker gadget. Though, linking pairs of vertices turns out to be very different from linking pairs of points. Therefore, we have to come up with fresh ideas to carry out the reduction. In a nutshell, the principal ingredient is to link pairs of convex vertices by introducing reflex vertices at strategic places. As placing guards on those reflex vertices is not supposed to happen in the Structured 2-Track Hitting Set instance, we design a so-called filter gadget to prevent any solution from doing so. Theorem 1.2 (Parameterized hardness vertex guard). Vertex Guard Art Gallery is not solvable in time f (k)n o(k /log k ) , even on simple polygons, where n is the number of vertices of the polygon and k is the number of guards allowed, for any computable function f , unless the ETH fails. Proof. From an instance I = (k ∈ N, t ∈ N, σ ∈ S k , σ 1 ∈ S t , . . . , σ k ∈ S t , S A , S B ), we build a simple polygon P with O(kt + |S A | + |S B |) vertices, such that I is a YES-instance iff P can be guarded by 3k vertices.

Fig. 12 .

 12 Fig. 12. Overall picture of the reduction with k = 5, and σ = 42531. The linker gadgets P j , together with F j , force guards at vertices α j i(j) , β j i(j) . The filter gadgets F j transmit the choice of β j i(j) and ensure that no other guard placement can be made in P j . The A-intervals of the Structured 2-Track Hitting Set instance are encoded by triangular pockets on Track 1, while the B-intervals are encoded on Track 2.

It means that α 1 σ 1 (s 1 )

 11 , . . . , α k σ k (s k ) see all the pockets of Track 1, while d 1 s 1 , . . . , d k s k see all the pockets of Track 2. Therefore the set of k 2-elements {(a1 σ 1 (s 1 ) , b 1 σ 1 (s 1 ) ), . . . , (a k σ k (s k ) , b k σ k (s k ) )}is a hitting set of both S A and S B , hence I is a YES-instance.Let us bound the number of vertices of P. Each sub-polygon P j or F j contains O(t) vertices. Track 1 contains 3|S A | vertices and Track 2 contains 3|S B | vertices. Linking everything together requires O(k) additional vertices. So, in total, there are O(kt + |S A | + |S B |) vertices. Thus, this reduction together with Theorem 4.2 implies that Vertex Guard Art Gallery is W[1]-hard and cannot be solved in time f (k)n o(k /log k ) , where n is the number of vertices of the polygon and k the number of guards, for any computable function f , unless the ETH fails. □

  for some i and j. We denote by ≤ Y the order of Y . A set-system (X , S) is said to be two-block if X can be partitioned into two totally ordered sets A = {a 1 , . . . , a |A | } and B = {b 1 , . . . , b |B | } such that each set S ∈ S is the union of an A-interval with a B-interval.

  1 1 , . . . , α 1 t . The only points that can see a rectangular pocket P j ′′ ,r and at least t pockets of P 1,α,α are on ℓ ′ 1 : they are the points ACM Trans. Algor., Vol. 1, No. 1, Article 1. Publication date: January 2020. , . . . , α 1 t . As P 1,α,α has 2t pockets, S 1 should contain two points α 1 i and α 1 i ′ . By the argument of Lemma 5.1, i should be equal to i ′ (otherwise, i < i ′ and the left pocket pointing towards α 1 i ′ -1 and

	Parameterized Hardness of Art Gallery Problems	1:17
	α 1 1

ACM Trans. Algor., Vol. 1, No. 1, Article 1. Publication date: January 2020.

By i < j ∈ [k ], we mean that i ∈ [k ], j ∈ [k ], and i < j. ACM Trans. Algor., Vol. 1, No. 1, Article 1. Publication date: January

We do not call them color classes to avoid the confusion with the color classes of the instance of Multicolored k -Cliqe. ACM Trans. Algor., Vol. 1, No. 1, Article 1. Publication date: January 2020.

* supported by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR). † supported by the ERC Consolidator Grant 615640-ForEFront. The author acknowledges generous support from the Netherlands Organisation for Scientific Research (NWO) under project no. 016.Veni.192.250.