10:12 On the Distance Identifying Set Meta-Problem

**Proposition 28.** The 1-layered gadget is a bipartite planar (*f*,*r*)-gadget for any 1-layered distance identifying function *f* and *r* ∈ [∞].

**Proposition 29.** Given a positive integer *r*, the *r*-local 0-layered gadget is a local bipartite planar (*f*, *r*)-gadget for every *r*-local 0-layered distance identifying function *f*.

**Proposition 30.** Given a positive integer *r*, the *r*-IC gadget is a local bipartite planar (*f*, *r*)-gadget for the identifying function *f* associated with *r*-IC, where $f_G[w](u, v) = \text{true if } w \in N_r[u]\Delta N_r[v]$ for relevant inputs *G*, *u*, *v* and *w*.

With Propositions 28 to 30, we can now prove the Theorems 9 to 12. We focus here on
1-layered distance identifying functions and show the other reductions in [4].

**Proof of Theorems 9 and 12 for each 1-layered identifying function f and r ∈ [∞].**

We first suggest a reduction from PLANAR HITTING SET to (*f*, *r*)-DIS based on the bipartite planar 1-layered gadget (*H*, *B*, *C*). Let (*Ω*, *S*) be an instance of PLANAR HITTING SET with |*Ω*| = *n* and |*S*| = *m* such that *m* = *O*(*n*). According to Proposition 18, the bipartite apex graph *G* = *Φ*\*[*H*, *B*](*Ω*, *S*) has size *n*' linear in *n* + *m* = *O*(*n*) and may be built in polynomial-time in its size. Recall that (*H*, *B*, *C*) is a (*f*, *r*)-gadget by Proposition 28. By Theorem 21, *G* admits a (*f*, *r*)-distance identifying set of size *k*' = *k* + |*C*|(*n* + *m*) if an only if *S* admits an hitting set of size *k*. Thus, an algorithm solving (*f*, *r*)-DIS in 2<sup>*o*(*√*n*</sup>) would solve PLANAR HITTING SET in time 2<sup>*o*(*√*n*</sup>), a contradiction to Theorem 3 (assuming ETH).

We adapt the previous argumentation to get a reduction from HITTING SET to (f, r)-DIS, the instance (Ω, S) belonging now to the HITTING SET problem. According to Proposition 23, the bipartite graph G = Ψ[H, B, 1](Ω, S) has size n' linear in n + m = O(n) and may also be built in polynomial-time in its size. By Theorem 24, G admits a (f, r)-distance identifying set of size k' = k + |C|(lg<sub>n+1</sub> + lg<sub>m</sub>) if an only if S admits an hitting set of size k. Thus, an algorithm solving (f, r)-DIS in 2<sup>o(n')</sup> would solve HITTING SET in time 2<sup>o(n)</sup>, contradicting Theorem 2 when assuming ETH. Moreover, a parameterized algorithm solving (f, r)-DIS in 2<sup>O(k)</sup> · n'<sup>O(1)</sup> would be in contradiction with Theorem 1 when assuming W[2] ≠ FPT. ◀

5 Conclusion

In this paper, we showed generic tools to analysis identifying problems and their computational lower bounds. This study opens some new questions. First of all, we observe that our toolbox does not contain a *r*-local gadget. Does one exist? Furthermore, there is still a gap between the computational lower bound provided by Theorem 12 and the elementary upper bound from Proposition 14 in the local cases. We wonder if local problems may be solved in *k*<sup>O(k)</sup> · *n*<sup>O(1)</sup>. Notice that a polynomial kernel would imply such a complexity (but the reciprocal is not true). For non-local problems, an FPT upper bound is globally unknown. In particular, W[2]-hard problems like MD cannot admit FPT algorithms unless W[2] = FPT. Then, which non-local problem is W[2]-hard? We mention that we actually get a FPT reduction from HITTING SET to some scarce non-local problems (however including MD) proving their W[2]-hardness, but the family of involved problems is not precise nor wide. Nevertheless, we remark that most of our reductions may be generalized to the oriented version of DISTANCE IDENTIFYING SET sometimes even for the strongly connected graphs –this is due to the fact that the paths in our distance identifying graphs and gadgets may often be seen as oriented–. Thus, we inform the community that the oriented version of MD (studied for Cayley graphs in [15]) remains W[2]-hard.
References

1 David Auger. Minimal identifying codes in trees and planar graphs with large girth. *Eur. J. Comb.*, 31(5):1372–1384, 2010. doi:10.1016/j.ejc.2009.11.012.

2 László Babai. On the Complexity of Canonical Labeling of Strongly Regular Graphs. *SIAM J. Comput.*, 9(1):212–216, 1980. doi:10.1137/0209018.

3 Evangelos Bampas, Davide Bilò, Guido Drovandi, Luciano Gualà, Ralf Klasing, and Guido Proietti. Network verification via routing table queries. *J. Comput. Syst. Sci.*, 81(1):234–248, 2015. doi:10.1016/j.jcss.2014.06.003.

4 Florian Barbero, Lucas Isenmann, and Jocelyn Thiebaut. On the Distance Identifying Set meta-problem and applications to the complexity of identifying problems on graphs. *ArXiv e-prints*, October 2018. doi:1810.03868.

5 Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matús Mihalák, and L. Shankar Ram. Network Discovery and Verification. *IEEE Journal on Selected Areas in Communications*, 24(12):2168–2181, 2006. doi:10.1109/JSAC.2006.884015.

6 Béla Bollobás and Alex D. Scott. On separating systems. *Eur. J. Comb.*, 28(4):1068–1071, 2007. doi:10.1016/j.ejc.2006.04.003.

7 J.A Bondy. Induced subsets. *Journal of Combinatorial Theory, Series B*, 12(2):201–202, 1972. doi:10.1016/0095-8956(72)90025-1.

8 Emmanuel Charbit, Irène Charon, Gérard D. Cohen, Olivier Hudry, and Antoine Lobstein. Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity. *Adv. in Math. of Comm.*, 2(4):403–420, 2008. doi:10.3934/amc.2008.2.403.

9 Irène Charon, Olivier Hudry, and Antoine Lobstein. Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard. *Theor. Comput. Sci.*, 290(3):2109–2120, 2003. doi:10.1016/S0304-3975(02)00536-4.

10 Gérard D. Cohen, Iiro S. Honkala, Antoine Lobstein, and Gilles Zémor. On identifying codes. In *Codes and Association Schemes, Proceedings of a DIMACS Workshop, Piscataway, New Jersey, USA, November 9-12, 1999*, pages 97–110, 1999.

11 Charles J Colbourn, Peter J Slater, and Lorna K Stewart. Locating dominating sets in series parallel networks. *Congr. Numer*, 56:135–162, 1987.

12 Josep Díaz, Olli Pottonen, Maria J. Serna, and Erik Jan van Leeuwen. On the Complexity of Metric Dimension. In *Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings*, pages 419–430, 2012. doi:10.1007/978-3-642-33090-2_37.

13 Rodney G. Downey and Michael R. Fellows. *Parameterized Complexity*. Monographs in Computer Science. Springer, 1999. doi:10.1007/978-1-4612-0515-9.

14 Leah Epstein-Asaf Levin, and Gerhard J. Woeginger. The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases. *Algorithmica*, 72(4):1130–1171, 2015. doi:10.1007/s00453-014-9896-2.

15 Melodie Fehr, Shonda Gosselin, and Ortrud R Oellermann. The metric dimension of Cayley digraphs. *Discrete Mathematics*, 306(1):31–41, 2006.

16 Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau, and Petru Valicov. Identification, Location-Domination and Metric Dimension on Interval and Permutation Graphs. II. Algorithms and Complexity. *Algorithmica*, 78(3):914–944, 2017. doi:10.1007/s00453-016-0184-1.

17 M. R. Garey and David S. Johnson. *Computers and Intractability: A Guide to the Theory of NP-Completeness*. W. H. Freeman, 1979.

18 Frank Harary and RA Melter. On the metric dimension of a graph. *Ars Combin*, 2(191-195):1, 1976.
References

1 David Auger. Minimal identifying codes in trees and planar graphs with large girth. *Eur. J. Comb.*, 31(5):1372-1384, 2010. doi:10.1016/j.ejc.2009.11.012.

2 László Babai. On the Complexity of Canonical Labeling of Strongly Regular Graphs. *SIAM J. Comput.*, 9(1):212-216, 1980. doi:10.1137/0209018.

3 Evangelos Bampas, Davide Bilò, Guido Drovandi, Luciano Gualà, Ralf Klasing, and Guido Proietti. Network verification via routing table queries. *J. Comput. Syst. Sci.*, 81(1):234-248, 2015. doi:10.1016/j.jcss.2014.06.003.

4 Florian Barbero, Lucas Isenmann, and Jocelyn Thiebaut. On the Distance Identifying Set meta-problem and applications to the complexity of identifying problems on graphs. *ArXiv e-prints*, October 2018. doi:1810.03868.

5 Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matús Mihalák, and L. Shankar Ram. Network Discovery and Verification. *IEEE Journal on Selected Areas in Communications*, 24(12):2168-2181, 2006. doi:10.1109/JSAC.2006.884015.

6 Béla Bollobás and Alex D. Scott. On separating systems. *Eur. J. Comb.*, 28(4):1068-1071, 2007. doi:10.1016/j.ejc.2006.04.003.

7 J.A Bondy. Induced subsets. *Journal of Combinatorial Theory, Series B*, 12(2):201-202, 1972. doi:10.1016/0095-8956(72)90025-1.

8 Emmanuel Charbit, Irène Charon, Gérard D. Cohen, Olivier Hudry, and Antoine Lobstein. Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity. *Adv. in Math. of Comm.*, 2(4):403-420, 2008. doi:10.3934/amc.2008.2.403.

9 Irène Charon, Olivier Hudry, and Antoine Lobstein. Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard. *Theor. Comput. Sci.*, 290(3):2109-2120, 2003. doi:10.1016/S0304-3975(02)00536-4.

10 Gérard D. Cohen, Iiro S. Honkala, Antoine Lobstein, and Gilles Zémor. On identifying codes. In *Codes and Association Schemes, Proceedings of a DIMACS Workshop, Piscataway, New Jersey, USA, November 9-12, 1999*, pages 97-110, 1999.

11 Charles J Colbourn, Peter J Slater, and Lorna K Stewart. Locating dominating sets in series parallel networks. *Congr. Numer*, 56:135-162, 1987.

12 Josep Díaz, Olli Pottonen, Maria J. Serna, and Erik Jan van Leeuwen. On the Complexity of Metric Dimension. In *Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings*, pages 419-430, 2012. doi:10.1007/978-3-642-33090-2_37.

13 Rodney G. Downey and Michael R. Fellows. *Parameterized Complexity*. Monographs in Computer Science. Springer, 1999. doi:10.1007/978-1-4612-0515-9.

14 Leah Epstein-Asaf Levin, and Gerhard J. Woeginger. The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases. *Algorithmica*, 72(4):1130-1171, 2015. doi:10.1007/s00453-014-9896-2.

15 Melodie Fehr, Shonda Gosselin, and Ortrud R Oellermann. The metric dimension of Cayley digraphs. *Discrete Mathematics*, 306(1):31-41, 2006.

16 Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau, and Petru Valicov. Identification, Location-Domination and Metric Dimension on Interval and Permutation Graphs. II. Algorithms and Complexity. *Algorithmica*, 78(3):914-944, 2017. doi:10.1007/s00453-016-0184-1.

17 M. R. Garey and David S. Johnson. *Computers and Intractability: A Guide to the Theory of NP-Completeness*. W. H. Freeman, 1979.

18 Frank Harary and RA Melter. On the metric dimension of a graph. *Ars Combin*, 2(191-195):1, 1976.
10:14 On the Distance Identifying Set Meta-Problem

19 Sepp Hartung. Exploring parameter spaces in coping with computational intractability. PhD thesis, Fakultät Elektrotechnik und Informatik der Technischen Universität Berlin, December 2014.

20 Sepp Hartung and André Nichterlein. On the Parameterized and Approximation Hardness of Metric Dimension. In *Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013*, pages 266–276, 2013. doi:10.1109/CCC.2013.36.

21 Stefan Hoffmann and Egon Wanke. Metric Dimension for Gabriel Unit Disk Graphs Is NP-Complete. In *Algorithms for Sensor Systems, 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2012, Ljubljana, Slovenia, September 13-14, 2012*. Revised Selected Papers, pages 90–92, 2012. doi:10.1007/978-3-642-36092-3_10.

22 Mark G. Karpovsky, Krishnendu Chakrabarty, and Lev B. Levitin. On a New Class of Codes for Identifying Vertices in Graphs. *IEEE Trans. Information Theory*, 44(2):599–611, 1998. doi:10.1109/18.661507.

23 Jeong Han Kim, Oleg Pikhurko, Joel H. Spencer, and Oleg Verbitsky. How complex are random graphs in first order logic? *Random Struct. Algorithms*, 26(1-2):119–145, 2005. doi:10.1002/rsa.20049.

24 Peter J Slater. Leaves of trees. *Congr. Numer*, 14(549-559):37, 1975.

25 Peter J. Slater. Domination and location in acyclic graphs. *Networks*, 17(1):55–64, 1987. doi:10.1002/net.3230170105.

26 Peter J Slater. Dominating and reference sets in a graph. *J. Math. Phys. Sci*, 22(4):445–455, 1988.

27 Simon Tippenhauer. *On Planar 3-SAT and its Variants*. PhD thesis, Freien Universität Berlin, 2016. URL: https://www.mi.fu-berlin.de/inf/groups/ag-ti/theses/download/Tippenhauer16.pdf.

28 Rachanee Ungrangsi, Ari Trachtenberg, and David Starobinski. An Implementation of Indoor Location Detection Systems Based on Identifying Codes. In *Intelligence in Communication Systems, IFIP International Conference, INTELLCOMM 2004, Bangkok, Thailand, November 23-26, 2004, Proceedings*, pages 175–189, 2004. doi:10.1007/978-3-540-30179-0_16.
10:14 On the Distance Identifying Set Meta-Problem

19 Sepp Hartung. Exploring parameter spaces in coping with computational intractability. PhD thesis, Fakultät Elektrotechnik und Informatik der Technischen Universität Berlin, December 2014.

20 Sepp Hartung and André Nichterlein. On the Parameterized and Approximation Hardness of Metric Dimension. In *Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013*, pages 266–276, 2013. doi:10.1109/CCC.2013.36.

21 Stefan Hoffmann and Egon Wanke. Metric Dimension for Gabriel Unit Disk Graphs Is NP-Complete. In *Algorithms for Sensor Systems, 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2012, Ljubljana, Slovenia, September 13-14, 2012*. Revised Selected Papers, pages 90–92, 2012. doi:10.1007/978-3-642-36092-3_10.

22 Mark G. Karpovsky, Krishnendu Chakrabarty, and Lev B. Levitin. On a New Class of Codes for Identifying Vertices in Graphs. *IEEE Trans. Information Theory*, 44(2):599–611, 1998. doi:10.1109/18.661507.

23 Jeong Han Kim, Oleg Pikhurko, Joel H. Spencer, and Oleg Verbitsky. How complex are random graphs in first order logic? *Random Struct. Algorithms*, 26(1-2):119–145, 2005. doi:10.1002/rsa.20049.

24 Peter J Slater. Leaves of trees. *Congr. Numer*, 14(549-559):37, 1975.

25 Peter J. Slater. Domination and location in acyclic graphs. *Networks*, 17(1):55–64, 1987. doi:10.1002/net.3230170105.

26 Peter J Slater. Dominating and reference sets in a graph. *J. Math. Phys. Sci*, 22(4):445–455, 1988.

27 Simon Tippenhauer. *On Planar 3-SAT and its Variants*. PhD thesis, Freien Universität Berlin, 2016. URL: https://www.mi.fu-berlin.de/inf/groups/ag-ti/theses/download/Tippenhauer16.pdf.

28 Rachanee Ungrangsi, Ari Trachtenberg, and David Starobinski. An Implementation of Indoor Location Detection Systems Based on Identifying Codes. In *Intelligence in Communication Systems, IFIP International Conference, INTELLCOMM 2004, Bangkok, Thailand, November 23-26, 2004, Proceedings*, pages 175–189, 2004. doi:10.1007/978-3-540-30179-0_16.
# The Parameterized Complexity of Finding Point Sets with Hereditary Properties

David Eppstein<fnref n="1" />

Computer Science Department, University of California, Irvine, USA
eppstein@uci.edu

Daniel Lokshtanov<fnref n="2" />

Department of Informatics, University of Bergen, Norway
dlokshtanov@gmail.com

## Abstract

We consider problems where the input is a set of points in the plane and an integer *k*, and the task is to find a subset *S* of the input points of size *k* such that *S* satisfies some property. We focus on properties that depend only on the order type of the points and are monotone under point removals. We exhibit a property defined by three forbidden patterns for which finding a *k*-point subset with the property is W[1]-complete and (assuming the exponential time hypothesis) cannot be solved in time $n^{o(k/\log k)}$. However, we show that problems of this type are fixed-parameter tractable for all properties that include all collinear point sets, properties that exclude at least one convex polygon, and properties defined by a single forbidden pattern.

**2012 ACM Subject Classification** Theory of computation → Design and analysis of algorithms

**Keywords and phrases** parameterized complexity, fixed-parameter tractability, point set pattern matching, largest pattern-avoiding subset, order type

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.11

## 1 Introduction

In this work, we study the parameterized complexity of finding subsets of planar point sets having hereditary properties, by analogy to past work on hereditary properties of graphs.

Hereditary properties of graphs have long been a central organizing principle for such diverse topics as coloring, perfection, intersection graph theory, and the theories of claw-free and triangle-free graphs. Finding the largest induced subgraph with any hereditary property is NP-hard [11, 21]. The parameterized complexity of finding a *k*-vertex induced subgraph with a given hereditary property was resolved by Khot and Raman [19]. If all cliques and all independent sets have the property, then only graphs of bounded size can fail to include a *k*-vertex induced subgraph with the property. If there exist a clique and an independent set that do not have the property, then only bounded-size induced subgraphs can have the property. In all remaining cases the problem is W[1]-complete. For hereditary properties with finitely many minimal forbidden induced subgraphs, removing *k* vertices so that the remaining induced subgraph has the property is always fixed-parameter tractable, as a hitting set problem [1, 10]. The parameterized complexity of problems of this type with more than finitely many obstacles, such as deletion to a planar graph (*k*-apex graph recognition) [5, 17] or to a bipartite graph (odd cycle transversal) [18, 20], also remains of interest.

<figure><img src="image_63.png" /></figure>

<footnote n="1">¹ Supported in part by NSF grants CCF-1618301 and CCF-1616248.</footnote>

<footnote n="2">² Supported by Pareto-Optimal Parameterized Algorithms, ERC Starting Grant 715744</footnote>
# The Parameterized Complexity of Finding Point Sets with Hereditary Properties

David Eppstein<fnref n="1" />

Computer Science Department, University of California, Irvine, USA
eppstein@uci.edu

Daniel Lokshtanov<fnref n="2" />

Department of Informatics, University of Bergen, Norway
dlokshtanov@gmail.com

## Abstract

We consider problems where the input is a set of points in the plane and an integer *k*, and the task is to find a subset *S* of the input points of size *k* such that *S* satisfies some property. We focus on properties that depend only on the order type of the points and are monotone under point removals. We exhibit a property defined by three forbidden patterns for which finding a *k*-point subset with the property is W[1]-complete and (assuming the exponential time hypothesis) cannot be solved in time $n^{o(k/\log k)}$. However, we show that problems of this type are fixed-parameter tractable for all properties that include all collinear point sets, properties that exclude at least one convex polygon, and properties defined by a single forbidden pattern.

**2012 ACM Subject Classification** Theory of computation → Design and analysis of algorithms

**Keywords and phrases** parameterized complexity, fixed-parameter tractability, point set pattern matching, largest pattern-avoiding subset, order type

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.11

## 1 Introduction

In this work, we study the parameterized complexity of finding subsets of planar point sets having hereditary properties, by analogy to past work on hereditary properties of graphs.

Hereditary properties of graphs have long been a central organizing principle for such diverse topics as coloring, perfection, intersection graph theory, and the theories of claw-free and triangle-free graphs. Finding the largest induced subgraph with any hereditary property is NP-hard [11, 21]. The parameterized complexity of finding a *k*-vertex induced subgraph with a given hereditary property was resolved by Khot and Raman [19]. If all cliques and all independent sets have the property, then only graphs of bounded size can fail to include a *k*-vertex induced subgraph with the property. If there exist a clique and an independent set that do not have the property, then only bounded-size induced subgraphs can have the property. In all remaining cases the problem is W[1]-complete. For hereditary properties with finitely many minimal forbidden induced subgraphs, removing *k* vertices so that the remaining induced subgraph has the property is always fixed-parameter tractable, as a hitting set problem [1, 10]. The parameterized complexity of problems of this type with more than finitely many obstacles, such as deletion to a planar graph (*k*-apex graph recognition) [5, 17] or to a bipartite graph (odd cycle transversal) [18, 20], also remains of interest.

<figure><img src="image_66.png" /></figure>

<footnote n="1">¹ Supported in part by NSF grants CCF-1618301 and CCF-1616248.</footnote>

<footnote n="2">² Supported by Pareto-Optimal Parameterized Algorithms, ERC Starting Grant 715744</footnote>
11:2 The Parameterized Complexity of Finding Point Sets with Hereditary Properties

Point sets in the Euclidean plane can be described combinatorially by their order type, the specification for each ordered triple of points of whether that triple forms the vertices of a triangle in clockwise or counterclockwise order, or whether the three points are collinear. It is natural to define a hereditary property of point sets to be a property that depends only on the order type, and that remains true for every subset of a point set having the property. This concept of hereditary properties has been adopted recently as a central organizing principle in discrete geometry [8] and encompasses many famous and well-studied problems:

■ The *happy ending problem* concerns conditions that force some *k*-point subset to be in convex position [9, 24]. The property of not containing a *k*-point convex subset is hereditary [8, Chapter 11]. It can be tested in polynomial time for points in the plane [6,7], but is NP-hard in three dimensions, and finding the largest 3d *k*-point convex set that does not enclose any other input points is W[1]-hard [12].

■ The *no-three-in-line problem* concerns the size of the largest general-position subset of an $n \times n$ grid [15, 23]. Here, “general position” means having no three collinear points. The property of not containing a *k*-point general-position subset is hereditary [8, Chapter 9].

■ The *Erdős–Ulam problem* asks whether there exist dense sets with all distances rational [25]; *Harborth’s conjecture* is that every planar graph can be drawn with non-crossing straight edges of rational length [16]. The existence of a rational-distance point set with the same order type as the given point set is hereditary. If every general-position order type has a rational-distance realization then *Harborth’s conjecture* follows, and if not then the *Erdős–Ulam problem* has a negative answer [8, Section 13.5].

Every hereditary property can be defined by its *forbidden patterns*, the point-minimal order types that do not have the property. The first author’s recent book on these problems asked whether every problem of finding *k* points with a hereditary property defined by finitely many forbidden patterns is fixed-parameter tractable [8, Open Problem 7.6]. We answer this question negatively, by finding a property for which (under standard complexity-theoretic assumptions) no FPT algorithm exists. However, we show that several natural classes of properties have fixed-parameter tractable algorithms. Specifically, we show:

■ There exists a hereditary property Π, defined by finitely many forbidden patterns, such that finding a *k*-point subset with property Π is W[1]-complete and (assuming the exponential time hypothesis) cannot be solved in time $n^{o(k/\log k)}$).

■ Finding a *k*-point subset with a given hereditary property is fixed-parameter tractable whenever all collinear sets have the property.

■ Finding a *k*-point subset with a given hereditary property is fixed-parameter tractable whenever there exists a convex polygon that does not have the property.

■ Finding a *k*-point subset that avoids a single forbidden pattern is fixed-parameter tractable. As with the analogous graph problems, the dual problem of removing *k* points to make the remaining points have a given property is fixed-parameter tractable whenever the property has finitely many forbidden patterns, as a hitting set problem for the copies of the patterns within the point set [8, Theorem 7.9].

Our algorithmic results apply to any model of point set input that allows us to determine the orientation of a triple of points in constant (or polynomial) time. For points given by Cartesian coordinates, these orientations can be determined from the sign of a quadratic polynomial of these coordinates. Not all order types can be realized with integer coordinates, and even when this is possible a realization may need very large coordinates [13], but our algorithms could instead use inputs that specify an $n \times n \times n$ three-dimensional array of orientations. The point sets used for our hardness results and lower bounds can be constructed using explicit integer coordinates of polynomial magnitude.
11:2 The Parameterized Complexity of Finding Point Sets with Hereditary Properties

Point sets in the Euclidean plane can be described combinatorially by their order type, the specification for each ordered triple of points of whether that triple forms the vertices of a triangle in clockwise or counterclockwise order, or whether the three points are collinear. It is natural to define a hereditary property of point sets to be a property that depends only on the order type, and that remains true for every subset of a point set having the property. This concept of hereditary properties has been adopted recently as a central organizing principle in discrete geometry [8] and encompasses many famous and well-studied problems:

■ The *happy ending problem* concerns conditions that force some *k*-point subset to be in convex position [9, 24]. The property of not containing a *k*-point convex subset is hereditary [8, Chapter 11]. It can be tested in polynomial time for points in the plane [6,7], but is NP-hard in three dimensions, and finding the largest 3d *k*-point convex set that does not enclose any other input points is W[1]-hard [12].

- The *no-three-in-line problem* concerns the size of the largest general-position subset of an $n \times n$ grid [15, 23]. Here, “general position” means having no three collinear points. The property of not containing a *k*-point general-position subset is hereditary [8, Chapter 9].

■ The *Erdős–Ulam problem* asks whether there exist dense sets with all distances rational [25]; *Harborth’s conjecture* is that every planar graph can be drawn with non-crossing straight edges of rational length [16]. The existence of a rational-distance point set with the same order type as the given point set is hereditary. If every general-position order type has a rational-distance realization then *Harborth’s conjecture* follows, and if not then the *Erdős–Ulam problem* has a negative answer [8, Section 13.5].

Every hereditary property can be defined by its *forbidden patterns*, the point-minimal order types that do not have the property. The first author’s recent book on these problems asked whether every problem of finding *k* points with a hereditary property defined by finitely many forbidden patterns is fixed-parameter tractable [8, Open Problem 7.6]. We answer this question negatively, by finding a property for which (under standard complexity-theoretic assumptions) no FPT algorithm exists. However, we show that several natural classes of properties have fixed-parameter tractable algorithms. Specifically, we show:

- There exists a hereditary property Π, defined by finitely many forbidden patterns, such that finding a *k*-point subset with property Π is W[1]-complete and (assuming the exponential time hypothesis) cannot be solved in time $n^{o(k/\log k)}$).

- Finding a *k*-point subset with a given hereditary property is fixed-parameter tractable whenever all collinear sets have the property.

■ Finding a *k*-point subset with a given hereditary property is fixed-parameter tractable whenever there exists a convex polygon that does not have the property.

- Finding a *k*-point subset that avoids a single forbidden pattern is fixed-parameter tractable. As with the analogous graph problems, the dual problem of removing *k* points to make the remaining points have a given property is fixed-parameter tractable whenever the property has finitely many forbidden patterns, as a hitting set problem for the copies of the patterns within the point set [8, Theorem 7.9].

Our algorithmic results apply to any model of point set input that allows us to determine the orientation of a triple of points in constant (or polynomial) time. For points given by Cartesian coordinates, these orientations can be determined from the sign of a quadratic polynomial of these coordinates. Not all order types can be realized with integer coordinates, and even when this is possible a realization may need very large coordinates [13], but our algorithms could instead use inputs that specify an $n \times n \times n$ three-dimensional array of orientations. The point sets used for our hardness results and lower bounds can be constructed using explicit integer coordinates of polynomial magnitude.
<figure><img src="image_64.png" /><figcaption>Figure 1 The three forbidden patterns for a compliant point set.</figcaption></figure>

## 2 A hard property

The property for which we will prove finding a $k$-point subset hard is defined by the three forbidden patterns in Figure 1: four points in a line (left), an eight-point pattern based on a complete quadrilateral$^3$ (center), and a nine-point pattern resembling a tic-tac-toe board or $3 \times 3$ grid, but with the central vertical line broken rather than straight (right). We call a set of points *compliant* if it does not contain any of these three patterns.

The hard inputs to our problem will be point sets of a special form, which we call *yards*. A yard consists of points with the following properties:

- Most of its points are arranged onto horizontal lines of at least three points per line, which we call *rows*. We call the leftmost and rightmost points of each row the *guards* of the row (or more specifically the left and right guards, respectively). We call the remaining points, that are neither leftmost nor rightmost in their row, the *inmates*.

- Some triples of points from different rows form non-horizontal lines of three points, but there are no non-horizontal lines of four points.

- Every line between two inmates of different rows passes completely above or completely below all left guards, and completely below or completely above (respectively) all right guards. Similarly, every line through two left guards or through two right guards passes completely above or completely below all inmates. (These points may determine vertical lines, which we consider to pass above and below all points.)

- The only lines of three or more points with both inmate and guard points are rows.

- No subset of nine guards forms the configuration on the right of Figure 1.

- In addition to the points on rows, the yard has six additional points, forming a complete quadrilateral. We call these points the *fence*.

- The only lines of three or more points that include points of the fence are the four lines from which the fence was defined. No other six points of the yard form a complete quadrilateral.

- The fence encloses the inmates but not the guards. Every two inmates on a single row, plus the fence, form the middle forbidden pattern of Figure 1, and every instance of the middle forbidden pattern is formed in this way.

An example of a yard is shown in Figure 2. For a yard with $r$ rows, we define a *lineup* to be a compliant subset of $k = 3r + 6$ points from the yard.

**► Lemma 1.** Every lineup must consist of all six points of the fence, and two guards and one inmate from each row. Whenever three rows have the property that their three left guards and their three right guards form two collinear triples of points, the three inmates of the lineup from these rows must also be collinear.

<footnote>$^3$ A *complete quadrilateral* consists of four lines and six points, with each line containing three points and each point contained in two lines. It can be constructed from four Euclidean lines, no two parallel and no three crossing in a single point, by including the six crossing points of pairs of lines.</footnote>
<figure><img src="image_67.png" /><figcaption>■ **Figure 1** The three forbidden patterns for a compliant point set.</figcaption></figure>

## 2 A hard property

The property for which we will prove finding a $k$-point subset hard is defined by the three forbidden patterns in Figure 1: four points in a line (left), an eight-point pattern based on a complete quadrilateral$^3$ (center), and a nine-point pattern resembling a tic-tac-toe board or $3 \times 3$ grid, but with the central vertical line broken rather than straight (right). We call a set of points *compliant* if it does not contain any of these three patterns.

The hard inputs to our problem will be point sets of a special form, which we call *yards*. A yard consists of points with the following properties:

- Most of its points are arranged onto horizontal lines of at least three points per line, which we call *rows*. We call the leftmost and rightmost points of each row the *guards* of the row (or more specifically the left and right guards, respectively). We call the remaining points, that are neither leftmost nor rightmost in their row, the *inmates*.

- Some triples of points from different rows form non-horizontal lines of three points, but there are no non-horizontal lines of four points.

- Every line between two inmates of different rows passes completely above or completely below all left guards, and completely below or completely above (respectively) all right guards. Similarly, every line through two left guards or through two right guards passes completely above or completely below all inmates. (These points may determine vertical lines, which we consider to pass above and below all points.)

- The only lines of three or more points with both inmate and guard points are rows.

- No subset of nine guards forms the configuration on the right of Figure 1.

- In addition to the points on rows, the yard has six additional points, forming a complete quadrilateral. We call these points the *fence*.

- The only lines of three or more points that include points of the fence are the four lines from which the fence was defined. No other six points of the yard form a complete quadrilateral.

- The fence encloses the inmates but not the guards. Every two inmates on a single row, plus the fence, form the middle forbidden pattern of Figure 1, and every instance of the middle forbidden pattern is formed in this way.

An example of a yard is shown in Figure 2. For a yard with $r$ rows, we define a *lineup* to be a compliant subset of $k = 3r + 6$ points from the yard.

**► Lemma 1.** Every lineup must consist of all six points of the fence, and two guards and one inmate from each row. Whenever three rows have the property that their three left guards and their three right guards form two collinear triples of points, the three inmates of the lineup from these rows must also be collinear.

<footnote>$^3$ A *complete quadrilateral* consists of four lines and six points, with each line containing three points and each point contained in two lines. It can be constructed from four Euclidean lines, no two parallel and no three crossing in a single point, by including the six crossing points of pairs of lines.</footnote>
<figure><img src="image_65.png" /><figcaption>■ **Figure 2** A yard with three rows. The fence and its points are shown in red; the rows and their guards are blue, and the inmates on each row are yellow. The green lines are the most far from vertical among the lines through pairs of inmates that are not both on the same row as each other; they can be used to verify that all non-horizontal and non-vertical lines through pairs of inmates pass above or below the guards on each side, and that no pair of inmates on different rows from each other forms a forbidden pattern with the fence. By Lemma 1, every lineup in this yard consists of all of the blue and red points together with three collinear yellow points, one from each row. In this example all the left guards and all the right guards are collinear, but in larger examples only certain triples of guards would be collinear.</figcaption></figure>

**Proof.** The forbidden four-point line forces the lineup to contain at most three points from each row, so if it contains $3r + 6$ points it must include exactly three points from each row and all six points of the fence. The forbidden pattern in the form of a complete quadrilateral plus two points forces the lineup to contain at most one inmate from each row, so in order for it to contain three points from each row it must contain both guards.

If the three left guards and the three right guards of a triple of rows are collinear (as they are in Figure 2), then the three inmates of the lineup from the same three rows must also be collinear. For otherwise, they would form the forbidden pattern on the right of Figure 1, either as shown or under a $180^\circ$ rotation (which causes no change to the order type of the configuration). Therefore, every such triple of inmates must be collinear. ◀

Lemma 1 is not a necessary and sufficient condition (for instance, it is possible to have a subset of points that meets the condition of the lemma but contains a copy of the rightmost forbidden pattern, rotated by $90^\circ$) but we will see that it is necessary and sufficient for the yards constructed by the reduction that we describe next.

We prove hardness of finding lineups in yards via a parameterized reduction from *partitioned subgraph isomorphism*. This problem's input consists of two graphs, a *host graph* $H$ and a *pattern graph* $G$, whose sizes (numbers of edges) are $n$ and $k$ respectively. The vertices of $G$ and $H$ are colored, with all vertices of $G$ having distinct colors. The problem is to find a subgraph of $H$ that is isomorphic to $G$ and matches it in coloring. Thus, the color classes of $H$ partition its vertices. We must choose a representative vertex from each color class so that whenever two vertices in $G$ are adjacent their representatives in $H$ are also adjacent. The color partition of the vertices in $H$ is what gives rise to the name, partitioned subgraph isomorphism. In our hardness reduction, we will consider a restricted case of this problem, *cubic partitioned subgraph isomorphism*, in which we require the pattern graph $G$ to be a cubic (that is, 3-regular) graph. $H$ is not restricted. This problem is $W[1]$-complete and, assuming the exponential time hypothesis, cannot be solved in time $n^{o(k/\log k)}$.
<figure><img src="image_68.png" /><figcaption>■ **Figure 2** A yard with three rows. The fence and its points are shown in red; the rows and their guards are blue, and the inmates on each row are yellow. The green lines are the most far from vertical among the lines through pairs of inmates that are not both on the same row as each other; they can be used to verify that all non-horizontal and non-vertical lines through pairs of inmates pass above or below the guards on each side, and that no pair of inmates on different rows from each other forms a forbidden pattern with the fence. By Lemma 1, every lineup in this yard consists of all of the blue and red points together with three collinear yellow points, one from each row. In this example all the left guards and all the right guards are collinear, but in larger examples only certain triples of guards would be collinear.</figcaption></figure>

**Proof.** The forbidden four-point line forces the lineup to contain at most three points from each row, so if it contains $3r + 6$ points it must include exactly three points from each row and all six points of the fence. The forbidden pattern in the form of a complete quadrilateral plus two points forces the lineup to contain at most one inmate from each row, so in order for it to contain three points from each row it must contain both guards.

If the three left guards and the three right guards of a triple of rows are collinear (as they are in Figure 2), then the three inmates of the lineup from the same three rows must also be collinear. For otherwise, they would form the forbidden pattern on the right of Figure 1, either as shown or under a $180^\circ$ rotation (which causes no change to the order type of the configuration). Therefore, every such triple of inmates must be collinear. ◀

Lemma 1 is not a necessary and sufficient condition (for instance, it is possible to have a subset of points that meets the condition of the lemma but contains a copy of the rightmost forbidden pattern, rotated by $90^\circ$) but we will see that it is necessary and sufficient for the yards constructed by the reduction that we describe next.

We prove hardness of finding lineups in yards via a parameterized reduction from *partitioned subgraph isomorphism*. This problem's input consists of two graphs, a *host graph* $H$ and a *pattern graph* $G$, whose sizes (numbers of edges) are $n$ and $k$ respectively. The vertices of $G$ and $H$ are colored, with all vertices of $G$ having distinct colors. The problem is to find a subgraph of $H$ that is isomorphic to $G$ and matches it in coloring. Thus, the color classes of $H$ partition its vertices. We must choose a representative vertex from each color class so that whenever two vertices in $G$ are adjacent their representatives in $H$ are also adjacent. The color partition of the vertices in $H$ is what gives rise to the name, partitioned subgraph isomorphism. In our hardness reduction, we will consider a restricted case of this problem, *cubic partitioned subgraph isomorphism*, in which we require the pattern graph $G$ to be a cubic (that is, 3-regular) graph. $H$ is not restricted. This problem is $W[1]$-complete and, assuming the exponential time hypothesis, cannot be solved in time $n^{o(k/\log k)}$.
Cubic partitioned subgraph isomorphism has been used for the same sort of hardness reduction previously [3, 4]. The W[1]-completeness of partitioned subgraph isomorphism appears to be folklore, but it has a straightforward proof by reduction from the W[1]-complete clique problem.<fnref n="4" /> In turn, partitioned subgraph isomorphism on graphs of minimum degree at least three can be reduced to the 3-regular case by expanding each high-degree vertex into a 3-regular tree, as follows:

- Choose for each vertex $v$ of the pattern graph a tree $T_v$ having degree three at each internal vertex and having the neighbors of $v$ as its leaves. Let $T'_v$ be the subtree of $T_v$ consisting only of the interior nodes of $T_v$.

- Form the disjoint union of the trees $T'_v$. For each edge $uv$ of the pattern graph add an edge to this union, connecting the node in $T'_u$ to which the leaf for $v$ is attached to the node in $T'_v$ to which the leaf for $u$ is attached.

- For each vertex $w$ of the host graph, having the same color as a vertex $v$ of the pattern graph, make a tree $T'_w$ isomorphic to $T'_v$. Form a new host graph from the disjoint union of these trees $T'_w$.

- For each pair of vertices $wx$ of the host graph such that $w$ has the same color as a vertex $u$ of the pattern graph, $x$ has the same color as a vertex $v$ of the pattern graph, $u$ and $v$ are adjacent, and $w$ and $x$ are adjacent, add an edge to this union, connecting the node in $T'_w$ corresponding to the one in $T'_u$ to which the leaf for $v$ would be attached with the node in $T'_x$ corresponding to the one in $T'_v$ to which the leaf for $u$ would be attached.

The ETH-x lower bounds on cubic partitioned subgraph isomorphism come from Corollary 6.1 of Marx [22], using the fact that a cubic expander graph $G$ has treewidth $\Omega(k)$ [14].

To translate an instance of cubic partitioned subgraph isomorphism to the problem of finding lineups in yards, we construct a yard with a row for each vertex or edge of the pattern graph $G$. We will arrange the guards and inmates of the yard in such a way that collinearities of guards correspond to vertex-edge incidences in the pattern graph, and collinearities of inmates correspond to vertex-edge incidences in the host graph. In this way, every lineup of the yard will necessarily correspond to a solution to the partitioned subgraph isomorphism instance. We take some care in the construction in order to ensure that the resulting yard uses only points with integer coordinates of small magnitude.

The rows of the yard will be placed on horizontal lines, with positive integer $y$-coordinate $y_v$ or $y_{uv}$ for each vertex $v$ or edge $uv$ of the pattern graph. It will be convenient to be able to place arbitrary integer-coordinate points on two vertex rows and have the intersection of the line through these points with an edge row automatically be an integer-coordinate point. To ensure this property, we will always choose $y_{uv} = 2y_v - y_u$ (where $y_v > y_u$). However, this requires that we choose the coordinates $y_u$ and $y_v$ carefully, so that no two vertices or edges have rows with equal $y$-coordinates. We make this choice greedily, choosing the coordinates $y_v$ for the vertices in an arbitrary order. For each vertex $v$ in this order, we choose $y_v$ to be the smallest positive integer that obeys the following constraints:

- $y_v$ is unequal to any $y_u$ for an earlier vertex $u$

- $y_v$ is unequal to any $y_{uw}$ for any two adjacent earlier vertices $u$ and $w$

<footnote n="4">⁴ The reduction uses the tensor product of graphs $G \times H$ of graphs $G$ and $H$. This product has as vertices the pairs $(u, v)$ where $u$ is a vertex in $G$ and $v$ is a vertex in $H$. Pairs $(u, v)$ and $(u', v')$ are adjacent if and only if either $u = u'$ and $v$ is adjacent to $v'$, or $v = v'$ and $u$ is adjacent to $u'$. If we properly color $K_k$ and assign each vertex $(u, v)$ in $G \times K_k$ the same color as $v$, then $G$ has a $k$-clique if and only if the partitioned subgraph isomorphism instance for $G \times K_k$ and $K_k$ (with these colors) has a solution. This reduction proves the W[1]-completeness of partitioned subgraph isomorphism problem from the known completeness of the clique problem.</footnote>
Cubic partitioned subgraph isomorphism has been used for the same sort of hardness reduction previously [3, 4]. The W[1]-completeness of partitioned subgraph isomorphism appears to be folklore, but it has a straightforward proof by reduction from the W[1]-complete clique problem.<fnref n="4" /> In turn, partitioned subgraph isomorphism on graphs of minimum degree at least three can be reduced to the 3-regular case by expanding each high-degree vertex into a 3-regular tree, as follows:

- Choose for each vertex $v$ of the pattern graph a tree $T_v$ having degree three at each internal vertex and having the neighbors of $v$ as its leaves. Let $T'_v$ be the subtree of $T_v$ consisting only of the interior nodes of $T_v$.

- Form the disjoint union of the trees $T'_v$. For each edge $uv$ of the pattern graph add an edge to this union, connecting the node in $T'_u$ to which the leaf for $v$ is attached to the node in $T'_v$ to which the leaf for $u$ is attached.

- For each vertex $w$ of the host graph, having the same color as a vertex $v$ of the pattern graph, make a tree $T'_w$ isomorphic to $T'_v$. Form a new host graph from the disjoint union of these trees $T'_w$.

- For each pair of vertices $wx$ of the host graph such that $w$ has the same color as a vertex $u$ of the pattern graph, $x$ has the same color as a vertex $v$ of the pattern graph, $u$ and $v$ are adjacent, and $w$ and $x$ are adjacent, add an edge to this union, connecting the node in $T'_w$ corresponding to the one in $T'_u$ to which the leaf for $v$ would be attached with the node in $T'_x$ corresponding to the one in $T'_v$ to which the leaf for $u$ would be attached.

The ETH-x lower bounds on cubic partitioned subgraph isomorphism come from Corollary 6.1 of Marx [22], using the fact that a cubic expander graph $G$ has treewidth $\Omega(k)$ [14].

To translate an instance of cubic partitioned subgraph isomorphism to the problem of finding lineups in yards, we construct a yard with a row for each vertex or edge of the pattern graph $G$. We will arrange the guards and inmates of the yard in such a way that collinearities of guards correspond to vertex-edge incidences in the pattern graph, and collinearities of inmates correspond to vertex-edge incidences in the host graph. In this way, every lineup of the yard will necessarily correspond to a solution to the partitioned subgraph isomorphism instance. We take some care in the construction in order to ensure that the resulting yard uses only points with integer coordinates of small magnitude.

The rows of the yard will be placed on horizontal lines, with positive integer $y$-coordinate $y_v$ or $y_{uv}$ for each vertex $v$ or edge $uv$ of the pattern graph. It will be convenient to be able to place arbitrary integer-coordinate points on two vertex rows and have the intersection of the line through these points with an edge row automatically be an integer-coordinate point. To ensure this property, we will always choose $y_{uv} = 2y_v - y_u$ (where $y_v > y_u$). However, this requires that we choose the coordinates $y_u$ and $y_v$ carefully, so that no two vertices or edges have rows with equal $y$-coordinates. We make this choice greedily, choosing the coordinates $y_v$ for the vertices in an arbitrary order. For each vertex $v$ in this order, we choose $y_v$ to be the smallest positive integer that obeys the following constraints:

- $y_v$ is unequal to any $y_u$ for an earlier vertex $u$

- $y_v$ is unequal to any $y_{uw}$ for any two adjacent earlier vertices $u$ and $w$

<footnote n="4">⁴ The reduction uses the tensor product of graphs $G \times H$ of graphs $G$ and $H$. This product has as vertices the pairs $(u, v)$ where $u$ is a vertex in $G$ and $v$ is a vertex in $H$. Pairs $(u, v)$ and $(u', v')$ are adjacent if and only if either $u = u'$ and $v$ is adjacent to $v'$, or $v = v'$ and $u$ is adjacent to $u'$. If we properly color $K_k$ and assign each vertex $(u, v)$ in $G \times K_k$ the same color as $v$, then $G$ has a $k$-clique if and only if the partitioned subgraph isomorphism instance for $G \times K_k$ and $K_k$ (with these colors) has a solution. This reduction proves the W[1]-completeness of partitioned subgraph isomorphism problem from the known completeness of the clique problem.</footnote>
11:6 The Parameterized Complexity of Finding Point Sets with Hereditary Properties

- $y_v$ does not make any $y_u = y_{vx}$ for any earlier vertex $u$ and earlier neighbor $x$ of $v$

- $y_v$ does not make $y_{uw} = y_{vx}$ for any three earlier vertices $u, w$, or $x$ with $u$ adjacent to $w$ and $x$ to $v$.

These conditions are each determined by at most one earlier vertex $u$, at most one of three neighbors $w$ of $u$, and at most one of three neighbors $x$ of $v$. For each combination of these vertices, each condition causes one integer to be unavailable as a choice for $y_v$. Therefore, $O(k)$ positive integers are unavailable. Because our greedy algorithm chooses the first available integer in each case, it chooses all coordinates $y_v$ and $y_{uv}$ to have magnitude $O(k)$. Our actual row coordinates will be scaled and translated from these values, but both of these kinds of transformations preserve the property that two integer points on vertex rows determine an integer point on an edge row.

The first points we determine in the construction are the six points of the fence. We construct a complete quadrilateral with integer coordinates, by using lines with rational coefficients and then clearing denominators. We scale it by a sufficiently large factor so that there are as many integer-coordinate horizontal lines through the fence as we need rows (given the assignment of row coordinates to vertices and edges of the pattern graph) and so that each row intersects the region inside the fence in a segment of length proportional to the diameter of the fence. We scale these fences and rows a second time, by a polynomially-large factor $\phi$, to ensure that the following steps can be carried out using integer coordinates for the remaining points. We leave $\phi$ unspecified for now, and will later state constraints on how large it needs to be for the construction to work.

Next, we choose three intervals on the $x$-coordinate axis: a left interval that will contain the $x$-coordinates of all left guards, a middle interval that will contain the $x$-coordinates of all inmates, and a right interval that will contain the $x$-coordinates of all right guards. The middle interval should be chosen so that its intersection with all row lines is inside the fence (using the fact that there is a vertical line segment inside the fence that crosses all row lines) and the left and right intervals should intersect all row lines outside the fence, on either side of it. inside the fence and the left and right intervals should be outside it, on either side of the fence. These intervals should be sufficiently narrow that all lines through pairs of points on corresponding intervals of different rows pass in the correct way above or below the points of the fence and the intervals of other types. In order to prevent an inmate from being collinear with two guards from other rows than its own, we also require that there be no line that crosses a row line in the left interval, a second row line in the middle interval, and a third row line in the right interval. In order to achieve this, it will be sufficient to choose the interval widths to be smaller than the diameter of the fence by a sufficiently large factor $\rho$. With this factor, we can choose the left and right guard intervals first, arbitrarily subject to the above constraints. Given this choice, let $C$ be the set of crossing points of the rows with non-horizontal lines through potential left and right guard points. Then $C$ is a union of a cubic number of intervals (one for each triple of rows). Each of these intervals defining $C$ is wider than the left and right intervals by a factor of $O(k)$, because the slopes of the lines through points within the left and right intervals on different rows are bounded away from zero by $\Omega(1/k)$. Therefore, the projection of $C$ onto the $x$-axis has length $O(k^4/\rho)$ relative to the diameter of the fence. For $\rho = \rho_0 k^4$ for a sufficiently large constant factor $\rho_0$, a constant fraction of the length within the fence will remain disjoint from $C$, and at least one interval within this constant fraction of the length will be long enough to use as the middle interval.

After these choices, we place the two guards on each row, with the left guard having its $x$-coordinate within the left interval and the right guard within the right interval. We choose the positions of the *vertex guards* (the guards on the rows that correspond to vertices of the
11:6 The Parameterized Complexity of Finding Point Sets with Hereditary Properties

- $y_v$ does not make any $y_u = y_{vx}$ for any earlier vertex $u$ and earlier neighbor $x$ of $v$

- $y_v$ does not make $y_{uw} = y_{vx}$ for any three earlier vertices $u, w$, or $x$ with $u$ adjacent to $w$ and $x$ to $v$.

These conditions are each determined by at most one earlier vertex $u$, at most one of three neighbors $w$ of $u$, and at most one of three neighbors $x$ of $v$. For each combination of these vertices, each condition causes one integer to be unavailable as a choice for $y_v$. Therefore, $O(k)$ positive integers are unavailable. Because our greedy algorithm chooses the first available integer in each case, it chooses all coordinates $y_v$ and $y_{uv}$ to have magnitude $O(k)$. Our actual row coordinates will be scaled and translated from these values, but both of these kinds of transformations preserve the property that two integer points on vertex rows determine an integer point on an edge row.

The first points we determine in the construction are the six points of the fence. We construct a complete quadrilateral with integer coordinates, by using lines with rational coefficients and then clearing denominators. We scale it by a sufficiently large factor so that there are as many integer-coordinate horizontal lines through the fence as we need rows (given the assignment of row coordinates to vertices and edges of the pattern graph) and so that each row intersects the region inside the fence in a segment of length proportional to the diameter of the fence. We scale these fences and rows a second time, by a polynomially-large factor $\phi$, to ensure that the following steps can be carried out using integer coordinates for the remaining points. We leave $\phi$ unspecified for now, and will later state constraints on how large it needs to be for the construction to work.

Next, we choose three intervals on the $x$-coordinate axis: a left interval that will contain the $x$-coordinates of all left guards, a middle interval that will contain the $x$-coordinates of all inmates, and a right interval that will contain the $x$-coordinates of all right guards. The middle interval should be chosen so that its intersection with all row lines is inside the fence (using the fact that there is a vertical line segment inside the fence that crosses all row lines) and the left and right intervals should intersect all row lines outside the fence, on either side of it. inside the fence and the left and right intervals should be outside it, on either side of the fence. These intervals should be sufficiently narrow that all lines through pairs of points on corresponding intervals of different rows pass in the correct way above or below the points of the fence and the intervals of other types. In order to prevent an inmate from being collinear with two guards from other rows than its own, we also require that there be no line that crosses a row line in the left interval, a second row line in the middle interval, and a third row line in the right interval. In order to achieve this, it will be sufficient to choose the interval widths to be smaller than the diameter of the fence by a sufficiently large factor $\rho$. With this factor, we can choose the left and right guard intervals first, arbitrarily subject to the above constraints. Given this choice, let $C$ be the set of crossing points of the rows with non-horizontal lines through potential left and right guard points. Then $C$ is a union of a cubic number of intervals (one for each triple of rows). Each of these intervals defining $C$ is wider than the left and right intervals by a factor of $O(k)$, because the slopes of the lines through points within the left and right intervals on different rows are bounded away from zero by $\Omega(1/k)$. Therefore, the projection of $C$ onto the $x$-axis has length $O(k^4/\rho)$ relative to the diameter of the fence. For $\rho = \rho_0 k^4$ for a sufficiently large constant factor $\rho_0$, a constant fraction of the length within the fence will remain disjoint from $C$, and at least one interval within this constant fraction of the length will be long enough to use as the middle interval.

After these choices, we place the two guards on each row, with the left guard having its $x$-coordinate within the left interval and the right guard within the right interval. We choose the positions of the *vertex guards* (the guards on the rows that correspond to vertices of the
pattern graph), one at a time. As each vertex guard is placed, it may also determine the location of one or more *edge guards* (the guards on the rows that correspond to edges of the pattern graph). An edge guard's location is determined when the vertex guards for its two endpoints have been placed. Whenever this happens, we place the edge guard at the point where the line through the two vertex guards crosses the edge's row. In order to ensure that the edge guards are placed within the left and right intervals, we place each vertex guard within the middle third of its interval. In this way, for each edge *uv* of the pattern graph we will produce two collinear triples of guards: the triple of left guards for *u*, *v*, and *uv*, and the triple of right guards for *u*, *v*, and *uv*. We will position the vertex guards in sufficiently general position so that these are the only collinearities between triples of guards. As with our choice of row coordinates, we achieve this absence of extra collinearities by a greedy algorithm, in which we place one vertex guard at a time, subject to the constraint that this choice should not create any undesired collinearities between the new vertex guard, the new edge guards whose position becomes determined by the new vertex guard, and the previously determined vertex and edge guards. Each potential undesired collinearity is determined by the choice of two previous guard positions (for which there are $O(k)$ choices) and possibly one of the three neighbors of the vertex whose guard we are trying to place. This implies that, when we are placing each vertex guard, there may be up to $O(k^2)$ positions that we should not place it, because placing it in one of those positions would cause a collinearity. Recall that, when constructing the fence, we left a scaling factor $\phi$ undetermined, and that the left and right interval each contain $\Omega(k\phi/\rho)$ integer coordinates, where $\rho = O(k^4)$ is the factor by which the intervals are narrower than the diameter of the fence and where the factor of $k$ comes from the earlier scaling used to make the fence big enough to include as many integer-coordinate rows as we need. We will choose our scaling factor $\phi$ to be large enough (at least a sufficiently large multiple of $k^5$) to ensure that the middle thirds of the left and right intervals contain more integer coordinates than the number of unavailable positions. With this choice of $\phi$, our greedy guard-placing strategy will always be able to determine a valid integer-coordinate placement for each vertex guard point. By our previous choice of the row coordinates, the edge guard points will also have integer coordinates.

Finally, we place the inmates on each row, within the middle interval. Each edge or vertex of the host graph corresponds to exactly one inmate point, which we place on the row for the corresponding edge or vertex of the pattern graph, given by the coloring of the host graph vertex or the coloring of the endpoints of the host graph edge. We choose the locations for these inmate points in exactly the same way as we chose them for the guard points, greedily one vertex at a time, with the vertex guards placed within the middle third of the middle interval. We place each edge inmate point on the intersection between each edge row and the line through the inmate points for its two endpoints, as soon as these two vertex inmate points have been placed. This will cause each triple of an edge and its two endpoints in the host graph to correspond to three collinear inmate points. We require in addition that no three inmate points on different rows are collinear if they do not form such a triple, and that no two points on the same row as each other coincide. Each potential undesired collinearity is determined by the choice of two previous guard positions (for which there are $O(n^2)$ choices, as the host graph may be dense) and possibly one of up to $O(n)$ neighbors of the vertex whose guard we are trying to place. This implies that there may be $O(n^5)$ positions in the row of the new vertex guard that would cause an unwanted collinearity or coincidence. We will choose our scaling factor $\phi$ to be large enough (at least a sufficiently large multiple of $k^3n^5$) to ensure that the middle third of the middle interval in which we place the inmate points contains more integer coordinates than this number of unavailable positions. In this way, we ensure the success of our greedy inmate-placing strategy.
pattern graph), one at a time. As each vertex guard is placed, it may also determine the location of one or more *edge guards* (the guards on the rows that correspond to edges of the pattern graph). An edge guard's location is determined when the vertex guards for its two endpoints have been placed. Whenever this happens, we place the edge guard at the point where the line through the two vertex guards crosses the edge's row. In order to ensure that the edge guards are placed within the left and right intervals, we place each vertex guard within the middle third of its interval. In this way, for each edge *uv* of the pattern graph we will produce two collinear triples of guards: the triple of left guards for *u*, *v*, and *uv*, and the triple of right guards for *u*, *v*, and *uv*. We will position the vertex guards in sufficiently general position so that these are the only collinearities between triples of guards. As with our choice of row coordinates, we achieve this absence of extra collinearities by a greedy algorithm, in which we place one vertex guard at a time, subject to the constraint that this choice should not create any undesired collinearities between the new vertex guard, the new edge guards whose position becomes determined by the new vertex guard, and the previously determined vertex and edge guards. Each potential undesired collinearity is determined by the choice of two previous guard positions (for which there are $O(k)$ choices) and possibly one of the three neighbors of the vertex whose guard we are trying to place. This implies that, when we are placing each vertex guard, there may be up to $O(k^2)$ positions that we should not place it, because placing it in one of those positions would cause a collinearity. Recall that, when constructing the fence, we left a scaling factor $\phi$ undetermined, and that the left and right interval each contain $\Omega(k\phi/\rho)$ integer coordinates, where $\rho = O(k^4)$ is the factor by which the intervals are narrower than the diameter of the fence and where the factor of $k$ comes from the earlier scaling used to make the fence big enough to include as many integer-coordinate rows as we need. We will choose our scaling factor $\phi$ to be large enough (at least a sufficiently large multiple of $k^5$) to ensure that the middle thirds of the left and right intervals contain more integer coordinates than the number of unavailable positions. With this choice of $\phi$, our greedy guard-placing strategy will always be able to determine a valid integer-coordinate placement for each vertex guard point. By our previous choice of the row coordinates, the edge guard points will also have integer coordinates.

Finally, we place the inmates on each row, within the middle interval. Each edge or vertex of the host graph corresponds to exactly one inmate point, which we place on the row for the corresponding edge or vertex of the pattern graph, given by the coloring of the host graph vertex or the coloring of the endpoints of the host graph edge. We choose the locations for these inmate points in exactly the same way as we chose them for the guard points, greedily one vertex at a time, with the vertex guards placed within the middle third of the middle interval. We place each edge inmate point on the intersection between each edge row and the line through the inmate points for its two endpoints, as soon as these two vertex inmate points have been placed. This will cause each triple of an edge and its two endpoints in the host graph to correspond to three collinear inmate points. We require in addition that no three inmate points on different rows are collinear if they do not form such a triple, and that no two points on the same row as each other coincide. Each potential undesired collinearity is determined by the choice of two previous guard positions (for which there are $O(n^2)$ choices, as the host graph may be dense) and possibly one of up to $O(n)$ neighbors of the vertex whose guard we are trying to place. This implies that there may be $O(n^5)$ positions in the row of the new vertex guard that would cause an unwanted collinearity or coincidence. We will choose our scaling factor $\phi$ to be large enough (at least a sufficiently large multiple of $k^3n^5$) to ensure that the middle third of the middle interval in which we place the inmate points contains more integer coordinates than this number of unavailable positions. In this way, we ensure the success of our greedy inmate-placing strategy.
<figure><img src="image_66.png" /><figcaption>Figure 3 Illustration for the proof of Lemma 2.</figcaption></figure>

**Lemma 2.** *The translation described above constructs a yard.*

**Proof.** The construction explicitly ensures that most properties of a yard are true: there is a fence, and rows of points, each having two guards outside the fence and inmates inside the fence. There are no non-horizontal lines of four points, and all non-horizontal lines defined by pairs of guards or pairs of inmates pass above or below the other points and through the fence in the proper manner. There are no lines of three points that include both guards and inmates and are not rows. It remains to verify two properties, not stated explicitly as part of the construction: there must be no complete quadrilateral other than the fence, and no subset of guards that form the forbidden pattern on the right of Figure 1.

If either of these forbidden patterns existed, but did not include three points from the same row of the configuration, then all of its three-point lines would have to be non-horizontal lines, composed only of guards or only of inmates. But an edge point can only participate in one such line, and both forbidden patterns include at least one line all three points of which participate in two three-point lines. So all three of the points on this line would have to be vertex points, an impossibility.

The only remaining possibility is a complete quadrilateral that uses at least one row as one of its lines. Let $a$ and $b$ be any two points of this row, and choose $c, d$, and $e$ so $acd$ and $bce$ are distinct lines of the quadrilateral. Then triples $acd$ and $ade$ must each be the crossing points of their lines with three rows that correspond in $G$ to an edge and its two endpoints. The choice of the row through $a$ and $b$, and a second row through $c$, determines the third row, which must therefore include both $d$ and $e$. But then lines $ab$ and $de$ are parallel, and cannot intersect to produce the sixth point of a complete quadrilateral (Figure 3). ◀

**Lemma 3.** *An instance $(H, G, c)$ of partitioned subgraph isomorphism (where $c$ is the coloring of the instance) is solvable if and only if the yard constructed from it admits a lineup.*

**Proof.** If a lineup exists, it must include all fence and guard points, and one inmate from each row. This choice of the inmate for each row selects one vertex or edge from the host graph $H$, of the appropriate color class (or pair of endpoint color classes), for each vertex or edge in the pattern graph $G$. If the selected collection of vertices and edges in $H$ does not form an isomorph of $G$, it will include two vertices $u$ and $v$ in $H$ that are adjacent in $G$ but for which the edge $uv$ does not exist in $H$, or has not been selected by the choice of inmate for its row. In this case, the guards for the rows of $u, v$, and $uv$ will be collinear in triples (because the corresponding vertices in $G$ are adjacent) but the inmates will not be collinear, creating an instance of the forbidden pattern on the right of Figure 1. So when $H$ does not contain a subgraph isomorphic to $G$, the yard admits no lineup.

If $H$ does contain a subgraph isomorphic to $G$, we can choose the points corresponding to the vertices and edges of that subgraph as the inmates of a lineup. As the following case analysis shows, the resulting system of points does not include any forbidden pattern.
<figure><img src="image_69.png" /><figcaption>Figure 3 Illustration for the proof of Lemma 2.</figcaption></figure>

**▶ Lemma 2.** *The translation described above constructs a yard.*

**Proof.** The construction explicitly ensures that most properties of a yard are true: there is a fence, and rows of points, each having two guards outside the fence and inmates inside the fence. There are no non-horizontal lines of four points, and all non-horizontal lines defined by pairs of guards or pairs of inmates pass above or below the other points and through the fence in the proper manner. There are no lines of three points that include both guards and inmates and are not rows. It remains to verify two properties, not stated explicitly as part of the construction: there must be no complete quadrilateral other than the fence, and no subset of guards that form the forbidden pattern on the right of Figure 1.

If either of these forbidden patterns existed, but did not include three points from the same row of the configuration, then all of its three-point lines would have to be non-horizontal lines, composed only of guards or only of inmates. But an edge point can only participate in one such line, and both forbidden patterns include at least one line all three points of which participate in two three-point lines. So all three of the points on this line would have to be vertex points, an impossibility.

The only remaining possibility is a complete quadrilateral that uses at least one row as one of its lines. Let $a$ and $b$ be any two points of this row, and choose $c, d$, and $e$ so $acd$ and $bce$ are distinct lines of the quadrilateral. Then triples $acd$ and $ade$ must each be the crossing points of their lines with three rows that correspond in $G$ to an edge and its two endpoints. The choice of the row through $a$ and $b$, and a second row through $c$, determines the third row, which must therefore include both $d$ and $e$. But then lines $ab$ and $de$ are parallel, and cannot intersect to produce the sixth point of a complete quadrilateral (Figure 3). ◀

**▶ Lemma 3.** *An instance $(H, G, c)$ of partitioned subgraph isomorphism (where $c$ is the coloring of the instance) is solvable if and only if the yard constructed from it admits a lineup.*

**Proof.** If a lineup exists, it must include all fence and guard points, and one inmate from each row. This choice of the inmate for each row selects one vertex or edge from the host graph $H$, of the appropriate color class (or pair of endpoint color classes), for each vertex or edge in the pattern graph $G$. If the selected collection of vertices and edges in $H$ does not form an isomorph of $G$, it will include two vertices $u$ and $v$ in $H$ that are adjacent in $G$ but for which the edge $uv$ does not exist in $H$, or has not been selected by the choice of inmate for its row. In this case, the guards for the rows of $u, v$, and $uv$ will be collinear in triples (because the corresponding vertices in $G$ are adjacent) but the inmates will not be collinear, creating an instance of the forbidden pattern on the right of Figure 1. So when $H$ does not contain a subgraph isomorphic to $G$, the yard admits no lineup.

If $H$ does contain a subgraph isomorphic to $G$, we can choose the points corresponding to the vertices and edges of that subgraph as the inmates of a lineup. As the following case analysis shows, the resulting system of points does not include any forbidden pattern.
■ It does not include four points in a line.

■ Because it has only one inmate on each row and the fence is the only complete quadrilateral in the yard, it does not include the middle forbidden pattern in Figure 1.

■ It does not include a copy of the right forbidden pattern in which none of its lines are rows, or in which only one of the vertical lines is a row, because in that case (as in Lemma 2) the other vertical line would be a line of three points, each of which belongs to two non-row lines of three points. This is an impossibility because the points on edge rows only belong to one non-row three-point line, and each non-row three-point line includes at least one of these edge points.

■ It does not include a copy of the right forbidden pattern in which only one or two of its horizontal lines is a row, because then the two vertical lines could only be lines through three guards. This would force the remaining horizontal lines to contain a left guard, a right guard, and a point between them, and therefore be rows themselves.

■ It does not include a copy of the right forbidden pattern with two rows as its two three-point vertical lines. If these rows represent two vertices $u$ and $v$ of $G$, the three points not on these lines would belong to the row for edge $uv$, as they belong to a line containing a representative for $u$ and a representative for $v$. If the rows represent a vertex $u$ and edge $uv$ of $G$, the three points not on these lines would all belong to the row for vertex $v$. In either case these points form another line, unlike the forbidden pattern.

■ The only remaining possibility is that the three horizontal lines of this pattern are rows. To form this pattern, the guards of these three rows must be collinear, meaning that they represent two adjacent vertices and the edge between them in $G$. But since we have selected the inmates on each row to form a correctly-colored subgraph isomorphic to $G$, the three inmates must also be collinear, preventing the forbidden pattern from occurring. Thus, the selected points form a lineup of the yard, as required. ◀

By combining these results with the known hardness of partitioned subgraph isomorphism we obtain our main result:

**Theorem 4.** *Finding a $k$-vertex compliant subset of a given $n$-point set is $W[1]$-complete and, under the exponential time hypothesis, cannot be solved in time $n^{o(k/\log k)}$.*

### 3 Collinearity and convex subsets

We have claimed that finding a $k$-point subset with a given hereditary property is fixed-parameter tractable whenever the property is true for all collinear sets, or whenever there exists a convex polygon for which the property is not true. We split the proof into cases:

■ Properties that are true for all collinear point sets and for all convex polygons.

■ Properties that are neither true for all collinear point sets nor for all convex polygons.

■ Properties that are true for all collinear point sets but not true for all convex polygons. However, the first two cases follow easily from known results.

The first case covers properties that are true for all collinear subsets and for all convex polygons. By the happy ending theorem, every $n$ points in the plane include $\Omega(\log n)$ points that are either all collinear or all in convex position. So, if property $\Pi$ is true for all collinear subsets and for all convex polygons (the first case), then every sufficiently large point set has a $k$-point subset with property $\Pi$. Here, “sufficiently large” means large enough that this $\Omega(\log n)$ bound is at least $k$. For smaller values of $n$ we can search by brute force all subsets of the point set in time that is fixed-parameter tractable in $k$, because (for these values) $n$ itself is bounded by a function of $k$. For larger values of $n$, we can either just answer yes (for
■ It does not include four points in a line.

■ Because it has only one inmate on each row and the fence is the only complete quadrilateral in the yard, it does not include the middle forbidden pattern in Figure 1.

■ It does not include a copy of the right forbidden pattern in which none of its lines are rows, or in which only one of the vertical lines is a row, because in that case (as in Lemma 2) the other vertical line would be a line of three points, each of which belongs to two non-row lines of three points. This is an impossibility because the points on edge rows only belong to one non-row three-point line, and each non-row three-point line includes at least one of these edge points.

■ It does not include a copy of the right forbidden pattern in which only one or two of its horizontal lines is a row, because then the two vertical lines could only be lines through three guards. This would force the remaining horizontal lines to contain a left guard, a right guard, and a point between them, and therefore be rows themselves.

■ It does not include a copy of the right forbidden pattern with two rows as its two three-point vertical lines. If these rows represent two vertices $u$ and $v$ of $G$, the three points not on these lines would belong to the row for edge $uv$, as they belong to a line containing a representative for $u$ and a representative for $v$. If the rows represent a vertex $u$ and edge $uv$ of $G$, the three points not on these lines would all belong to the row for vertex $v$. In either case these points form another line, unlike the forbidden pattern.

■ The only remaining possibility is that the three horizontal lines of this pattern are rows. To form this pattern, the guards of these three rows must be collinear, meaning that they represent two adjacent vertices and the edge between them in $G$. But since we have selected the inmates on each row to form a correctly-colored subgraph isomorphic to $G$, the three inmates must also be collinear, preventing the forbidden pattern from occurring. Thus, the selected points form a lineup of the yard, as required. ◀

By combining these results with the known hardness of partitioned subgraph isomorphism we obtain our main result:

**Theorem 4.** *Finding a $k$-vertex compliant subset of a given $n$-point set is $W[1]$-complete and, under the exponential time hypothesis, cannot be solved in time $n^{o(k/\log k)}$.*

## 3 Collinearity and convex subsets

We have claimed that finding a $k$-point subset with a given hereditary property is fixed-parameter tractable whenever the property is true for all collinear sets, or whenever there exists a convex polygon for which the property is not true. We split the proof into cases:

■ Properties that are true for all collinear point sets and for all convex polygons.

■ Properties that are neither true for all collinear point sets nor for all convex polygons.

■ Properties that are true for all collinear point sets but not true for all convex polygons. However, the first two cases follow easily from known results.

The first case covers properties that are true for all collinear subsets and for all convex polygons. By the happy ending theorem, every $n$ points in the plane include $\Omega(\log n)$ points that are either all collinear or all in convex position. So, if property $\Pi$ is true for all collinear subsets and for all convex polygons (the first case), then every sufficiently large point set has a $k$-point subset with property $\Pi$. Here, “sufficiently large” means large enough that this $\Omega(\log n)$ bound is at least $k$. For smaller values of $n$ we can search by brute force all subsets of the point set in time that is fixed-parameter tractable in $k$, because (for these values) $n$ itself is bounded by a function of $k$. For larger values of $n$, we can either just answer yes (for
<figure><img src="image_67.png" /><figcaption>Figure 4 If $G$ (blue) is a maximal general-position subset of $P$, the remaining points of $P$ (yellow) must be covered by lines through pairs of points in $G$, or else they could be added to $G$.</figcaption></figure>

a decision problem) or reduce the input arbitrarily to the smallest number of points that ensures the existence of a solution (a number bounded by a function of $k$) and then perform a brute force search for a solution within the reduced subproblem.

The second case covers properties that exclude a collinear subset and a convex polygon. By the happy ending theorem, sets of points with the property have bounded size (at most some number $p$ independent of the parameter $k$), because all sufficiently large sets contain a collinear or convex subset without the property, and by heredity do not have the property themselves. To test whether there exists a $k$-point subset with such a property, we answer no immediately when $k > p$. Otherwise we perform a brute-force search over all subsets of the input of size $k$. The time for this search is $O(n^p)$, a polynomial with constant exponent.

We now detail a fixed-point-tractable solution for the remaining case.

**Lemma 5.** Let decidable hereditary property $\Pi$ be true for all collinear point sets but not true for all convex polygons. Then it is fixed-parameter tractable to find a $k$-point subset having property $\Pi$, among a given set of points in the plane.

**Proof.** It is straightforward, in polynomial time, to find all lines through pairs of input points and determine whether any of these lines contains $k$ or more points. If so, we can immediately return a subset of $k$ collinear points. So for the remainder of the proof we assume without loss of generality that each line contains at most $k-1$ input points.

Let $q$ be the smallest number of vertices in a convex polygon that does not have property $\Pi$. By assumption, $q$ exists, and by the definition of hereditary properties, any set of points containing the vertices of a convex $q$-gon does not have property $\Pi$. Let $r$ be the largest number of points in a set of points in general position (no three in a line) that does not include a convex $q$-gon; by Suk's improvement to the happy ending theorem [24], $r \le 2^{q+o(q)}$. Let $P$ be the unknown $k$-point subset (assuming it exists), and $G$ be a maximal subset of $P$ that is in general position (meaning that no other point from $P$ can be added to $G$ without creating a three-point line). Then $|G| \le r$, or else $G$ and $P$ would contain a convex $q$-gon and $P$ would not have property $\Pi$. The pairs of points in $G$ determine $\binom{|G|}{2} \le \binom{r}{2}$ lines, and these lines together must cover all of $P$, or else $G$ would not be maximal (Figure 4).

Therefore, we can solve the problem of finding a $k$-point subset $P$ with property $\Pi$ by guessing an $\binom{r}{2}$-tuple of lines that cover $P$, among all $\binom{n}{2}$ lines through pairs of input points, and then for each tuple of lines performing a brute-force search among the points covered by those lines. Because $r$ is a constant (depending on $\Pi$ but not on the input parameter $k$), there are a polynomial number of tuples of lines to be searched. Each tuple covers at most $(k-1)\binom{r}{2}$ points, so performing each brute-force search takes time bounded by a function of $k$, independent of the input size. Therefore, this algorithm is fixed-parameter tractable. $\quad$
<figure><img src="image_70.png" /><figcaption>Figure 4 If $G$ (blue) is a maximal general-position subset of $P$, the remaining points of $P$ (yellow) must be covered by lines through pairs of points in $G$, or else they could be added to $G$.</figcaption></figure>

a decision problem) or reduce the input arbitrarily to the smallest number of points that ensures the existence of a solution (a number bounded by a function of $k$) and then perform a brute force search for a solution within the reduced subproblem.

The second case covers properties that exclude a collinear subset and a convex polygon. By the happy ending theorem, sets of points with the property have bounded size (at most some number $p$ independent of the parameter $k$), because all sufficiently large sets contain a collinear or convex subset without the property, and by heredity do not have the property themselves. To test whether there exists a $k$-point subset with such a property, we answer no immediately when $k > p$. Otherwise we perform a brute-force search over all subsets of the input of size $k$. The time for this search is $O(n^p)$, a polynomial with constant exponent.

We now detail a fixed-point-tractable solution for the remaining case.

**Lemma 5.** Let decidable hereditary property $\Pi$ be true for all collinear point sets but not true for all convex polygons. Then it is fixed-parameter tractable to find a $k$-point subset having property $\Pi$, among a given set of points in the plane.

**Proof.** It is straightforward, in polynomial time, to find all lines through pairs of input points and determine whether any of these lines contains $k$ or more points. If so, we can immediately return a subset of $k$ collinear points. So for the remainder of the proof we assume without loss of generality that each line contains at most $k-1$ input points.

Let $q$ be the smallest number of vertices in a convex polygon that does not have property $\Pi$. By assumption, $q$ exists, and by the definition of hereditary properties, any set of points containing the vertices of a convex $q$-gon does not have property $\Pi$. Let $r$ be the largest number of points in a set of points in general position (no three in a line) that does not include a convex $q$-gon; by Suk's improvement to the happy ending theorem [24], $r \le 2^{q+o(q)}$. Let $P$ be the unknown $k$-point subset (assuming it exists), and $G$ be a maximal subset of $P$ that is in general position (meaning that no other point from $P$ can be added to $G$ without creating a three-point line). Then $|G| \le r$, or else $G$ and $P$ would contain a convex $q$-gon and $P$ would not have property $\Pi$. The pairs of points in $G$ determine $\binom{|G|}{2} \le \binom{r}{2}$ lines, and these lines together must cover all of $P$, or else $G$ would not be maximal (Figure 4).

Therefore, we can solve the problem of finding a $k$-point subset $P$ with property $\Pi$ by guessing an $\binom{r}{2}$-tuple of lines that cover $P$, among all $\binom{n}{2}$ lines through pairs of input points, and then for each tuple of lines performing a brute-force search among the points covered by those lines. Because $r$ is a constant (depending on $\Pi$ but not on the input parameter $k$), there are a polynomial number of tuples of lines to be searched. Each tuple covers at most $(k-1)\binom{r}{2}$ points, so performing each brute-force search takes time bounded by a function of $k$, independent of the input size. Therefore, this algorithm is fixed-parameter tractable. $\quad$
This completes the last case of the following result:

**Theorem 6.** Let decidable hereditary property $\Pi$ either be true for all collinear point sets or not be true for at least one convex polygon (or both). Then it is fixed-parameter tractable to find a $k$-point subset having property $\Pi$, among a given set of points in the plane.

Not every hereditary property is decidable: there are uncountably many hereditary properties,<fnref n="5" /> only countably many of which are decidable. When a hereditary property is not decidable, the same technique applies, but (because of the need to test the property within each brute-force search used as a subroutine of the algorithms) it gives us a non-uniform fixed-parameter tractable algorithm.

# 4 Properties with a single obstacle

If $X$ is any fixed point set, we can define hereditary property $\Pi_X$ to be true for the point sets that do not contain $X$, and false otherwise. We are then interested in testing whether a given input includes $k$ points with property $\Pi_X$. That is, are there at least $k$ points in the largest point set that avoids $X$? If $X$ is not itself collinear, then all collinear point sets have property $\Pi_X$. Therefore, there is only one family of possible choices for $X$ that is not already covered by Theorem 6: the family of sets $X$ consisting of $q$ points on a single line. The order type of any such point set depends only on $q$. We call a point set with this order type $L_q$.

**Lemma 7.** Let $q$ be fixed. Then it is fixed-parameter tractable to find a $k$-point subset avoiding $L_q$, among a given set of points in the plane.

**Proof.** We assume $q > 2$ for otherwise the problem is trivial (an $L_2$-avoiding set can only be a single point, and an $L_1$-avoiding set must be empty). We begin by finding a maximal subset $G$ of the input that is in general position (no three in a line). If $|G| \ge k$, we return any $k$ points from $G$ as our $k$-point $L_q$-avoiding set. Otherwise, as in Lemma 5 and Figure 4, the input can be covered by at most $\binom{k-1}{2}$ lines, the lines through pairs of points in $G$.

Observe that, on each of these lines, an $L_q$-avoiding set can include at most $q-1$ points from the line. Consider a single line $\ell$ and a process in which we build up a $k$-point $L_q$-avoiding set, one point at a time, starting from a subset of points that are disjoint from $\ell$ and then adding points from $\ell$ in an arbitrary order. At each step of this process, at most $q-2$ points from $\ell$ have already been chosen, and the next point must be chosen to be disjoint from these already-chosen points and from any of the lines through pairs of points (neither on $\ell$) that already contain $q-1$ points. There at most $\binom{k-1}{2}$ of these lines through pairs of already-chosen points (because we have already chosen at most $k-1$ points), and each can prevent only a single point of $\ell$ from being chosen. So, as long as $\ell$ contains $\binom{k-1}{2} + q-1$ points, there will always remain at least one point that is free to be added until we have included exactly $q-1$ points from $\ell$. Therefore, if we reduce the input to contain any arbitrary subset of $\binom{k-1}{2} + q-1$ points on $\ell$, keeping the points disjoint from $\ell$ unchanged, we cannot affect the existence or nonexistence of a $k$-point $L_q$-avoiding subset.

<footnote n="5">⁵ This follows from the fact that there are infinite families of point sets in which no family member has the same order type as a subset of another family member. For example, the set of vertices and edge midpoints of a convex $r$-gon is not a subset of the set of vertices and edge midpoints of any other convex polygon, so choosing one such point set for each $r$ gives a family of point sets none of which have the order type of a subset of another. This family has uncountably many subfamilies, each of which forms the set of forbidden patterns for a hereditary property. See [8, Observation 5.9].</footnote>
This completes the last case of the following result:

**Theorem 6.** Let decidable hereditary property $\Pi$ either be true for all collinear point sets or not be true for at least one convex polygon (or both). Then it is fixed-parameter tractable to find a $k$-point subset having property $\Pi$, among a given set of points in the plane.

Not every hereditary property is decidable: there are uncountably many hereditary properties,<fnref n="5" /> only countably many of which are decidable. When a hereditary property is not decidable, the same technique applies, but (because of the need to test the property within each brute-force search used as a subroutine of the algorithms) it gives us a non-uniform fixed-parameter tractable algorithm.

# 4 Properties with a single obstacle

If $X$ is any fixed point set, we can define hereditary property $\Pi_X$ to be true for the point sets that do not contain $X$, and false otherwise. We are then interested in testing whether a given input includes $k$ points with property $\Pi_X$. That is, are there at least $k$ points in the largest point set that avoids $X$? If $X$ is not itself collinear, then all collinear point sets have property $\Pi_X$. Therefore, there is only one family of possible choices for $X$ that is not already covered by Theorem 6: the family of sets $X$ consisting of $q$ points on a single line. The order type of any such point set depends only on $q$. We call a point set with this order type $L_q$.

**Lemma 7.** Let $q$ be fixed. Then it is fixed-parameter tractable to find a $k$-point subset avoiding $L_q$, among a given set of points in the plane.

**Proof.** We assume $q > 2$ for otherwise the problem is trivial (an $L_2$-avoiding set can only be a single point, and an $L_1$-avoiding set must be empty). We begin by finding a maximal subset $G$ of the input that is in general position (no three in a line). If $|G| \ge k$, we return any $k$ points from $G$ as our $k$-point $L_q$-avoiding set. Otherwise, as in Lemma 5 and Figure 4, the input can be covered by at most $\binom{k-1}{2}$ lines, the lines through pairs of points in $G$.

Observe that, on each of these lines, an $L_q$-avoiding set can include at most $q-1$ points from the line. Consider a single line $\ell$ and a process in which we build up a $k$-point $L_q$-avoiding set, one point at a time, starting from a subset of points that are disjoint from $\ell$ and then adding points from $\ell$ in an arbitrary order. At each step of this process, at most $q-2$ points from $\ell$ have already been chosen, and the next point must be chosen to be disjoint from these already-chosen points and from any of the lines through pairs of points (neither on $\ell$) that already contain $q-1$ points. There at most $\binom{k-1}{2}$ of these lines through pairs of already-chosen points (because we have already chosen at most $k-1$ points), and each can prevent only a single point of $\ell$ from being chosen. So, as long as $\ell$ contains $\binom{k-1}{2} + q-1$ points, there will always remain at least one point that is free to be added until we have included exactly $q-1$ points from $\ell$. Therefore, if we reduce the input to contain any arbitrary subset of $\binom{k-1}{2} + q-1$ points on $\ell$, keeping the points disjoint from $\ell$ unchanged, we cannot affect the existence or nonexistence of a $k$-point $L_q$-avoiding subset.

<footnote n="5">⁵ This follows from the fact that there are infinite families of point sets in which no family member has the same order type as a subset of another family member. For example, the set of vertices and edge midpoints of a convex $r$-gon is not a subset of the set of vertices and edge midpoints of any other convex polygon, so choosing one such point set for each $r$ gives a family of point sets none of which have the order type of a subset of another. This family has uncountably many subfamilies, each of which forms the set of forbidden patterns for a hereditary property. See [8, Observation 5.9].</footnote>
11:12 The Parameterized Complexity of Finding Point Sets with Hereditary Properties

By applying this observation repeatedly we can kernelize the problem. That is, we find a polynomial-time algorithm that reduces any parameterized instance to an equivalent instance (the “kernel”) whose size is bounded by a function of the parameter. To do so, we consider the lines through pairs of points of $G$, one at a time. Whenever any such line contains more than $\binom{k-1}{2} + q - 1$ points of the remaining input, we delete arbitrarily chosen points until it contains exactly $\binom{k-1}{2} + q - 1$ points. At the end of this process, the total number of remaining points is at most $\binom{k-1}{2} (\binom{k-1}{2} + q - 1) = O(k^4)$, depending only on $k$. We may then find a $k$-point $L_q$-avoiding subset by a brute force search of this kernel. ◀

This includes as a special case the problem of finding an $L_3$-avoiding subset (that is, a subset in general position), the central computational task for the no-3-in-line problem. (We already proved this special case to be NP-hard in [8, Theorem 9.3] and fixed-parameter tractable in [8, Theorem 9.5].) It completes the last case of the following result:

► **Theorem 8.** Let $X$ be any fixed finite set of points. Then it is fixed-parameter tractable to find a $k$-point subset avoiding $X$, among a given set of points in the plane.

5 Conclusions

We have identified a hereditary property of point sets such that finding a $k$-point subset with this property is unlikely to be fixed-parameter tractable, and identified several general classes of properties for which the corresponding problems are fixed-parameter tractable. These include properties that include all collinear sets, properties that exclude a convex polygon, and properties with a single obstacle. Several additional cases are fixed-parameter tractable:

- The largest convex subset (avoiding two forbidden patterns, one of three points on a line and the other of a triangle with an interior point) is polynomially solvable, in cubic time and linear space [6, 7].

- If finding $k$-point subsets is fixed-parameter tractable for two properties $\Pi$ and $\Pi'$, then it is also fixed-parameter tractable for their disjunction (the point sets that have at least one of the two properties), by running both algorithms and returning any $k$-point set found by either of them.

- If finding $k$-point subsets is fixed-parameter tractable for property $\Pi$, then it is also fixed-parameter tractable for the property $\Pi_q$ of being partitionable into $q$ subsets that have property $\Pi$, by color-coding [2]. Alternatively one could use a different hereditary property for each color class.

We have been unable to complete a classification of which of these problems are fixed-parameter tractable and which are not. We leave this as open for future research.

Another open problem concerns properties (such as being in convex position) that can be true only of point sets in general position. That is, these properties have a three-point line as one of their forbidden patterns. Can it be hard, for such a property, to find a $k$-point subset with the property? We suspect that the answer is yes, by a reduction that mimics the one we have given, using more complex constraints on general-position subsets of points to make them act like the collinear subsets of points in our reduction. However, we have not worked out the details of such a reduction.
11:12 The Parameterized Complexity of Finding Point Sets with Hereditary Properties

By applying this observation repeatedly we can kernelize the problem. That is, we find a polynomial-time algorithm that reduces any parameterized instance to an equivalent instance (the “kernel”) whose size is bounded by a function of the parameter. To do so, we consider the lines through pairs of points of $G$, one at a time. Whenever any such line contains more than $\binom{k-1}{2} + q - 1$ points of the remaining input, we delete arbitrarily chosen points until it contains exactly $\binom{k-1}{2} + q - 1$ points. At the end of this process, the total number of remaining points is at most $\binom{k-1}{2} (\binom{k-1}{2} + q - 1) = O(k^4)$, depending only on $k$. We may then find a $k$-point $L_q$-avoiding subset by a brute force search of this kernel. ◀

This includes as a special case the problem of finding an $L_3$-avoiding subset (that is, a subset in general position), the central computational task for the no-3-in-line problem. (We already proved this special case to be NP-hard in [8, Theorem 9.3] and fixed-parameter tractable in [8, Theorem 9.5].) It completes the last case of the following result:

► **Theorem 8.** Let $X$ be any fixed finite set of points. Then it is fixed-parameter tractable to find a $k$-point subset avoiding $X$, among a given set of points in the plane.

5 Conclusions

We have identified a hereditary property of point sets such that finding a $k$-point subset with this property is unlikely to be fixed-parameter tractable, and identified several general classes of properties for which the corresponding problems are fixed-parameter tractable. These include properties that include all collinear sets, properties that exclude a convex polygon, and properties with a single obstacle. Several additional cases are fixed-parameter tractable:

- The largest convex subset (avoiding two forbidden patterns, one of three points on a line and the other of a triangle with an interior point) is polynomially solvable, in cubic time and linear space [6, 7].

- If finding $k$-point subsets is fixed-parameter tractable for two properties $\Pi$ and $\Pi'$, then it is also fixed-parameter tractable for their disjunction (the point sets that have at least one of the two properties), by running both algorithms and returning any $k$-point set found by either of them.

- If finding $k$-point subsets is fixed-parameter tractable for property $\Pi$, then it is also fixed-parameter tractable for the property $\Pi_q$ of being partitionable into $q$ subsets that have property $\Pi$, by color-coding [2]. Alternatively one could use a different hereditary property for each color class.

We have been unable to complete a classification of which of these problems are fixed-parameter tractable and which are not. We leave this as open for future research.

Another open problem concerns properties (such as being in convex position) that can be true only of point sets in general position. That is, these properties have a three-point line as one of their forbidden patterns. Can it be hard, for such a property, to find a $k$-point subset with the property? We suspect that the answer is yes, by a reduction that mimics the one we have given, using more complex constraints on general-position subsets of points to make them act like the collinear subsets of points in our reduction. However, we have not worked out the details of such a reduction.
References

1 Faisal N. Abu-Khzam. A kernelization algorithm for *d*-hitting set. *J. Comput. System Sci.*, 76(7):524–531, 2010. doi:10.1016/j.jcss.2009.09.002.

2 Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. *J. ACM*, 42(4):844–856, 1995. doi:10.1145/210332.210337.

3 Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, and Roman Rabinovich. Routing with congestion in acyclic digraphs. In *41st International Symposium on Mathematical Foundations of Computer Science*, volume 58 of *LIPIcs. Leibniz Int. Proc. Inform.*, pages 7:1–7:11. Schloss Dagstuhl, Leibniz-Zent. Inform., Wadern, 2016. doi:10.4230/LIPIcs.MFCS.2016.7.

4 Édouard Bonnet, Tillmann Miltzow, and Paweł Rządewski. Complexity of token swapping and its variants. *Algorithmica*, 2017. doi:10.1007/s00453-017-0387-0.

5 Glencora Borradaile, David Eppstein, and Pingan Zhu. Planar induced subgraphs of sparse graphs. *J. Graph Algorithms Appl.*, 19(1):281–297, 2015. doi:10.7155/jgaa.00358.

6 Václav Chvátal and Gheza T. Klincsek. Finding largest convex subsets. In *11th Southern Conference on Combinatorics, Graph Theory and Computing, Vol. II*, volume 29 of *Congressus Numerantium*, pages 453–460, 1980.

7 Herbert Edelsbrunner and Leonidas J. Guibas. Topologically sweeping an arrangement. *J. Comput. System Sci.*, 38(1):165–194, 1989. doi:10.1016/0022-0000(89)90038-X.

8 David Eppstein. *Forbidden Configurations in Discrete Geometry*. Cambridge University Press, 2018.

9 Paul Erdős and George Szekeres. A combinatorial problem in geometry. *Compositio Math.*, 2:463–470, 1935. URL: http://www.numdam.org/item?id=CM_1935__2__463_0.

10 Jörg Flum and Martin Grohe. 9.1 Polynomial Kernelizations. In *Parameterized Complexity Theory*, EATCS Ser. Texts in Theoretical Computer Science, pages 208–212. Springer, 2006. doi:10.1007/3-540-29953-X.

11 Michael R. Garey and David S. Johnson. GT21: Induced subgraph with property II. In *Computers and Intractability: A Guide to the Theory of NP-completeness*, page 195. W. H. Freeman, 1979.

12 Panos Giannopoulos, Christian Knauer, and Daniel Werner. On the computational complexity of Erdős-Szekeres and related problems in $R^3$. In *21st Annual European Symposium on Algorithms (ESA 2013)*, volume 8125 of *Lecture Notes in Computer Science*, pages 541–552. Springer, 2013. doi:10.1007/978-3-642-40450-4_46.

13 Jacob E. Goodman, Richard Pollack, and Bernd Sturmfels. Coordinate representation of order types requires exponential storage. In *21st Symposium on Theory of Computing (STOC '89)*, pages 405–410. ACM, 1989. doi:10.1145/73007.73046.

14 Martin Grohe and Dániel Marx. On tree width, bramble size, and expansion. *J. Combin. Theory Ser. B*, 99(1):218–228, 2009. doi:10.1016/j.jctb.2008.06.004.

15 Richard R. Hall, Terence H. Jackson, Anthony Sudbery, and Ken Wild. Some advances in the no-three-in-line problem. *J. Combin. Theory Ser. A*, 18:336–341, 1975. doi:10.1016/0097-3165(75)90043-6.

16 Heiko Harborth, Arnfried Kemnitz, Meinhard Möller, and Andreas Süssenbach. Ganzzahlige planare Darstellungen der platonischen Körper. *Elemente der Mathematik*, 42(5):118–122, 1987. URL: https://eudml.org/doc/141411.

17 Ken-ichi Kawarabayashi. Planarity allowing few error vertices in linear time. In *50th IEEE Symposium on Foundations of Computer Science (FOCS 2009)*, pages 639–648. IEEE Computer Society, Los Alamitos, CA, 2009. doi:10.1109/FOCS.2009.45.

18 Ken-ichi Kawarabayashi and Bruce Reed. An (almost) linear time algorithm for odd cycles transversal. In *21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)*, pages 365–378, Philadelphia, PA, 2010. SIAM.
References

1 Faisal N. Abu-Khzam. A kernelization algorithm for *d*-hitting set. *J. Comput. System Sci.*, 76(7):524–531, 2010. doi:10.1016/j.jcss.2009.09.002.

2 Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. *J. ACM*, 42(4):844–856, 1995. doi:10.1145/210332.210337.

3 Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, and Roman Rabinovich. Routing with congestion in acyclic digraphs. In *41st International Symposium on Mathematical Foundations of Computer Science*, volume 58 of *LIPIcs. Leibniz Int. Proc. Inform.*, pages 7:1–7:11. Schloss Dagstuhl, Leibniz-Zent. Inform., Wadern, 2016. doi:10.4230/LIPIcs.MFCS.2016.7.

4 Édouard Bonnet, Tillmann Miltzow, and Paweł Rządewski. Complexity of token swapping and its variants. *Algorithmica*, 2017. doi:10.1007/s00453-017-0387-0.

5 Glencora Borradaile, David Eppstein, and Pingan Zhu. Planar induced subgraphs of sparse graphs. *J. Graph Algorithms Appl.*, 19(1):281–297, 2015. doi:10.7155/jgaa.00358.

6 Václav Chvátal and Gheza T. Klincsek. Finding largest convex subsets. In *11th Southern Conference on Combinatorics, Graph Theory and Computing, Vol. II*, volume 29 of *Congressus Numerantium*, pages 453–460, 1980.

7 Herbert Edelsbrunner and Leonidas J. Guibas. Topologically sweeping an arrangement. *J. Comput. System Sci.*, 38(1):165–194, 1989. doi:10.1016/0022-0000(89)90038-X.

8 David Eppstein. *Forbidden Configurations in Discrete Geometry*. Cambridge University Press, 2018.

9 Paul Erdős and George Szekeres. A combinatorial problem in geometry. *Compositio Math.*, 2:463–470, 1935. URL: http://www.numdam.org/item?id=CM_1935__2__463_0.

10 Jörg Flum and Martin Grohe. 9.1 Polynomial Kernelizations. In *Parameterized Complexity Theory*, EATCS Ser. Texts in Theoretical Computer Science, pages 208–212. Springer, 2006. doi:10.1007/3-540-29953-X.

11 Michael R. Garey and David S. Johnson. GT21: Induced subgraph with property II. In *Computers and Intractability: A Guide to the Theory of NP-completeness*, page 195. W. H. Freeman, 1979.

12 Panos Giannopoulos, Christian Knauer, and Daniel Werner. On the computational complexity of Erdős-Szekeres and related problems in $R^3$. In *21st Annual European Symposium on Algorithms (ESA 2013)*, volume 8125 of *Lecture Notes in Computer Science*, pages 541–552. Springer, 2013. doi:10.1007/978-3-642-40450-4_46.

13 Jacob E. Goodman, Richard Pollack, and Bernd Sturmfels. Coordinate representation of order types requires exponential storage. In *21st Symposium on Theory of Computing (STOC '89)*, pages 405–410. ACM, 1989. doi:10.1145/73007.73046.

14 Martin Grohe and Dániel Marx. On tree width, bramble size, and expansion. *J. Combin. Theory Ser. B*, 99(1):218–228, 2009. doi:10.1016/j.jctb.2008.06.004.

15 Richard R. Hall, Terence H. Jackson, Anthony Sudbery, and Ken Wild. Some advances in the no-three-in-line problem. *J. Combin. Theory Ser. A*, 18:336–341, 1975. doi:10.1016/0097-3165(75)90043-6.

16 Heiko Harborth, Arnfried Kemnitz, Meinhard Möller, and Andreas Süssenbach. Ganzzahlige planare Darstellungen der platonischen Körper. *Elemente der Mathematik*, 42(5):118–122, 1987. URL: https://eudml.org/doc/141411.

17 Ken-ichi Kawarabayashi. Planarity allowing few error vertices in linear time. In *50th IEEE Symposium on Foundations of Computer Science (FOCS 2009)*, pages 639–648. IEEE Computer Society, Los Alamitos, CA, 2009. doi:10.1109/FOCS.2009.45.

18 Ken-ichi Kawarabayashi and Bruce Reed. An (almost) linear time algorithm for odd cycles transversal. In *21st ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)*, pages 365–378, Philadelphia, PA, 2010. SIAM.
11:14 The Parameterized Complexity of Finding Point Sets with Hereditary Properties

19 Subhash Khot and Venkatesh Raman. Parameterized complexity of finding subgraphs with hereditary properties. *Theoret. Comput. Sci.*, 289(2):997-1008, 2002. doi:10.1016/S0304-3975(01)00414-5.

20 R. Krithika and N. S. Narayanaswamy. Another disjoint compression algorithm for odd cycle transversal. *Inform. Process. Lett.*, 113(22-24):849-851, 2013. doi:10.1016/j.ipl.2013.08.007.

21 John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is NP-complete. *J. Comput. System Sci.*, 20(2):219-230, 1980. doi:10.1016/0022-0000(80)90060-4.

22 Dániel Marx. Can you beat treewidth? *Theory of Computing*, 6:85-112, 2010. doi:10.4086/toc.2010.v006a005.

23 Klaus F. Roth. On a problem of Heilbronn. *J. London Math. Soc.*, 26:198-204, 1951. doi:10.1112/jlms/s1-26.3.198.

24 Andrew Suk. On the Erdős-Szekeres convex polygon problem. *J. Amer. Math. Soc.*, 30:1047-1053, 2017. doi:10.1090/jams/869.

25 Terence Tao. The Erdos-Ulam problem, varieties of general type, and the Bombieri-Lang conjecture. In *What's new*. WordPress, December 20, 2014. URL: https://terrytao.wordpress.com/2014/12/20/.
11:14 The Parameterized Complexity of Finding Point Sets with Hereditary Properties

19 Subhash Khot and Venkatesh Raman. Parameterized complexity of finding subgraphs with hereditary properties. *Theoret. Comput. Sci.*, 289(2):997-1008, 2002. doi:10.1016/S0304-3975(01)00414-5.

20 R. Krithika and N. S. Narayanaswamy. Another disjoint compression algorithm for odd cycle transversal. *Inform. Process. Lett.*, 113(22-24):849-851, 2013. doi:10.1016/j.ipl.2013.08.007.

21 John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is NP-complete. *J. Comput. System Sci.*, 20(2):219-230, 1980. doi:10.1016/0022-0000(80)90060-4.

22 Dániel Marx. Can you beat treewidth? *Theory of Computing*, 6:85-112, 2010. doi:10.4086/toc.2010.v006a005.

23 Klaus F. Roth. On a problem of Heilbronn. *J. London Math. Soc.*, 26:198-204, 1951. doi:10.1112/jlms/s1-26.3.198.

24 Andrew Suk. On the Erdős-Szekeres convex polygon problem. *J. Amer. Math. Soc.*, 30:1047-1053, 2017. doi:10.1090/jams/869.

25 Terence Tao. The Erdos-Ulam problem, varieties of general type, and the Bombieri-Lang conjecture. In *What's new*. WordPress, December 20, 2014. URL: https://terrytao.wordpress.com/2014/12/20/.
# Dual Parameterization of Weighted Coloring

## Júlio Araújo

Departamento de Matemática, Universidade Federal do Ceará, Fortaleza, Brazil
julio@mat.ufc.br

https://orcid.org/0000-0001-7074-2753

## Victor A. Campos

Departamento de Computação, Universidade Federal do Ceará, Fortaleza, Brazil
campos@lia.ufc.br

## Carlos Vinícius G. C. Lima

Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil

carloslima@dcc.ufmg.br

https://orcid.org/0000-0002-6666-0533

## Vinícius Fernandes dos Santos

Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil

viniciussantos@dcc.ufmg.br

https://orcid.org/0000-0002-4608-4559

## Ignasi Sau

LIRMM, CNRS, Université de Montpellier, Montpellier, France

ignasi.sau@lirmm.fr

https://orcid.org/0000-0002-8981-9287

## Ana Silva

Departamento de Matemática, Universidade Federal do Ceará, Fortaleza, Brazil

anasilva@mat.ufc.br

https://orcid.org/0000-0001-8917-0564

## Abstract

Given a graph $G$, a proper $k$-coloring of $G$ is a partition $c = (S_i)_{i \in [1,k]}$ of $V(G)$ into $k$ stable sets $S_1, \dots, S_k$. Given a weight function $w : V(G) \to \mathbb{R}^+$, the weight of a color $S_i$ is defined as $w(i) = \max_{v \in S_i} w(v)$ and the weight of a coloring $c$ as $w(c) = \sum_{i=1}^k w(i)$. Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair $(G, w)$, denoted by $\sigma(G, w)$, as the minimum weight of a proper coloring of $G$. The problem of determining $\sigma(G, w)$ has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on $n$-vertex trees in time $n^{o(\log n)}$ unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree.

We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph $(G, w)$ and an integer $k$, is $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k$? This parameterization has been recently considered by Escoffier [WG, 2016], who provided an FPT algorithm running in time $2^{O(k \log k)} \cdot n^{O(1)}$, and asked which kernel size can be achieved for the problem.

We provide an FPT algorithm running in time $9^k \cdot n^{O(1)}$, and prove that no algorithm in time $2^{O(k)} \cdot n^{O(1)}$ exists under the ETH. On the other hand, we present a kernel with at most $(2^{k-1}+1)(k-1)$ vertices, and rule out the existence of polynomial kernels unless NP $\subseteq$ coNP/poly, even on split graphs with only two different weights. Finally, we identify some classes of graphs on which the problem admits a polynomial kernel, in particular interval graphs and subclasses of split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.

<figure><img src="image_68.png" /></figure>

© Júlio Araújo, Victor A. Campos, Carlos V. Lima, Vinícius F. dos Santos, Ignasi Sau, and Ana Silva; licensed under Creative Commons License CC-BY

13th International Symposium on Parameterized and Exact Computation (IPEC 2018).

Editors: Christophe Paul and Michał Pilipczuk; Article No. 12; pp. 12:1–12:14

<figure><img src="image_69.png" /></figure>

Leibniz International Proceedings in Informatics
LIPICS Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
# Dual Parameterization of Weighted Coloring

## Júlio Araújo

Departamento de Matemática, Universidade Federal do Ceará, Fortaleza, Brazil
julio@mat.ufc.br

https://orcid.org/0000-0001-7074-2753

## Victor A. Campos

Departamento de Computação, Universidade Federal do Ceará, Fortaleza, Brazil
campos@lia.ufc.br

## Carlos Vinícius G. C. Lima

Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil

carloslima@dcc.ufmg.br

https://orcid.org/0000-0002-6666-0533

## Vinícius Fernandes dos Santos

Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil

viniciussantos@dcc.ufmg.br

https://orcid.org/0000-0002-4608-4559

## Ignasi Sau

LIRMM, CNRS, Université de Montpellier, Montpellier, France

ignasi.sau@lirmm.fr

https://orcid.org/0000-0002-8981-9287

## Ana Silva

Departamento de Matemática, Universidade Federal do Ceará, Fortaleza, Brazil

anasilva@mat.ufc.br

https://orcid.org/0000-0001-8917-0564

## Abstract

Given a graph $G$, a proper $k$-coloring of $G$ is a partition $c = (S_i)_{i \in [1,k]}$ of $V(G)$ into $k$ stable sets $S_1, \dots, S_k$. Given a weight function $w : V(G) \to \mathbb{R}^+$, the weight of a color $S_i$ is defined as $w(i) = \max_{v \in S_i} w(v)$ and the weight of a coloring $c$ as $w(c) = \sum_{i=1}^k w(i)$. Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair $(G, w)$, denoted by $\sigma(G, w)$, as the minimum weight of a proper coloring of $G$. The problem of determining $\sigma(G, w)$ has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on $n$-vertex trees in time $n^{o(\log n)}$ unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree.

We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph $(G, w)$ and an integer $k$, is $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k$? This parameterization has been recently considered by Escoffier [WG, 2016], who provided an FPT algorithm running in time $2^{O(k \log k)} \cdot n^{O(1)}$, and asked which kernel size can be achieved for the problem.

We provide an FPT algorithm running in time $9^k \cdot n^{O(1)}$, and prove that no algorithm in time $2^{O(k)} \cdot n^{O(1)}$ exists under the ETH. On the other hand, we present a kernel with at most $(2^{k-1}+1)(k-1)$ vertices, and rule out the existence of polynomial kernels unless NP $\subseteq$ coNP/poly, even on split graphs with only two different weights. Finally, we identify some classes of graphs on which the problem admits a polynomial kernel, in particular interval graphs and subclasses of split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.

<figure><img src="image_71.png" /></figure>

© Júlio Araújo, Victor A. Campos, Carlos V. Lima, Vinícius F. dos Santos, Ignasi Sau, and Ana Silva; licensed under Creative Commons License CC-BY

13th International Symposium on Parameterized and Exact Computation (IPEC 2018).

Editors: Christophe Paul and Michał Pilipczuk; Article No. 12; pp. 12:1–12:14

<figure><img src="image_72.png" /></figure>

Leibniz International Proceedings in Informatics
LIPICS Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
12:2 Dual Parameterization of Weighted Coloring

**2012 ACM Subject Classification** Mathematics of computing → Graph algorithms, Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** weighted coloring, max coloring, parameterized complexity, dual parameterization, FPT algorithms, polynomial kernels, split graphs, interval graphs

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.12

**Related Version** A full version of this article is permanently available at https://arxiv.org/abs/1805.06699.

**Funding** Work supported by French projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010), and by Brazilian projects CNPq 306262/2014-2, CNPq 311013/2015-5, CNPq Universal 421660/2016-3, CNPq Universal 401519/2016-3, FAPEMIG, Funcap PNE-0112-00061.01.00/16, and Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001.

**Acknowledgements** We would like to thank the anonymous reviewers for carefully reading the article, in particular for spotting a flaw in the proof of Claim 5, which we rewrote completely in a simpler way. We also thank Mikko Koivisto for pointing us to reference [4].

1 Introduction

A (vertex) *k*-coloring of a graph *G* = (*V*,*E*) is a function *c* : *V*(*G*) → {1, ..., *k*}. Such coloring *c* is proper if *c*(*u*) ≠ *c*(*v*) for every edge {*u*,*v*} ∈ *E*(*G*). All the colorings we consider in this paper are proper, hence we may omit the word “proper”. The chromatic number χ(*G*) of *G* is the minimum integer *k* such that *G* admits a *k*-coloring. Given a graph *G*, determining χ(*G*) is the goal of the classical VERTEX COLORING problem. If *c* is a *k*-coloring of *G*, then *S*<sub>*i*</sub> = {*u* ∈ *V*(*G*) | *c*(*u*) = *i*} is a stable (or independent) set. With slight abuse of notation, we shall also call such a set *S*<sub>*i*</sub> a color.

In this paper we study a generalization of VERTEX COLORING for vertex-weighted graphs that has been defined by Guan and Zhu [24]. Given a graph *G* and a weight function *w*: *V*(*G*) → R<sup>+</sup>, the weight of a color *S*<sub>*i*</sub> is defined as *w*(*i*) = max<sub>*v*∈*S*<sub>*i*</sub></sub> *w*(*v*). Then, the weight of a coloring *c* is *w*(*c*) = Σ<sub>*i*=1 to *k*</sub> *w*(*i*). In the WEIGHTED COLORING problem, the goal is to determine the weighted chromatic number of a pair (*G*, *w*), denoted by σ(*G*, *w*), which is the minimum weight of a coloring of (*G*, *w*). A coloring *c* of *G* such that *w*(*c*) = σ(*G*, *w*) is an optimal weighted coloring. Guan and Zhu [24] also defined, for a positive integer *r*, σ(*G*, *w*; *r*) as the minimum of *w*(*c*) among all *r*-colorings *c* of *G*, or as +∞ if no *r*-coloring exists. Note that σ(*G*, *w*) = min<sub>*r*≥1</sub> σ(*G*, *w*; *r*). It is worth mentioning that the WEIGHTED COLORING problem is also sometimes called MAX-COLORING in the literature; see for instance [34, 37, 18]. Guan and Zhu defined this problem in order to study practical applications related to resource allocation, which they describe in detail in [24]. One should observe that if all the vertex weights are equal to one, then σ(*G*, *w*) = χ(*G*), for every graph *G*. Consequently, determining σ(*G*, *w*) is an NP-hard problem on general graphs [33]. In fact, this problem has been shown to be NP-hard even on very restricted graph classes, such as split graphs with only two different weights, interval graphs, triangle-free planar graphs with bounded degree, and bipartite graphs [12, 11, 19]. On the other hand, the weighted chromatic number of cographs and of some subclasses of bipartite graphs can be found in polynomial time [12, 11].
12:2 Dual Parameterization of Weighted Coloring

**2012 ACM Subject Classification** Mathematics of computing → Graph algorithms, Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** weighted coloring, max coloring, parameterized complexity, dual parameterization, FPT algorithms, polynomial kernels, split graphs, interval graphs

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.12

**Related Version** A full version of this article is permanently available at https://arxiv.org/abs/1805.06699.

**Funding** Work supported by French projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010), and by Brazilian projects CNPq 306262/2014-2, CNPq 311013/2015-5, CNPq Universal 421660/2016-3, CNPq Universal 401519/2016-3, FAPEMIG, Funcap PNE-0112-00061.01.00/16, and Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001.

**Acknowledgements** We would like to thank the anonymous reviewers for carefully reading the article, in particular for spotting a flaw in the proof of Claim 5, which we rewrote completely in a simpler way. We also thank Mikko Koivisto for pointing us to reference [4].

1 Introduction

A (*vertex*) *k*-coloring of a graph *G* = (*V*, *E*) is a function *c* : *V*(*G*) → {1, ..., *k*}. Such coloring *c* is proper if *c*(*u*) ≠ *c*(*v*) for every edge {*u*, *v*} ∈ *E*(*G*). All the colorings we consider in this paper are proper, hence we may omit the word “proper”. The *chromatic number* χ(*G*) of *G* is the minimum integer *k* such that *G* admits a *k*-coloring. Given a graph *G*, determining χ(*G*) is the goal of the classical VERTEX COLORING problem. If *c* is a *k*-coloring of *G*, then *S*<sub>*i*</sub> = {*u* ∈ *V*(*G*) | *c*(*u*) = *i*} is a stable (or independent) set. With slight abuse of notation, we shall also call such a set *S*<sub>*i*</sub> a *color*.

In this paper we study a generalization of VERTEX COLORING for vertex-weighted graphs that has been defined by Guan and Zhu [24]. Given a graph G and a weight function w : V(G) → R+, the weight of a color S_i is defined as w(i) = max_{v∈S_i} w(v). Then, the weight of a coloring c is w(c) = ∑k i=1 w(i). In the WEIGHTED COLORING problem, the goal is to determine the weighted chromatic number of a pair (G, w), denoted by σ(G, w), which is the minimum weight of a coloring of (G, w). A coloring c of G such that w(c) = σ(G, w) is an optimal weighted coloring. Guan and Zhu [24] also defined, for a positive integer r, σ(G, w; r) as the minimum of w(c) among all r-colorings c of G, or as +∞ if no r-coloring exists. Note that σ(G, w) = min_{r≥1} σ(G, w; r). It is worth mentioning that the WEIGHTED COLORING problem is also sometimes called MAX-COLORING in the literature; see for instance [34, 37, 18]. Guan and Zhu defined this problem in order to study practical applications related to resource allocation, which they describe in detail in [24]. One should observe that if all the vertex weights are equal to one, then σ(G, w) = χ(G), for every graph G. Consequently, determining σ(G, w) is an NP-hard problem on general graphs [33]. In fact, this problem has been shown to be NP-hard even on very restricted graph classes, such as split graphs with only two different weights, interval graphs, triangle-free planar graphs with bounded degree, and bipartite graphs [12, 11, 19]. On the other hand, the weighted chromatic number of cographs and of some subclasses of bipartite graphs can be found in polynomial time [12, 11].
The complexity of WEIGHTED COLORING on trees (and forests) has attracted considerable attention in the literature. Guan and Zhu [24] left as an open problem whether WEIGHTED COLORING is polynomial on trees and, more generally, on graphs of bounded treewidth. Escoffier et al. [19] found a polynomial-time approximation scheme to solve WEIGHTED COLORING on bounded treewidth graphs, and Kavitha and Mestre [34] showed that the problem is in P on the class of trees where vertices with degree at least three induce a stable set. But the question of Guan and Zhu has been answered only recently, when Araújo et al. [2] showed that, unless the Exponential Time Hypothesis (ETH)<fnref n="1" /> fails, there is no algorithm computing the weighted chromatic number of *n*-vertex trees in time $n^{o(\log n)}$. Moreover, as discussed in [2], this lower bound is tight. Very recently Araújo et al. [1] focused on the parameterized complexity of computing $\sigma(G, w)$ and $\sigma(G, w; r)$ when $G$ is a forest, and they proved that computing $\sigma(G, w)$ is W[1]-hard parameterized by the size of a largest tree of $G$, and that computing $\sigma(G, w; r)$ is W[2]-hard parameterized by $r$.

In view of the above discussion, we can conclude that WEIGHTED COLORING is a particularly hard problem from a computational point of view, and that the positive results in the literature are quite scarce. In this paper we adopt the perspective of parameterized complexity and consider the dual parameterization of the problem, which we call DUAL WEIGHTED COLORING and is formally defined as follows:

**DUAL WEIGHTED COLORING**

**Input:** A vertex-weighted graph $(G, w)$ and a positive integer $k$.

**Parameter:** $k$.

**Question:** Is $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k$?

Since by definition of parameterized problem (cf. [16, 10]) the parameter needs to be a non-negative integer, for the above parameterization to make sense we will assume henceforth that all vertex-weights are positive integers. We will denote by *n* the number of vertices of the input graph of DUAL WEIGHTED COLORING.

The motivation for considering such parameterization is to take as the parameter the “savings” with respect to the trivial upper bound of $\sum_{v \in V(G)} w(v)$ on $\sigma(G, w)$. This approach has proved to be very useful for the classical VERTEX COLORING problem, especially from the approximation point of view [13, 28, 26, 27, 17, 18]. From a parameterized perspective, Chor et al. [9] presented an FPT algorithm for DUAL VERTEX COLORING. Concerning kernelization, it is not difficult to see [10, Exercise 2.22] that the problem admits a kernel with at most $3k$ vertices, by applying the so-called *crown reduction rule* to the complement of the input graph $G$. Other results concerning dual parameterization are, for instance, FPT algorithms for the Grundy and *b*-chromatic numbers of a graph [29], the parameterized approximability of subset graph problems [8], or the existence of polynomial kernels for the SET COVER and HITTING SET problems [25, 3].

The dual parameterization of the WEIGHTED COLORING problem, under the equivalent name of MAX COLORING, has been recently considered by Escoffier [18], who provided an FPT algorithm running in time $2^{O(k \log k)} \cdot n^{O(1)}$, and asked which is the smallest kernel size that can be achieved for the problem.

**Our results.** Improving over Escoffier's algorithm [18], our first result is an FPT algorithm for DUAL WEIGHTED COLORING running in time $9^k \cdot n^{O(1)}$, based on some standard dynamic programming ideas used in coloring and partition problems (see, for example, [35] and [20,

<footnote n="1">¹ The ETH states that 3-SAT cannot be solved in subexponential time; see [32, 31] for more details.</footnote>
The complexity of WEIGHTED COLORING on trees (and forests) has attracted considerable attention in the literature. Guan and Zhu [24] left as an open problem whether WEIGHTED COLORING is polynomial on trees and, more generally, on graphs of bounded treewidth. Escoffier et al. [19] found a polynomial-time approximation scheme to solve WEIGHTED COLORING on bounded treewidth graphs, and Kavitha and Mestre [34] showed that the problem is in P on the class of trees where vertices with degree at least three induce a stable set. But the question of Guan and Zhu has been answered only recently, when Araújo et al. [2] showed that, unless the Exponential Time Hypothesis (ETH)<fnref n="1" /> fails, there is no algorithm computing the weighted chromatic number of *n*-vertex trees in time $n^{o(\log n)}$. Moreover, as discussed in [2], this lower bound is tight. Very recently Araújo et al. [1] focused on the parameterized complexity of computing $\sigma(G, w)$ and $\sigma(G, w; r)$ when $G$ is a forest, and they proved that computing $\sigma(G, w)$ is W[1]-hard parameterized by the size of a largest tree of $G$, and that computing $\sigma(G, w; r)$ is W[2]-hard parameterized by $r$.

In view of the above discussion, we can conclude that WEIGHTED COLORING is a particularly hard problem from a computational point of view, and that the positive results in the literature are quite scarce. In this paper we adopt the perspective of parameterized complexity and consider the dual parameterization of the problem, which we call DUAL WEIGHTED COLORING and is formally defined as follows:

**DUAL WEIGHTED COLORING**

**Input:** A vertex-weighted graph $(G, w)$ and a positive integer $k$.

**Parameter:** $k$.

**Question:** Is $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k$?

Since by definition of parameterized problem (cf. [16, 10]) the parameter needs to be a non-negative integer, for the above parameterization to make sense we will assume henceforth that all vertex-weights are positive integers. We will denote by $n$ the number of vertices of the input graph of DUAL WEIGHTED COLORING.

The motivation for considering such parameterization is to take as the parameter the “savings” with respect to the trivial upper bound of $\sum_{v \in V(G)} w(v)$ on $\sigma(G, w)$. This approach has proved to be very useful for the classical VERTEX COLORING problem, especially from the approximation point of view [12, 25, 26, 27, 18]. From a parameterized perspective, Chor et al. [9] presented an FPT algorithm for DUAL VERTEX COLORING. Concerning kernelization, it is not difficult to see [10, Exercise 2.22] that the problem admits a kernel with at most $3k$ vertices, by applying the so-called *crown reduction rule* to the complement of the input graph $G$. Other results concerning dual parameterization are, for instance, FPT algorithms for the Grundy and *b*-chromatic numbers of a graph [29], the parameterized approximability of subset graph problems [8], or the existence of polynomial kernels for the SET COVER and HITTING SET problems [25, 3].

The dual parameterization of the WEIGHTED COLORING problem, under the equivalent name of MAX COLORING, has been recently considered by Escoffier [18], who provided an FPT algorithm running in time $2^{O(k \log k)} \cdot n^{O(1)}$, and asked which is the smallest kernel size that can be achieved for the problem.

**Our results.** Improving over Escoffier's algorithm [18], our first result is an FPT algorithm for DUAL WEIGHTED COLORING running in time $9^k \cdot n^{O(1)}$, based on some standard dynamic programming ideas used in coloring and partition problems (see, for example, [35] and [20,

<footnote n="1">¹ The ETH states that 3-SAT cannot be solved in subexponential time; see [32, 31] for more details.</footnote>
12:4 Dual Parameterization of Weighted Coloring

Section 3.1.2]). It is easy to see that a subexponential algorithm is unlikely to exist. Indeed, consider the 3-COLORING problem, which corresponds to the unweighted version of DUAL WEIGHTED COLORING with parameter $k = n - 3$. Since 3-COLORING cannot be solved in time $2^{o(n)}$ under the ETH [36], the existence of an algorithm for DUAL WEIGHTED COLORING running in time $2^{o(k)} \cdot n^{O(1)}$ would imply, in particular, an algorithm for 3-COLORING running in time $2^{o(k)} \cdot n^{O(1)} = 2^{o(n)}$, contradicting the ETH.

Our main contribution concerns the existence of (polynomial) kernels for DUAL WEIGHTED COLORING. By the well-known equivalence of admitting an FPT algorithm and a kernel (cf. [16, 10]), the FPT algorithm mentioned above directly yields a kernel for DUAL WEIGHTED COLORING of size at most $9^k$. On the one hand, we considerably improve this bound by providing a kernel with at most $(2^{k-1}+1)(k-1)$ vertices, inspired by an approach attributed to Jan Arne Telle [16, Exercise 4.12.12] for obtaining a quadratic kernel for DUAL VERTEX COLORING. On the other hand, we complement this result by showing that, unlike the DUAL VERTEX COLORING problem, DUAL WEIGHTED COLORING does *not* admit a polynomial kernel unless $NP \subseteq coNP/poly$, even on split graphs with only two different weights. We prove this result by a polynomial parameter transformation from the SET COVER problem parameterized by the size of the universe, proved not to admit polynomial kernels unless $NP \subseteq coNP/poly$ by Dom et al. [15]. Our reduction is an appropriate modification of a reduction of Demange et al. [12] to prove the NP-hardness of WEIGHTED COLORING on split graphs. Altogether, these results answer Escoffier's question [18] about the smallest kernel size for the problem.

Motivated by the above hardness result, it is natural to identify graph classes on which the DUAL WEIGHTED COLORING problem admits polynomial kernels. We prove that this is the case of graph classes with bounded clique number and of interval graphs, for which we present a linear and a cubic kernel, respectively. Finally, we identify subclasses of split graphs admitting polynomial kernels. Namely, we prove that DUAL WEIGHTED COLORING restricted to split graphs where each vertex in the clique has at most $d$ non-neighbors in the stable set, for some constant $d \ge 1$, admits a kernel with at most $k^{d+1}$ vertices. We show that the dependency on $d$ in the exponent is necessary, by proving that for any $d \ge 2$ and $\varepsilon > 0$, a kernel with $O(k^{\frac{d-3}{2}-\varepsilon})$ vertices on that graph class does not exist unless $NP \subseteq coNP/poly$. In other words, we rule out the existence of a *uniform* kernel, that is, a kernel of size $f(d) \cdot k^{O(1)}$ for any function $f$.

**Organization of the paper.** In Section 2 we present some basic preliminaries about graphs and parameterized complexity. In Section 3 we present the FPT algorithm and in Section 4 we provide the kernelization results. Finally, we conclude the article in Section 5.

2 Preliminaries

**Graphs.** We use standard graph-theoretic notation, and we consider simple undirected graphs without loops or multiple edges; see [14] for any undefined terminology. Given a graph $G = (V, E)$, $X \subseteq V$, and $v \in V$, we denote $N_X(v) = N(v) \cap X$, where $N(v) = \{u \in V \mid \{u, v\} \in E\}$, and $\overline{N_X}(v) = X \setminus \{N_X(v) \cup \{v\}\}$. An *antimatching* in a graph $G$ is a matching in the complement of $G$. Two vertices $u, v \in V(G)$ are *twins* if $N(u) = N(v)$. A vertex $v \in V(G)$ is *universal* if $N(v) = V(G) \setminus \{v\}$. A graph $G$ is a *split graph* if $V(G)$ can be partitioned into an independent set and a clique, and an *interval graph* if one can associate a real interval with each vertex, so that two vertices are adjacent if and only if the corresponding intervals intersect.
12:4 Dual Parameterization of Weighted Coloring

Section 3.1.2]). It is easy to see that a subexponential algorithm is unlikely to exist. Indeed, consider the 3-COLORING problem, which corresponds to the unweighted version of DUAL WEIGHTED COLORING with parameter $k = n - 3$. Since 3-COLORING cannot be solved in time $2^{o(n)}$ under the ETH [36], the existence of an algorithm for DUAL WEIGHTED COLORING running in time $2^{o(k)} \cdot n^{O(1)}$ would imply, in particular, an algorithm for 3-COLORING running in time $2^{o(k)} \cdot n^{O(1)} = 2^{o(n)}$, contradicting the ETH.

Our main contribution concerns the existence of (polynomial) kernels for DUAL WEIGHTED COLORING. By the well-known equivalence of admitting an FPT algorithm and a kernel (cf. [16, 10]), the FPT algorithm mentioned above directly yields a kernel for DUAL WEIGHTED COLORING of size at most $9^k$. On the one hand, we considerably improve this bound by providing a kernel with at most $(2^{k-1}+1)(k-1)$ vertices, inspired by an approach attributed to Jan Arne Telle [16, Exercise 4.12.12] for obtaining a quadratic kernel for DUAL VERTEX COLORING. On the other hand, we complement this result by showing that, unlike the DUAL VERTEX COLORING problem, DUAL WEIGHTED COLORING does not admit a polynomial kernel unless $NP \subseteq coNP/poly$, even on split graphs with only two different weights. We prove this result by a polynomial parameter transformation from the SET COVER problem parameterized by the size of the universe, proved not to admit polynomial kernels unless $NP \subseteq coNP/poly$ by Dom et al. [15]. Our reduction is an appropriate modification of a reduction of Demange et al. [12] to prove the NP-hardness of WEIGHTED COLORING on split graphs. Altogether, these results answer Escoffier's question [18] about the smallest kernel size for the problem.

Motivated by the above hardness result, it is natural to identify graph classes on which the DUAL WEIGHTED COLORING problem admits polynomial kernels. We prove that this is the case of graph classes with bounded clique number and of interval graphs, for which we present a linear and a cubic kernel, respectively. Finally, we identify subclasses of split graphs admitting polynomial kernels. Namely, we prove that DUAL WEIGHTED COLORING restricted to split graphs where each vertex in the clique has at most $d$ non-neighbors in the stable set, for some constant $d \ge 1$, admits a kernel with at most $k^{d+1}$ vertices. We show that the dependency on $d$ in the exponent is necessary, by proving that for any $d \ge 2$ and $\varepsilon > 0$, a kernel with $O(k^{\frac{d-3}{2}-\varepsilon})$ vertices on that graph class does not exist unless $NP \subseteq coNP/poly$. In other words, we rule out the existence of a *uniform* kernel, that is, a kernel of size $f(d) \cdot k^{O(1)}$ for any function $f$.

**Organization of the paper.** In Section 2 we present some basic preliminaries about graphs and parameterized complexity. In Section 3 we present the FPT algorithm and in Section 4 we provide the kernelization results. Finally, we conclude the article in Section 5.

2 Preliminaries

**Graphs.** We use standard graph-theoretic notation, and we consider simple undirected graphs without loops or multiple edges; see [14] for any undefined terminology. Given a graph $G = (V, E)$, $X \subseteq V$, and $v \in V$, we denote $N_X(v) = N(v) \cap X$, where $N(v) = \{u \in V \mid \{u, v\} \in E\}$, and $\overline{N_X}(v) = X \setminus \{N_X(v) \cup \{v\}\}$. An *antimatching* in a graph $G$ is a matching in the complement of $G$. Two vertices $u, v \in V(G)$ are *twins* if $N(u) = N(v)$. A vertex $v \in V(G)$ is *universal* if $N(v) = V(G) \setminus \{v\}$. A graph $G$ is a *split graph* if $V(G)$ can be partitioned into an independent set and a clique, and an *interval graph* if one can associate a real interval with each vertex, so that two vertices are adjacent if and only if the corresponding intervals intersect.
**Parameterized complexity.** We refer the reader to [16, 10] for basic background on parameterized complexity, and we recall here only some basic definitions, with special emphasis on tools for polynomial kernelization. A *parameterized problem* is a language $L \subseteq \Sigma^* \times \mathbb{N}$. For an instance $I = (x, k) \in \Sigma^* \times \mathbb{N}$, $k$ is called the *parameter*. A parameterized problem is *fixed-parameter tractable* (FPT) if there exists an algorithm $\mathcal{A}$, a computable function $f$, and a constant $c$ such that given an instance $I = (x, k)$, $\mathcal{A}$ (called an FPT *algorithm*) correctly decides whether $I \in L$ in time bounded by $f(k) \cdot |I|^c$.

A fundamental concept in parameterized complexity is that of *kernelization*. A kernelization algorithm, or just *kernel*, for a parameterized problem $\Pi$ takes an instance $(x, k)$ of the problem and, in time polynomial in $|x| + k$, outputs an instance $(x', k')$ such that $|x'|, k' \le g(k)$ for some function $g$, and $(x, k) \in \Pi$ if and only if $(x', k') \in \Pi$. The function $g$ is called the *size* of the kernel and may be viewed as a measure of the “compressibility” of a problem using polynomial-time preprocessing rules. A kernel is called *polynomial* (resp. *linear*) if the function $g(k)$ is a polynomial (resp. linear) function in $k$. A breakthrough result of Bodlaender et al. [5] gave the first framework for proving that certain parameterized problems do not admit polynomial kernels, by establishing so-called *composition algorithms*. Together with a result of Fortnow and Santhanam [21] this allows to exclude polynomial kernels under the assumption that $\mathrm{NP} \not\subseteq \mathrm{coNP/poly}$, otherwise implying a collapse of the polynomial hierarchy to its third level [38]. Very successful notions for proving such type of result are those of *cross-composition*, introduced by Bodlaender et al. [6], and of *polynomial parameter transformation*, introduced by Bodlaender et al. [7]. We need to define the latter. A polynomial parameter transformation from a parameterized problem $P$ to a parameterized problem $Q$ is an algorithm that, given an instance $(x, k)$ of $P$, computes in polynomial time an equivalent instance $(x', k')$ of $Q$ such that $k'$ is bounded by a polynomial depending only on $k$.

Within parameterized problems, the class $W[1]$ may be seen as the parameterized equivalent to the class $\mathrm{NP}$ of classical optimization problems. Without entering into details (see [16, 10] for the formal definitions), a parameterized problem being $W[1]$-hard can be seen as a strong evidence that this problem is not FPT. The class $W[2]$ of parameterized problems is a class that contains $W[1]$, and such that the problems that are $W[2]$-hard are even more unlikely to be FPT than those that are $W[1]$-hard (again, see [16, 10] for the formal definitions).

## 3 FPT algorithm

In this section we present an FPT algorithm for the DUAL WEIGHTED COLORING problem.

► **Theorem 1.** The DUAL WEIGHTED COLORING problem can be solved in time $9^k \cdot n^{O(1)}$.

*Proof.* We start by computing a maximum unweighted antimatching $\bar{M}$ in $G$ (this idea has been already used, in particular, in [12]); note that this can be done in polynomial time by computing a maximum matching in the complement of $G$. If $|\bar{M}| \ge k$, since we assume that all the vertex weights are at least 1, by putting in the same color class each pair of vertices that belong to a non-edge of $\bar{M}$ and coloring any other vertex with a new color, we obtain a coloring of $G$ with weight at most $\sum_{v \in V(G)} w(v) - k$, and we can output a constant-sized yes-instance. Thus, we assume henceforth that $|\bar{M}| \le k - 1$.

Let $V(\bar{M}) \subseteq V(G)$ be the set of vertices that appear in the non-edges in $\bar{M}$. Since $\bar{M}$ is maximum, the set of vertices $K := V(G) \setminus V(\bar{M})$ induces a clique in $G$. Note that, in any coloring $c$ of $G$, at least $|K|$ colors will be needed. Let $K = \{v_1, \dots, v_{|K|}\}$ and let $c(v_i) = c_i$.
**Parameterized complexity.** We refer the reader to [16, 10] for basic background on parameterized complexity, and we recall here only some basic definitions, with special emphasis on tools for polynomial kernelization. A *parameterized problem* is a language $L \subseteq \Sigma^* \times \mathbb{N}$. For an instance $I = (x, k) \in \Sigma^* \times \mathbb{N}$, $k$ is called the *parameter*. A parameterized problem is *fixed-parameter tractable* (FPT) if there exists an algorithm $\mathcal{A}$, a computable function $f$, and a constant $c$ such that given an instance $I = (x, k)$, $\mathcal{A}$ (called an FPT *algorithm*) correctly decides whether $I \in L$ in time bounded by $f(k) \cdot |I|^c$.

A fundamental concept in parameterized complexity is that of *kernelization*. A kernelization algorithm, or just *kernel*, for a parameterized problem $\Pi$ takes an instance $(x, k)$ of the problem and, in time polynomial in $|x| + k$, outputs an instance $(x', k')$ such that $|x'|, k' \le g(k)$ for some function $g$, and $(x, k) \in \Pi$ if and only if $(x', k') \in \Pi$. The function $g$ is called the *size* of the kernel and may be viewed as a measure of the “compressibility” of a problem using polynomial-time preprocessing rules. A kernel is called *polynomial* (resp. *linear*) if the function $g(k)$ is a polynomial (resp. linear) function in $k$. A breakthrough result of Bodlaender et al. [5] gave the first framework for proving that certain parameterized problems do not admit polynomial kernels, by establishing so-called *composition algorithms*. Together with a result of Fortnow and Santhanam [21] this allows to exclude polynomial kernels under the assumption that $\mathrm{NP} \not\subseteq \mathrm{coNP/poly}$, otherwise implying a collapse of the polynomial hierarchy to its third level [38]. Very successful notions for proving such type of result are those of *cross-composition*, introduced by Bodlaender et al. [6], and of *polynomial parameter transformation*, introduced by Bodlaender et al. [7]. We need to define the latter. A polynomial parameter transformation from a parameterized problem $P$ to a parameterized problem $Q$ is an algorithm that, given an instance $(x, k)$ of $P$, computes in polynomial time an equivalent instance $(x', k')$ of $Q$ such that $k'$ is bounded by a polynomial depending only on $k$.

Within parameterized problems, the class $W[1]$ may be seen as the parameterized equivalent to the class $\mathrm{NP}$ of classical optimization problems. Without entering into details (see [16, 10] for the formal definitions), a parameterized problem being $W[1]$-hard can be seen as a strong evidence that this problem is not FPT. The class $W[2]$ of parameterized problems is a class that contains $W[1]$, and such that the problems that are $W[2]$-hard are even more unlikely to be FPT than those that are $W[1]$-hard (again, see [16, 10] for the formal definitions).

## 3 FPT algorithm

In this section we present an FPT algorithm for the DUAL WEIGHTED COLORING problem.

► **Theorem 1.** The DUAL WEIGHTED COLORING problem can be solved in time $9^k \cdot n^{O(1)}$.

*Proof.* We start by computing a maximum unweighted antimatching $\bar{M}$ in $G$ (this idea has been already used, in particular, in [12]); note that this can be done in polynomial time by computing a maximum matching in the complement of $G$. If $|\bar{M}| \ge k$, since we assume that all the vertex weights are at least 1, by putting in the same color class each pair of vertices that belong to a non-edge of $\bar{M}$ and coloring any other vertex with a new color, we obtain a coloring of $G$ with weight at most $\sum_{v \in V(G)} w(v) - k$, and we can output a constant-sized yes-instance. Thus, we assume henceforth that $|\bar{M}| \le k - 1$.

Let $V(\bar{M}) \subseteq V(G)$ be the set of vertices that appear in the non-edges in $\bar{M}$. Since $\bar{M}$ is maximum, the set of vertices $K := V(G) \setminus V(\bar{M})$ induces a clique in $G$. Note that, in any coloring $c$ of $G$, at least $|K|$ colors will be needed. Let $K = \{v_1, \dots, v_{|K|}\}$ and let $c(v_i) = c_i$.
12:6 Dual Parameterization of Weighted Coloring

Hence, it remains just to color the vertices in $V(\bar{M})$, which may be colored with some colors previously used in $K$ or with new ones.

Let $X \subseteq V(\bar{M})$ and $0 \le i \le |K|$. We define $T(X, i)$ as the minimum weight of a coloring of $G[K \cup X]$ such that no color $c_j$, for $j > i$, is assigned to a vertex of $X$, i.e., the colors assigned to vertices in $X$ are either from the set $\{c_1, \dots, c_i\}$ or new colors not assigned to any vertex of $K$. Note that, by definition, $\sigma(G, w) = T(V(\bar{M}), |K|)$.

We now describe how to compute $T(X, i)$ for every $X \subseteq V(\bar{M})$ and every $0 \le i \le |K|$.
If $X = \emptyset$, then, for any $i$,

$$T(\emptyset, i) = \sum_{v \in K} w(v),$$

since $K$ is a clique. This can be done in linear time.

If $i = 0$, then the colors used in $K$ and in $X$ are disjoint. By applying brute force over all possible stable sets of $X$ we get

$$T(X, 0) = \min_{\substack{\emptyset \neq S \subseteq X \\ S \text{ stable}}} T(X \setminus S, 0) + w(S),$$

where $w(S) = \max_{v \in S} w(v)$. The values $T(X, 0)$, for all possible sets $X \subseteq V(\bar{M})$, can be computed in time

$$\left( \sum_{j=0}^{|V(\bar{M})|} \binom{|V(\bar{M})|}{j} \cdot 2^j \right) \cdot n^{\mathcal{O}(1)} = 3^{|V(\bar{M})|} \cdot n^{\mathcal{O}(1)},$$

corresponding to considering the sets $X$ by increasing size and choosing an arbitrary subset $S$ inside $X$, and where the polynomial factor comes from checking whether such a set $S$ is stable or not.

Now, if $i > 0$ and $X \neq \emptyset$, we have two possibilities, namely either color $c_i$ is used in $V(\bar{M})$ or not. If $c_i$ is not used, clearly we have $T(X, i) = T(X, i-1)$. Otherwise, there is a non-empty set $S \subseteq X$ of vertices colored with color $c_i$. Therefore, taking into account both cases, we can iterate over every possible set $S \subseteq X$ and compute $T(X, i)$ as follows:

$$T(X, i) = \min_{\substack{S \subseteq X \\ S \cup \{v_i\} \text{ stable}}} T(X \setminus S, i-1) + w(S \cup \{v_i\}) - w(v_i).$$

Here we have to subtract the weight of $v_i$, which was, in the partial solution $T(X \setminus S, i-1)$, the weight of color $c_i$, and replace it by $w(S \cup \{v_i\})$, which may be larger. As in the previous case, for every $i$ it is possible to compute $T(X, i)$ for every $X$ in time $3^{|V(\bar{M})|} \cdot n^{\mathcal{O}(1)}$.

Hence, since $|V(\bar{M})| \le 2k-2$, in time bounded by $3^{2k} \cdot n^{\mathcal{O}(1)} = 9^k \cdot n^{\mathcal{O}(1)}$ we can compute $T(V(\bar{M}), |K|) = \sigma(G, w)$ and answer whether $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k$ or not. $\blacksquare$

4 Kernelization results

In this section we focus on the existence of (polynomial) kernels for DUAL WEIGHTED COLORING.

► **Theorem 2.** The DUAL WEIGHTED COLORING problem admits a kernel with at most $(2^{k-1} + 1) \cdot (k-1)$ vertices.

**Proof.** We start with the following trivial polynomial-time reduction rule.
12:6 Dual Parameterization of Weighted Coloring

Hence, it remains just to color the vertices in $V(\bar{M})$, which may be colored with some colors previously used in $K$ or with new ones.

Let $X \subseteq V(\bar{M})$ and $0 \le i \le |K|$. We define $T(X, i)$ as the minimum weight of a coloring of $G[K \cup X]$ such that no color $c_j$, for $j > i$, is assigned to a vertex of $X$, i.e., the colors assigned to vertices in $X$ are either from the set $\{c_1, \dots, c_i\}$ or new colors not assigned to any vertex of $K$. Note that, by definition, $\sigma(G, w) = T(V(\bar{M}), |K|)$.

We now describe how to compute $T(X, i)$ for every $X \subseteq V(\bar{M})$ and every $0 \le i \le |K|$.
If $X = \emptyset$, then, for any $i$,

$$T(\emptyset, i) = \sum_{v \in K} w(v),$$

since $K$ is a clique. This can be done in linear time.

If $i = 0$, then the colors used in $K$ and in $X$ are disjoint. By applying brute force over all possible stable sets of $X$ we get

$$T(X, 0) = \min_{\substack{\emptyset \neq S \subseteq X \\ S \text{ stable}}} T(X \setminus S, 0) + w(S),$$

where $w(S) = \max_{v \in S} w(v)$. The values $T(X, 0)$, for all possible sets $X \subseteq V(\bar{M})$, can be computed in time

$$\left( \sum_{j=0}^{|V(\bar{M})|} \binom{|V(\bar{M})|}{j} \cdot 2^j \right) \cdot n^{\mathcal{O}(1)} = 3^{|V(\bar{M})|} \cdot n^{\mathcal{O}(1)},$$

corresponding to considering the sets $X$ by increasing size and choosing an arbitrary subset $S$ inside $X$, and where the polynomial factor comes from checking whether such a set $S$ is stable or not.

Now, if $i > 0$ and $X \neq \emptyset$, we have two possibilities, namely either color $c_i$ is used in $V(\bar{M})$ or not. If $c_i$ is not used, clearly we have $T(X, i) = T(X, i-1)$. Otherwise, there is a non-empty set $S \subseteq X$ of vertices colored with color $c_i$. Therefore, taking into account both cases, we can iterate over every possible set $S \subseteq X$ and compute $T(X, i)$ as follows:

$$T(X, i) = \min_{\substack{S \subseteq X \\ S \cup \{v_i\} \text{ stable}}} T(X \setminus S, i-1) + w(S \cup \{v_i\}) - w(v_i).$$

Here we have to subtract the weight of $v_i$, which was, in the partial solution $T(X \setminus S, i-1)$, the weight of color $c_i$, and replace it by $w(S \cup \{v_i\})$, which may be larger. As in the previous case, for every $i$ it is possible to compute $T(X, i)$ for every $X$ in time $3^{|V(\bar{M})|} \cdot n^{\mathcal{O}(1)}$.

Hence, since $|V(\bar{M})| \le 2k-2$, in time bounded by $3^{2k} \cdot n^{\mathcal{O}(1)} = 9^k \cdot n^{\mathcal{O}(1)}$ we can compute $T(V(\bar{M}), |K|) = \sigma(G, w)$ and answer whether $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k$ or not. $\blacksquare$

4 Kernelization results

In this section we focus on the existence of (polynomial) kernels for DUAL WEIGHTED COLORING.

► **Theorem 2.** The DUAL WEIGHTED COLORING problem admits a kernel with at most $(2^{k-1} + 1) \cdot (k-1)$ vertices.

**Proof.** We start with the following trivial polynomial-time reduction rule.
**Rule 1.** If $G$ contains a universal vertex, delete it.

**► Claim 1. Rule 1 is safe.**

**Proof.** Since a universal vertex $u$ appears as a singleton in any proper coloring of $G$, it follows that $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k$ if and only if $\sigma(G - \{u\}, w) \le \sum_{v \in V(G) \setminus \{u\}} w(v) - k$. ◀

As in the proof of Theorem 1, we compute in polynomial time a maximum unweighted antimatching $\bar{M}$ in $G$. Again, if $|\bar{M}| \ge k$, we can correctly answer that we have a yes-instance, so we assume henceforth that $|\bar{M}| \le k - 1$. Let again $V(\bar{M}) \subseteq V(G)$ be the set of vertices that appear in the non-edges in $\bar{M}$, and recall that since $\bar{M}$ is maximum, the set of vertices $K = V(G) \setminus V(\bar{M})$ induces a clique in $G$.

We now partition $K$ into a set of equivalence classes $\mathcal{C}$ according to the neighborhood in $V(\bar{M})$. That is, $u, v \in K$ belong to the same class in $\mathcal{C}$ if and only if $N_{V(\bar{M})}(u) = N_{V(\bar{M})}(v)$. Note that $\mathcal{C}$ can be constructed in polynomial time, by iteratively processing the vertices of $K$, comparing the neighborhood in $V(\bar{M})$ of the currently processed vertex $v$ with those of the already processed vertices, and creating a new class containing only $v$ if no class has exactly the set $N_{V(\bar{M})}(v)$ as neighbors in $V(\bar{M})$. Given an equivalence class $C \in \mathcal{C}$ and a non-edge $\bar{e} \in \bar{M}$, we denote by $N_{\bar{e}}(C)$ the set of neighbors of any vertex in $C$ in the set consisting of the two endpoints of $\bar{e}$. We proceed to analyze the number and the size of the classes in $\mathcal{C}$. We start with an easy claim.

**► Claim 2.** Let $C \in \mathcal{C}$ be an equivalence class with $|C| \ge 2$. For every non-edge $\bar{e} \in \bar{M}$ it holds that $|N_{\bar{e}}(C)| \ge 1$.

**Proof.** Suppose for contradiction that $|N_{\bar{e}}(C)| = 0$, let $x, y$ be the endvertices of $\bar{e}$, and let $u, v$ be any two vertices in $C$. Then we can obtain from $\bar{M}$ a larger antimatching $\bar{M}'$ by replacing the non-edge $\{x, y\}$ with the two non-edges $\{u, x\}$ and $\{v, y\}$, a contradiction. ◀

In the next claim we restrict further the neighborhoods of the equivalence classes in $V(\bar{C})$.

**► Claim 3.** Let $C_1, C_2 \in \mathcal{C}$ be two equivalence classes and let $\bar{e} \in \bar{M}$ be a non-edge with endpoints $x$ and $y$. Then it is not possible that $x \notin N_{\bar{e}}(C_1)$ and $y \notin N_{\bar{e}}(C_2)$, or vice versa.

**Proof.** Suppose for contradiction that $x \notin N_{\bar{e}}(C_1)$ and $y \notin N_{\bar{e}}(C_2)$, and let $u \in C_1$ and $v \in C_2$. Then we can obtain from $\bar{M}$ a larger antimatching $\bar{M}'$ by replacing the non-edge $\{x, y\}$ with the two non-edges $\{u, x\}$ and $\{v, y\}$, a contradiction. ◀

We call an equivalence class $C \in \mathcal{C}$ special if for some non-edge $\bar{e} \in \bar{M}$, $|N_{\bar{e}}(C)| = 0$, and we call such an $\bar{e}$ a special non-edge; otherwise we call an equivalence class normal. We call a non-edge $\bar{e} \in \bar{M}$ normal if for every $C \in \mathcal{C}$, $|N_{\bar{e}}(C)| \ge 1$. Let $k_s$ and $k_n$ be the number of special and normal non-edges in $\bar{M}$, respectively, and note that $k_s + k_n = |\bar{M}| \le k - 1$.

By Claim 2, every special class contains exactly one vertex. If $\bar{e} \in \bar{M}$ is a special non-edge and $C \in \mathcal{C}$ is such that $|N_{\bar{e}}(C)| = 0$, then Claim 3 implies that for every other class $C' \in \mathcal{C}$ different from $C$, it holds that $|N_{\bar{e}}(C')| = 2$. Therefore, the number of special classes in $C$ is at most the number of special non-edges in $\bar{M}$, that is, at most $k_s$.

Let $\bar{e} \in \bar{M}$ be a normal non-edge with endpoints $x, y$, let $C \in \mathcal{C}$ be such that $|N_{\bar{e}}(C)| = 1$, and assume that $N_{\bar{e}}(C) = \{x\}$. Then Claim 3 implies that for every class $C' \in \mathcal{C}$ such that $|N_{\bar{e}}(C')| = 1$, it holds that $N_{\bar{e}}(C') = \{x\}$. Hence, every normal non-edge $\bar{e} \in \bar{M}$ has at most one endpoint that has some non-neighbor in $K$; we call such a vertex the *avoidable* vertex of $\bar{e}$. This means that for every normal class $C \in \mathcal{C}$ and every non-edge $\bar{e} \in \bar{M}$, there are exactly two possibilities: either $|N_{\bar{e}}(C)| = 2$, or $|N_{\bar{e}}(C)| = 1$ and $N_{\bar{e}}(C)$ consists of the
**Rule 1.** If $G$ contains a universal vertex, delete it.

**► Claim 1. Rule 1 is safe.**

**Proof.** Since a universal vertex $u$ appears as a singleton in any proper coloring of $G$, it follows that $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k$ if and only if $\sigma(G - \{u\}, w) \le \sum_{v \in V(G) \setminus \{u\}} w(v) - k$. ◀

As in the proof of Theorem 1, we compute in polynomial time a maximum unweighted antimatching $\bar{M}$ in $G$. Again, if $|\bar{M}| \ge k$, we can correctly answer that we have a yes-instance, so we assume henceforth that $|\bar{M}| \le k - 1$. Let again $V(\bar{M}) \subseteq V(G)$ be the set of vertices that appear in the non-edges in $\bar{M}$, and recall that since $\bar{M}$ is maximum, the set of vertices $K = V(G) \setminus V(\bar{M})$ induces a clique in $G$.

We now partition $K$ into a set of equivalence classes $\mathcal{C}$ according to the neighborhood in $V(\bar{M})$. That is, $u, v \in K$ belong to the same class in $\mathcal{C}$ if and only if $N_{V(\bar{M})}(u) = N_{V(\bar{M})}(v)$. Note that $\mathcal{C}$ can be constructed in polynomial time, by iteratively processing the vertices of $K$, comparing the neighborhood in $V(\bar{M})$ of the currently processed vertex $v$ with those of the already processed vertices, and creating a new class containing only $v$ if no class has exactly the set $N_{V(\bar{M})}(v)$ as neighbors in $V(\bar{M})$. Given an equivalence class $C \in \mathcal{C}$ and a non-edge $\bar{e} \in \bar{M}$, we denote by $N_{\bar{e}}(C)$ the set of neighbors of any vertex in $C$ in the set consisting of the two endpoints of $\bar{e}$. We proceed to analyze the number and the size of the classes in $\mathcal{C}$. We start with an easy claim.

**► Claim 2.** Let $C \in \mathcal{C}$ be an equivalence class with $|C| \ge 2$. For every non-edge $\bar{e} \in \bar{M}$ it holds that $|N_{\bar{e}}(C)| \ge 1$.

**Proof.** Suppose for contradiction that $|N_{\bar{e}}(C)| = 0$, let $x, y$ be the endvertices of $\bar{e}$, and let $u, v$ be any two vertices in $C$. Then we can obtain from $\bar{M}$ a larger antimatching $\bar{M}'$ by replacing the non-edge $\{x, y\}$ with the two non-edges $\{u, x\}$ and $\{v, y\}$, a contradiction. ◀

In the next claim we restrict further the neighborhoods of the equivalence classes in $V(\bar{C})$.

**► Claim 3.** Let $C_1, C_2 \in \mathcal{C}$ be two equivalence classes and let $\bar{e} \in \bar{M}$ be a non-edge with endpoints $x$ and $y$. Then it is not possible that $x \notin N_{\bar{e}}(C_1)$ and $y \notin N_{\bar{e}}(C_2)$, or vice versa.

**Proof.** Suppose for contradiction that $x \notin N_{\bar{e}}(C_1)$ and $y \notin N_{\bar{e}}(C_2)$, and let $u \in C_1$ and $v \in C_2$. Then we can obtain from $\bar{M}$ a larger antimatching $\bar{M}'$ by replacing the non-edge $\{x, y\}$ with the two non-edges $\{u, x\}$ and $\{v, y\}$, a contradiction. ◀

We call an equivalence class $C \in \mathcal{C}$ special if for some non-edge $\bar{e} \in \bar{M}$, $|N_{\bar{e}}(C)| = 0$, and we call such an $\bar{e}$ a special non-edge; otherwise we call an equivalence class normal. We call a non-edge $\bar{e} \in \bar{M}$ normal if for every $C \in \mathcal{C}$, $|N_{\bar{e}}(C)| \ge 1$. Let $k_s$ and $k_n$ be the number of special and normal non-edges in $\bar{M}$, respectively, and note that $k_s + k_n = |\bar{M}| \le k - 1$.

By Claim 2, every special class contains exactly one vertex. If $\bar{e} \in \bar{M}$ is a special non-edge and $C \in \mathcal{C}$ is such that $|N_{\bar{e}}(C)| = 0$, then Claim 3 implies that for every other class $C' \in \mathcal{C}$ different from $C$, it holds that $|N_{\bar{e}}(C')| = 2$. Therefore, the number of special classes in $C$ is at most the number of special non-edges in $\bar{M}$, that is, at most $k_s$.

Let $\bar{e} \in \bar{M}$ be a normal non-edge with endpoints $x, y$, let $C \in \mathcal{C}$ be such that $|N_{\bar{e}}(C)| = 1$, and assume that $N_{\bar{e}}(C) = \{x\}$. Then Claim 3 implies that for every class $C' \in \mathcal{C}$ such that $|N_{\bar{e}}(C')| = 1$, it holds that $N_{\bar{e}}(C') = \{x\}$. Hence, every normal non-edge $\bar{e} \in \bar{M}$ has at most one endpoint that has some non-neighbor in $K$; we call such a vertex the *avoidable* vertex of $\bar{e}$. This means that for every normal class $C \in \mathcal{C}$ and every non-edge $\bar{e} \in \bar{M}$, there are exactly two possibilities: either $|N_{\bar{e}}(C)| = 2$, or $|N_{\bar{e}}(C)| = 1$ and $N_{\bar{e}}(C)$ consists of the
12:8 Dual Parameterization of Weighted Coloring

endpoint of $\bar{e}$ distinct from its avoidable vertex. Moreover, by Claim 3 the latter case can
only occur if $\bar{e}$ is a normal non-edge. Therefore, the number of normal classes in $\mathcal{C}$ is at most
$2^{k_n} - 1$, corresponding to all the choices of neighborhoods in the set consisting of the avoidable
vertices in the normal edges in $\bar{M}$, and excluding the class $C$ with $N_{V(\bar{M})}(C) = V(\bar{M})$, since
these vertices would be deleted by Rule 1.

Finally, in order to bound the size of the equivalence classes in $\mathcal{C}$, we state the following reduction rule, which says that it is enough to keep, for each equivalence class, the $|\bar{M}|$ heaviest vertices.

**Rule 2.** Suppose there exists an equivalence class $C \in \mathcal{C}$ with $|C| > |\bar{M}|$. Let $W \subseteq C$ be a subset of vertices with $|W| = |\bar{M}|$ and such that, if $u \in W$ and $v \in C \setminus W$, then $w(u) \ge w(v)$. Delete from $G$ all the vertices in $C \setminus W$.

► Claim 4. Rule 2 is safe.

**Proof.** We need to prove that if $(G', w, k)$ results from $(G, w, k)$ after the application of Rule 2, then $(G, w, k)$ and $(G', w, k)$ are equivalent instances of DUAL WEIGHTED COLORING.

Assume first that $\sigma(G', w) \le \sum_{v \in V(G')} w(v) - k$, and let $c'$ be a coloring of $(G', w)$ satisfying this bound. We define a coloring $c$ of $(G, w)$ starting from $c'$ and creating a new color for each of the vertices in $C \setminus W$. Clearly, $w(c) = w(c') + \sum_{v \in C \setminus W} w(v) \le \sum_{v \in V(G)} w(v) - k$.

Conversely, assume that $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k$, and let $c$ be a coloring of $(G, w)$ satisfying this bound. Due to Rule 1, we can clearly assume that $|\bar{M}| \ge 1$. Hence, since Rule 2 has been applied on $C \in \mathcal{C}$, it follows that $|C| \ge 2$. Thus, by Claim 2, we have that for every non-edge $\bar{e} \in \bar{M}$, $|N_{\bar{e}}(C)| \ge 1$. This implies, together with the fact that the vertices in $C$ induce a clique, that in the coloring $c$ of $(G, w)$, at most $|\bar{M}|$ vertices of $C$ appear in colors containing vertices of $V(\bar{M})$, and every other vertex in $C$ is a singleton in its color. Let $T \subseteq C$ be this set of at most $|\bar{M}|$ vertices, and let $W \subseteq C$ be the set such that Rule 2 has deleted from $G$ the vertices in $C \setminus W$. We iteratively modify the coloring $c$ by updating the set $T$ as follows (the set $W$ remains the same). While there exists a vertex $u \in V(G)$ such that $u \in T$ and $u \notin W$, let $v \in W$ such that $v \notin T$ (note that vertex $v$ exists, since $|T| \le |\bar{M}| = |W|$), and swap $u$ and $v$ in the coloring, that is, now $u$ is a singleton in its color and $v$ is in a color containing vertices of $V(\bar{M})$. Since $u$ and $v$ are twins, this procedure indeed creates a proper coloring of $G$, which we also call $c$ with abuse of notation. Let us now argue that the weight of the coloring has not increased. Note that since $u \notin W$ and $v \in W$, it follows that $w(v) \ge w(u)$. If we denote by $S_i$ and $S_j$ the colors of $c$ before the swapping, so that $u \in S_i$ and $S_j = \{v\}$, and by $S'_i$ and $S'_j$ the corresponding colors after the swapping, note that $w(S_i) \ge w(u)$, $w(S_j) = w(v)$, $w(S'_i) = \max\{w(S_i), w(v)\}$, and $w(S'_j) = w(u)$. Therefore,

$$
w(S'_{i}) + w(S'_{j}) = \max\{w(S_{i}), w(v)\} + w(u) \le w(S_{i}) + w(v) = w(S_{i}) + w(S_{j}),
$$

where we have used that $w(v) \ge w(u)$. Thus, at the end of this procedure we obtain a
coloring $c$ with $w(c) \le \sum_{v \in V(G)} w(v) - k$ such that every vertex in $C \setminus W$ is a singleton in
its color class. We define $c'$ to be the restriction of $c$ to $G'$. Since every vertex in $C \setminus W =$
$V(G) \setminus V(G')$ is a singleton in its color class in $c$, it follows that

$$
w(c') = w(c) - \sum_{v \in C \setminus W} w(v) \le \left( \sum_{v \in V(G)} w(v) - k \right) - \sum_{v \in C \setminus W} w(v) = \sum_{v \in V(G')} w(v) - k,
$$

and the claim follows.

<figure><img src="image_70.png" /></figure>
12:8 Dual Parameterization of Weighted Coloring

endpoint of $\bar{e}$ distinct from its avoidable vertex. Moreover, by Claim 3 the latter case can
only occur if $\bar{e}$ is a normal non-edge. Therefore, the number of normal classes in $\mathcal{C}$ is at most
$2^{k_n} - 1$, corresponding to all the choices of neighborhoods in the set consisting of the avoidable
vertices in the normal edges in $\bar{M}$, and excluding the class $C$ with $N_{V(\bar{M})}(C) = V(\bar{M})$, since
these vertices would be deleted by Rule 1.

Finally, in order to bound the size of the equivalence classes in $\mathcal{C}$, we state the following reduction rule, which says that it is enough to keep, for each equivalence class, the $|\bar{M}|$ heaviest vertices.

**Rule 2.** Suppose there exists an equivalence class $C \in \mathcal{C}$ with $|C| > |\bar{M}|$. Let $W \subseteq C$ be a subset of vertices with $|W| = |\bar{M}|$ and such that, if $u \in W$ and $v \in C \setminus W$, then $w(u) \ge w(v)$. Delete from $G$ all the vertices in $C \setminus W$.

► Claim 4. Rule 2 is safe.

**Proof.** We need to prove that if $(G', w, k)$ results from $(G, w, k)$ after the application of Rule 2, then $(G, w, k)$ and $(G', w, k)$ are equivalent instances of DUAL WEIGHTED COLORING.

Assume first that $\sigma(G', w) \le \sum_{v \in V(G')} w(v) - k$, and let $c'$ be a coloring of $(G', w)$ satisfying this bound. We define a coloring $c$ of $(G, w)$ starting from $c'$ and creating a new color for each of the vertices in $C \setminus W$. Clearly, $w(c) = w(c') + \sum_{v \in C \setminus W} w(v) \le \sum_{v \in V(G)} w(v) - k$.

Conversely, assume that $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k$, and let $c$ be a coloring of $(G, w)$ satisfying this bound. Due to Rule 1, we can clearly assume that $|\bar{M}| \ge 1$. Hence, since Rule 2 has been applied on $C \in \mathcal{C}$, it follows that $|C| \ge 2$. Thus, by Claim 2, we have that for every non-edge $\bar{e} \in \bar{M}$, $|N_{\bar{e}}(C)| \ge 1$. This implies, together with the fact that the vertices in $C$ induce a clique, that in the coloring $c$ of $(G, w)$, at most $|\bar{M}|$ vertices of $C$ appear in colors containing vertices of $V(\bar{M})$, and every other vertex in $C$ is a singleton in its color. Let $T \subseteq C$ be this set of at most $|\bar{M}|$ vertices, and let $W \subseteq C$ be the set such that Rule 2 has deleted from $G$ the vertices in $C \setminus W$. We iteratively modify the coloring $c$ by updating the set $T$ as follows (the set $W$ remains the same). While there exists a vertex $u \in V(G)$ such that $u \in T$ and $u \notin W$, let $v \in W$ such that $v \notin T$ (note that vertex $v$ exists, since $|T| \le |\bar{M}| = |W|$), and swap $u$ and $v$ in the coloring, that is, now $u$ is a singleton in its color and $v$ is in a color containing vertices of $V(\bar{M})$. Since $u$ and $v$ are twins, this procedure indeed creates a proper coloring of $G$, which we also call $c$ with abuse of notation. Let us now argue that the weight of the coloring has not increased. Note that since $u \notin W$ and $v \in W$, it follows that $w(v) \ge w(u)$. If we denote by $S_i$ and $S_j$ the colors of $c$ before the swapping, so that $u \in S_i$ and $S_j = \{v\}$, and by $S'_i$ and $S'_j$ the corresponding colors after the swapping, note that $w(S_i) \ge w(u)$, $w(S_j) = w(v)$, $w(S'_i) = \max\{w(S_i), w(v)\}$, and $w(S'_j) = w(u)$. Therefore,

$$
w(S'_{i}) + w(S'_{j}) = \max\{w(S_{i}), w(v)\} + w(u) \le w(S_{i}) + w(v) = w(S_{i}) + w(S_{j}),
$$

where we have used that $w(v) \ge w(u)$. Thus, at the end of this procedure we obtain a
coloring $c$ with $w(c) \le \sum_{v \in V(G)} w(v) - k$ such that every vertex in $C \setminus W$ is a singleton in
its color class. We define $c'$ to be the restriction of $c$ to $G'$. Since every vertex in $C \setminus W =$
$V(G) \setminus V(G')$ is a singleton in its color class in $c$, it follows that

$$
w(c') = w(c) - \sum_{v \in C \setminus W} w(v) \le \left( \sum_{v \in V(G)} w(v) - k \right) - \sum_{v \in C \setminus W} w(v) = \sum_{v \in V(G')} w(v) - k,
$$

and the claim follows.

<figure><img src="image_73.png" /></figure>
We can easily apply Rule 2 exhaustively in polynomial time to all the classes $C \in \mathcal{C}$ with $|C| > |\bar{M}|$. We call an instance reduced if none of Rule 1 and Rule 2 can be applied anymore. The above discussion implies that if $(G, w, k)$ is a reduced instance, then

$$|V(G)| = |V(\bar{M})| + |K| \le 2(k-1) + k_s + (2^{k_n} - 1) \cdot (k-1).$$

Using that $k_s + k_n \le k - 1$, from the above equation we get that

$$|V(G)| \le 2(k-1) + (2^{k-1} - 1) \cdot (k-1) = (2^{k-1} + 1) \cdot (k-1),$$

and the theorem follows.

<figure><img src="image_71.png" /></figure>

It is worth mentioning that the analysis of the kernel size in the proof of Theorem 2 is tight. Indeed, let $G$ consist of an antimatching $\bar{M}$ of size $k-1$, and let $K$ consist of $2^{k-1}-1$ equivalence classes with $k-1$ vertices, each having a distinct non-complete neighborhood in the set consisting of one (arbitrary) vertex of each non-edge in $\bar{M}$. One can easily check that $|V(G)| = (2^{k-1} + 1) \cdot (k-1)$, that none of Rule 1 and Rule 2 can be applied to $G$, and that $G$ contains no antimatching strictly larger than $k-1$.

We complement the result of Theorem 2 by showing that, unless $\mathrm{NP} \subseteq \mathrm{coNP/poly}$, the problem does not admit polynomial kernels.

**Theorem 3.** *The DUAL WEIGHTED COLORING problem does not admit a polynomial kernel unless $\mathrm{NP} \subseteq \mathrm{coNP/poly}$, even on split graphs with only two different weights.*

**Proof.** We present a polynomial parameter transformation from the SET COVER problem parameterized by the size of the universe; Dom et al. [15] proved that this problem does not admit a polynomial kernel unless $\mathrm{NP} \subseteq \mathrm{coNP/poly}$. Our reduction is almost the same as the reduction of Demange et al. [12] from SET COVER to WEIGHTED COLORING on split graphs, only the vertex weights change. Let $(U, S, k, \ell)$ be an instance of SET COVER, where $S$ is a family of sets of elements over a universe $U$ of size $k$, and the question is whether there exists a subset $S' \subseteq S$ of at most $\ell$ sets covering all the elements of $U$. We construct an instance $(G, w, k')$ of DUAL WEIGHTED COLORING as follows. The graph $G$ contains a clique $K$ on $|S|$ vertices and an independent set $I$ on $k$ vertices. The vertices of $K$ and $I$ are associated, respectively, with the sets in $S$ and the elements in $U$. There is an edge between a vertex in $K$ and a vertex in $I$ if and only if the corresponding set does not contain the corresponding element. All the vertices in $K$ have weight $\ell$, and all the vertices in $I$ have weight $\ell+1$. Note that $G$ is indeed a split graph with only two different weights. Finally, we set $k' = k(\ell+1) - \ell$. Since we can clearly assume that $\ell \le k$, as otherwise the instance is trivial, it follows that $k' = \mathcal{O}(k^2)$, which is required in a polynomial parameter transformation. We claim that $(U, S, k, \ell)$ is a yes-instance of SET COVER if and only if $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k'$.

Assume first that $(U, S, k, \ell)$ is a yes-instance, and let $S' \subseteq S$ be a solution with $|S'| \le \ell$. We define a coloring $c$ of $G$ as follows. We start with a color for each vertex in $K$ and, for every element of $U$, we include its corresponding vertex of $I$ into one of the colors corresponding to the sets in $S'$ containing that element. One can easily check that $w(c) \le |S| \cdot \ell + \ell = \sum_{v \in V(G)} w(v) - k'$.

Conversely, assume that $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k' = |S| \cdot \ell + \ell$, and let $c$ be a coloring of $(G, k)$ achieving this bound. Since $\sum_{v \in K} w(v) = |S| \cdot \ell$ and the vertices in $I$ have weight $\ell+1$, all the vertices in $I$ have to be included in at most $\ell$ out of the $|S|$ colors of $c$ containing the vertices of the clique $K$. By construction of $G$, this is possible only if there exists a subset of at most $\ell$ sets in $S$ covering all the elements of $U$, and the theorem follows.

<figure><img src="image_72.png" /></figure>
We can easily apply Rule 2 exhaustively in polynomial time to all the classes $C \in \mathcal{C}$ with $|C| > |\bar{M}|$. We call an instance reduced if none of Rule 1 and Rule 2 can be applied anymore. The above discussion implies that if $(G, w, k)$ is a reduced instance, then

$$|V(G)| = |V(\bar{M})| + |K| \le 2(k-1) + k_s + (2^{k_n} - 1) \cdot (k-1).$$

Using that $k_s + k_n \le k - 1$, from the above equation we get that

$$|V(G)| \le 2(k-1) + (2^{k-1} - 1) \cdot (k-1) = (2^{k-1} + 1) \cdot (k-1),$$

and the theorem follows.

<figure><img src="image_74.png" /></figure>

It is worth mentioning that the analysis of the kernel size in the proof of Theorem 2 is tight. Indeed, let $G$ consist of an antimatching $\bar{M}$ of size $k-1$, and let $K$ consist of $2^{k-1}-1$ equivalence classes with $k-1$ vertices, each having a distinct non-complete neighborhood in the set consisting of one (arbitrary) vertex of each non-edge in $\bar{M}$. One can easily check that $|V(G)| = (2^{k-1} + 1) \cdot (k-1)$, that none of Rule 1 and Rule 2 can be applied to $G$, and that $G$ contains no antimatching strictly larger than $k-1$.

We complement the result of Theorem 2 by showing that, unless $NP \subseteq \text{coNP/poly}$, the problem does not admit polynomial kernels.

**Theorem 3.** *The DUAL WEIGHTED COLORING problem does not admit a polynomial kernel unless $NP \subseteq \text{coNP/poly}$, even on split graphs with only two different weights.*

**Proof.** We present a polynomial parameter transformation from the SET COVER problem parameterized by the size of the universe; Dom et al. [15] proved that this problem does not admit a polynomial kernel unless $NP \subseteq \text{coNP/poly}$. Our reduction is almost the same as the reduction of Demange et al. [12] from SET COVER to WEIGHTED COLORING on split graphs, only the vertex weights change. Let $(U, S, k, \ell)$ be an instance of SET COVER, where $S$ is a family of sets of elements over a universe $U$ of size $k$, and the question is whether there exists a subset $S' \subseteq S$ of at most $\ell$ sets covering all the elements of $U$. We construct an instance $(G, w, k')$ of DUAL WEIGHTED COLORING as follows. The graph $G$ contains a clique $K$ on $|S|$ vertices and an independent set $I$ on $k$ vertices. The vertices of $K$ and $I$ are associated, respectively, with the sets in $S$ and the elements in $U$. There is an edge between a vertex in $K$ and a vertex in $I$ if and only if the corresponding set does not contain the corresponding element. All the vertices in $K$ have weight $\ell$, and all the vertices in $I$ have weight $\ell+1$. Note that $G$ is indeed a split graph with only two different weights. Finally, we set $k' = k(\ell+1) - \ell$. Since we can clearly assume that $\ell \le k$, as otherwise the instance is trivial, it follows that $k' = \mathcal{O}(k^2)$, which is required in a polynomial parameter transformation. We claim that $(U, S, k, \ell)$ is a yes-instance of SET COVER if and only if $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k'$.

Assume first that $(U, S, k, \ell)$ is a yes-instance, and let $S' \subseteq S$ be a solution with $|S'| \le \ell$. We define a coloring $c$ of $G$ as follows. We start with a color for each vertex in $K$ and, for every element of $U$, we include its corresponding vertex of $I$ into one of the colors corresponding to the sets in $S'$ containing that element. One can easily check that $w(c) \le |S| \cdot \ell + \ell = \sum_{v \in V(G)} w(v) - k'$.

Conversely, assume that $\sigma(G, w) \le \sum_{v \in V(G)} w(v) - k' = |S| \cdot \ell + \ell$, and let $c$ be a coloring of $(G, k)$ achieving this bound. Since $\sum_{v \in K} w(v) = |S| \cdot \ell$ and the vertices in $I$ have weight $\ell+1$, all the vertices in $I$ have to be included in at most $\ell$ out of the $|S|$ colors of $c$ containing the vertices of the clique $K$. By construction of $G$, this is possible only if there exists a subset of at most $\ell$ sets in $S$ covering all the elements of $U$, and the theorem follows.

<figure><img src="image_75.png" /></figure>
12:10 Dual Parameterization of Weighted Coloring

In view of Theorem 3, in what follows we focus on identifying graph classes on which the DUAL WEIGHTED COLORING problem admits a polynomial kernel.

**Remark.** The problem clearly admits a kernel of size $\mathcal{O}(k)$ on sparse graphs, since if there are no large cliques, then the clique $K$ defined in the proof of Theorem 3 (that is, the remaining vertices of those in a maximum antimatching) is of constant size. More formally, if $\omega$ is the maximum clique size of a graph in the class, then we get a kernel with at most $2k - 2 + \omega$ vertices.

In our next result we provide a polynomial kernel on a relevant class of dense graphs, namely that of interval graphs.

**Proposition 4.** *The DUAL WEIGHTED COLORING problem restricted to interval graphs admits a kernel with at most $k^3 - k^2 + k - 1$ vertices.*

**Proof.** We will proceed as in the proof of Theorem 2 and show that, if the input graph $G$ is an interval graph, then the number of equivalence classes is quadratic in the parameter $k$. As before, we assume that $\bar{M}$ is a maximum antimatching of $G$, that $|\bar{M}| \le k - 1$, and also that Rule 1 and Rule 2 have been exhaustively applied. We also consider $K = V(G) \setminus V(\bar{M})$ and, as before, note that $K$ induces a clique.

We will show that the number of maximal cliques of $G$ is bounded by a linear function of $|\bar{M}|$. For that, we will make use of a well-known result of Fulkerson and Gross [22] stating that a graph $G$ is an interval graph if and only if the 0/1 incidence matrix $\mathcal{M}$ of vertices and maximal cliques of $G$ has the *consecutive ones property*, i.e., the columns of $\mathcal{M}$ can be permuted so that the ones in each row appear consecutively. A consequence of this result is that the set $\mathcal{C}$ of maximal cliques of $G$ can be arranged as $\{C_1, \dots, C_p\}$ in such a way that, for each vertex $v$, there are indices $\ell_v$ and $r_v$ such that $v \in C_i$ if and only if $\ell_v \le i \le r_v$. It is worth mentioning that this property appears implicitly in [23, proof of Theorem 2].

Note that the incidence of a vertex to the maximal cliques completely defines its neighborhood. This implies that $G$ has at most $\binom{p}{2}$ neighborhood classes. Hence, for obtaining a cubic kernel it suffices to show that $p = \mathcal{O}(k)$. In what follows we provide explicit bounds on both $p$ and the size of the kernel; we will show later that these bounds are tight.

**Claim 5.** *Let $G$ be an interval graph with $p \ge 2$ maximal cliques and let $\bar{M}$ be a maximum antimatching of $G$. Then $p \le 2|\bar{M}| + 1$.*

**Proof.** We proceed by induction on $p$. Clearly, if $p \in \{2, 3\}$, then there are at least two non-adjacent vertices, so $|\bar{M}| \ge 1$ and $p \le 2|\bar{M}| + 1$.

Let $\{C_1, \dots, C_p\}$ be an ordering of the maximal cliques of $G$ as defined above. Since the $C_i$'s are maximal cliques, for any two consecutive cliques $C_i$ and $C_{i+1}$ it holds that $C_i \setminus C_{i+1} \ne \emptyset$ and $C_{i+1} \setminus C_i \ne \emptyset$. In particular, together with the consecutive ones property, this implies that $C_1$ has an exclusive vertex $u$, that is, a vertex that does not belong to any maximal clique other than $C_1$. Similarly, $C_p$ has an exclusive vertex $v$. Let $G' = G[V(G) \setminus \{u, v\}]$, $\bar{M}'$ be a maximum antimatching of $G'$, and $p'$ be the number of maximal cliques of $G'$. By the induction hypothesis, $p' \le 2|\bar{M}'| + 1$.

Note that $C_2, \dots, C_{p-1}$ are maximal cliques in $G'$, hence $p - 2 \le p'$. On the other hand, $|\bar{M}'| \le |\bar{M}| - 1$, otherwise $\bar{M}' \cup \{uv\}$ would be an antimatching of cardinality greater than $|\bar{M}|$ in $G$. Putting all together,

$$p - 2 \le p' \le 2|\bar{M}'| + 1 \le 2(|\bar{M}| - 1) + 1 = 2|\bar{M}| - 1,$$

and $p \le 2|\bar{M}| + 1$. This completes the proof of the claim.

<figure><img src="image_73.png" /></figure>
12:10 Dual Parameterization of Weighted Coloring

In view of Theorem 3, in what follows we focus on identifying graph classes on which the
DUAL WEIGHTED COLORING problem admits a polynomial kernel.

► **Remark.** The problem clearly admits a kernel of size $\mathcal{O}(k)$ on sparse graphs, since if there are no large cliques, then the clique $K$ defined in the proof of Theorem 3 (that is, the remaining vertices of those in a maximum antimatching) is of constant size. More formally, if $\omega$ is the maximum clique size of a graph in the class, then we get a kernel with at most $2k - 2 + \omega$ vertices.

In our next result we provide a polynomial kernel on a relevant class of dense graphs,
namely that of interval graphs.

**► Proposition 4.** *The DUAL WEIGHTED COLORING problem restricted to interval graphs admits a kernel with at most $k^3 - k^2 + k - 1$ vertices.*

**Proof.** We will proceed as in the proof of Theorem 2 and show that, if the input graph $G$ is an interval graph, then the number of equivalence classes is quadratic in the parameter $k$. As before, we assume that $\bar{M}$ is a maximum antimatching of $G$, that $|\bar{M}| \le k-1$, and also that Rule 1 and Rule 2 have been exhaustively applied. We also consider $K = V(G) \setminus V(\bar{M})$ and, as before, note that $K$ induces a clique.

We will show that the number of maximal cliques of $G$ is bounded by a linear function of $|\bar{M}|$. For that, we will make use of a well-known result of Fulkerson and Gross [22] stating that a graph $G$ is an interval graph if and only if the 0/1 incidence matrix $\mathcal{M}$ of vertices and maximal cliques of $G$ has the *consecutive ones property*, i.e., the columns of $\mathcal{M}$ can be permuted so that the ones in each row appear consecutively. A consequence of this result is that the set $\mathcal{C}$ of maximal cliques of $G$ can be arranged as $\{C_1, \dots, C_p\}$ in such a way that, for each vertex $v$, there are indices $\ell_v$ and $r_v$ such that $v \in C_i$ if and only if $\ell_v \le i \le r_v$. It is worth mentioning that this property appears implicitly in [23, proof of Theorem 2].

Note that the incidence of a vertex to the maximal cliques completely defines its neighborhood. This implies that $G$ has at most $\binom{p}{2}$ neighborhood classes. Hence, for obtaining a cubic kernel it suffices to show that $p = \mathcal{O}(k)$. In what follows we provide explicit bounds on both $p$ and the size of the kernel; we will show later that these bounds are tight.

**► Claim 5.** Let $G$ be an interval graph with $p \ge 2$ maximal cliques and let $\bar{M}$ be a maximum antimatching of $G$. Then $p \le 2|\bar{M}| + 1$.

**Proof.** We proceed by induction on $p$. Clearly, if $p \in \{2, 3\}$, then there are at least two non-adjacent vertices, so $|\bar{M}| \ge 1$ and $p \le 2|\bar{M}| + 1$.

Let $\{C_1, \dots, C_p\}$ be an ordering of the maximal cliques of $G$ as defined above. Since the $C_i$'s are maximal cliques, for any two consecutive cliques $C_i$ and $C_{i+1}$ it holds that $C_i \setminus C_{i+1} \ne \emptyset$ and $C_{i+1} \setminus C_i \ne \emptyset$. In particular, together with the consecutive ones property, this implies that $C_1$ has an exclusive vertex $u$, that is, a vertex that does not belong to any maximal clique other than $C_1$. Similarly, $C_p$ has an exclusive vertex $v$. Let $G' = G[V(G) \setminus \{u, v\}]$, $\bar{M}'$ be a maximum antimatching of $G'$, and $p'$ be the number of maximal cliques of $G'$. By the induction hypothesis, $p' \le 2|\bar{M}'| + 1$.

Note that $C_2, \dots, C_{p-1}$ are maximal cliques in $G'$, hence $p-2 \le p'$. On the other hand, $|\bar{M}'| \le |\bar{M}| - 1$, otherwise $\bar{M}' \cup \{uv\}$ would be an antimatching of cardinality greater than $|\bar{M}|$ in $G$. Putting all together,

$$p-2 \le p' \le 2|\bar{M}'| + 1 \le 2(|\bar{M}| - 1) + 1 = 2|\bar{M}| - 1,$$

and $p \le 2|\bar{M}| + 1$. This completes the proof of the claim.

<figure><img src="image_76.png" /></figure>
Since $K$ is a clique, there is an index $i$ such that $K \subseteq C_i$. For each $v \in K$, let $\ell_v$ be the smallest index such that $v \in C_{\ell_v}$ and $r_v$ be the largest index such that $v \in C_{r_v}$. Recall that $\ell_v$ and $r_v$ completely define the neighborhood of $v$. Note that for all $v \in K$, $\ell_v \le i \le r_v$ and that either $\ell_v \ne 1$ or $r_v \ne p$, since otherwise $v$ would be a universal vertex, which is impossible because we applied Rule 1 exhaustively. Hence, the maximum number of distinct possible combinations of indices $\ell_v$ and $r_v$ is $i \cdot (p - i + 1) - 1$, which is maximized when $i = \lfloor \frac{p+1}{2} \rfloor$, giving a total number of

$$ \lfloor \frac{p+1}{2} \rfloor \cdot \lfloor \frac{p+1}{2} \rfloor - 1 $$

distinct equivalence classes. Using the fact that $p \le 2|\bar{M}|+1$ by Claim 5, and that $|\bar{M}| \le k-1$, we get

$$ \lfloor \frac{p+1}{2} \rfloor \cdot \lfloor \frac{p+1}{2} \rfloor - 1 = k^2 - 1. $$

Since, by virtue of the application of Rule 2, each class has at most $(k-1)$ elements, we have

$$ |V(G)| = |V(\bar{M})| + |V(K)| \le 2(k-1) + (k-1) \cdot (k^2 - 1) = k^3 - k^2 + k - 1. \quad \triangle $$

Similarly to Theorem 2, we can show that the analysis of the kernel size in the proof of Proposition 4 is tight. Indeed, given an integer $k$, it is possible to build an interval graph with $2k-1$ maximal cliques, with $(k-1)$ vertices belonging exactly to cliques $C_i, \dots, C_j$, for each

$$ (i, j) \in [1, k] \times [k, 2k-1] \setminus \{(1, 2k-1)\}, $$

and one exclusive vertex in each clique, except for clique $C_k$, corresponding to vertices of $V(\bar{M})$. That interval graph attains the bound in the statement of Proposition 4 and cannot be reduced by Rule 1 or Rule 2.

**Remark.** The result of Proposition 4 cannot be generalized to chordal graphs, as split graphs are chordal, and by Theorem 3 the existence of a polynomial kernel on split graphs would imply that $NP \subseteq \text{coNP/poly}$.

Our last result deals with a subclass of split graphs motivated by the fact that DUAL WEIGHTED COLORING on split graphs seems to have a close relation with the SET COVER problem.

**Proposition 5.** The DUAL WEIGHTED COLORING problem restricted to split graphs such that each vertex in the clique has at most $d$ non-neighbors in the stable set, for some constant $d \ge 1$, admits a kernel with at most $k^{d+1}$ vertices. Furthermore, for any $d \ge 2$ and $\varepsilon > 0$, a kernel with $O(k^{\frac{d-3}{2}-\varepsilon})$ vertices does not exist unless $NP \subseteq \text{coNP/poly}$.

**Proof.** For the positive result, let $(G, w, k)$ be an instance of DUAL WEIGHTED COLORING, with $G$ being a split graph such that each vertex in the clique has at most $d$ non-neighbors in the stable set, for some integer $d \ge 2$. We mimic the proof of Theorem 2, and we slightly change the analysis. Recall that $|V(\bar{M})| \le 2(k-1)$ and that the number of special classes in $C$, each containing exactly one vertex, is at most $k_s$. Concerning the normal classes in $C$, we will obtain an improved bound using that each vertex in the clique has at most $d$ non-neighbors in the stable set, and therefore in the graph $G$ itself as well. Thus, the number of distinct neighborhoods in the set consisting of the avoidable vertices in