**Theorem 6.** PERFECT TARGET SET SELECTION with thresholds being at most three can be solved in $O^*(1.98577^n)$ time.

## 3.3 Algorithm for thresholds bounded by one-third of degrees

Here, we prove the following.

**Theorem 7.** Let $G$ be a connected graph with at least three vertices. Assume that $\text{thr}(v) \le \lfloor \frac{\text{deg}(v)}{3} \rfloor$ for every $v \in V(G)$. Then there is a perfect target set of $(G, \text{thr})$ of size at most $0.45|V(G)|$.

**Corollary 8.** TARGET SET SELECTION with thresholds bounded by one-third of degree rounded up can be solved in $O^*(1.99001^n)$ time.

In our proofs we use a combinatorial model proposed by Ackerman et al. in [2]. We provide these proofs in the full version of our paper.

# 4 Algorithm for bounded dual thresholds

Let $(G, \text{thr})$ be a graph with thresholds. By dual threshold of vertex $v \in V(G)$ we understand the value $\text{thr}(v) = \text{deg}(v) - \text{thr}(v)$. In terms of dual thresholds, $v$ becomes activated if it has at most $\text{thr}(v)$ not activated neighbours. For bounded dual thresholds we prove the following theorem.

**Theorem 9.** For any non-negative integer $d$, PERFECT TARGET SET SELECTION with dual thresholds bounded by $d$ can be solved in $O^*((2 - \epsilon_d)^n)$ randomized time for some $\epsilon_d > 0$.

This result follows from the result of Pilipczuk and Pilipczuk in [28], where they presented an algorithm for the MAXIMUM $d$-DEGENERATE INDUCED SUBGRAPH problem with the same running time. One may find the detailed proof in the full version of our paper.

# 5 Lower bounds

## 5.1 ETH lower bound

First of all, we show a $2^{o(n+m)}$ lower bound for PERFECT TARGET SET SELECTION, where $m$ denotes the number of edges in the input graph. We have not found any source that claims this result. Thus, for completeness, we state it here. The result follows from the reduction given by Centeno et al. in [10]. They showed a linear reduction from a special case of 3-SAT, where each variable appears at most three times, to PERFECT TARGET SET SELECTION where thresholds are equal to two and maximum degree of the graph is constant. Note that in their work they refer to the problem as IRR$_2$-CONVERSION SET.

**Theorem 10.** PERFECT TARGET SET SELECTION cannot be solved in $2^{o(n+m)}$ time unless ETH fails, even when thresholds are equal to two and maximum degree of the graph is constant.

One can find the detailed proof in the full version of our paper.

## 5.2 Parameterization by $\ell$

We now look at TARGET SET SELECTION from parameterized point of view. In [5], Bazgan et al. proved that TARGET SET SELECTION $\ell$ is W[1]-hard with respect to parameter $\ell$, when all dual thresholds are equal to 0. This result also follows from the proof of W[1]-hardness
of CUTTING $\ell$ VERTICES given by Marx in [25], with a somewhat different construction. Inspired by his proof, we show that this result holds even when all thresholds are constant.

**Theorem 11.** TARGET SET SELECTION parameterized by $\ell$ is $W[1]$-hard even when all thresholds are equal to two.

**Proof.** Let $(G, k)$ be an instance of the CLIQUE problem. In order to provide the reduction, we construct a graph $G'$ in which each vertex corresponds to a vertex or an edge of graph $G$ i.e. $V(G') = V(G) \sqcup E(G)$. We add edges in $G'$ between vertices corresponding to $v \in V(G)$ and $e \in E(G)$ if and only if $v$ and $e$ are incident in $G$.

We will refer to the vertex in $G'$ corresponding to an edge $e \in E(G)$ as $v_e \in V(G')$. If a vertex from $G'$ corresponds to a vertex $u \in G$ we refer to it as $v_u$. Slightly abusing notation we will refer to the set of vertices in $G'$ corresponding to the vertices $V(G)$ as $V$ and to the set of vertices corresponding to the edges $E(G)$ as $E$, $V \sqcup E = V(G')$. Consider now an instance of TARGET SET SELECTION for $G'$, with the same $k$, $\ell = k + \binom{k}{2}$ and all thresholds equal to $t = 2$.

If $G$ has a clique of size $k$, then selecting corresponding vertices as a target set of $G'$ leads to activation of the vertices corresponding to the edges of the clique. Hence, $k + \binom{k}{2}$ vertices will be activated in total.

Let us now prove that if $G'$ has a target set of size at most $k$ activating at least $\ell = k + \binom{k}{2}$ vertices, then $G$ has a clique on $k$ vertices. Let $S$ be such target set of $G'$. Denote by $k_v = |S \cap V|$ the number of vertices in $S$ corresponding to the vertices of $G$ and by $k_e = |S \cap E|$ the number of vertices in $S$ corresponding to the edges of $G$, $k_v + k_e \le k$.

Now, we show how to convert any target set $S$ of size at most $k$ activating at least $k + \binom{k}{2}$ vertices into a target set $S'$ such that $|S'| \le k$, $S' \subseteq V$ and $S'$ activates at least $k + \binom{k}{2}$ vertices.

Observe that if there is an edge $u_1u_2 = e \in E(G)$ such that $v_e \in S$ and $v_{u_1} \in S$ then $S' = S \setminus \{v_e\} \cup \{v_{u_2}\}$ also activates at least $k + \binom{k}{2}$ vertices and the size of $S'$ is at most $k$. Thus we can assume that if $v_{u_1u_2} \in S$, then $v_{u_1}, v_{u_2} \notin S$.

Observe that any initially not activated vertex in $E$ becomes activated only if all two of its neighbours are activated. It means that any such vertex does not influence the activation process in future. Hence, since $G'$ is bipartite, the activation process always finishes within two rounds, and no vertex in $V$ becomes activated in the second round.

Let $V_1$ be the set of vertices of $V$ that become activated by $S$ in the first round, i.e. $V_1 = S_1(S) \setminus S_0(S) \cap V$. Note that these vertices are activated directly by $k_e$ vertices in $S \cap E$. Let $S_{E,i}$ be the set of vertices in $S \cap E$ that have exactly $i$ endpoints in $V_1$. Denote by $k_{e,i}$ the size of $S_{E,i}$. Then we have $k_{e,0} + k_{e,1} + k_{e,2} = k_e$. Note that if there is a vertex in $S \cap E$ with no endpoints in $V_1$ then one can replace it with any neighbour and size of $S$ will not change and it will activate at least the same number of vertices in $G'$. Thus we can assume that $k_{e,0} = 0$.

We show that $|V_1| \le \frac{k_{e,1}}{2} + k_{e,2}$. Indeed, in order to be activated, any vertex from $V_1$ requires at least two vertices from $E$ to be in the target set. Each vertex from $S_{E,i}$ contributes to exactly $i$ vertices from $V_1$, and the total number of contributions is $k_{e,1} + 2k_{e,2}$. This number should be at least $2|V_1|$. Hence, $|V_1| \le \frac{k_{e,1}}{2} + k_{e,2}$.

Consider $S' = S \setminus E \cup V_1$ i.e. we replace all $k_e$ vertices from $E$ with all vertices from $V_1$. Note that $|S'| \le |S| - \frac{k_{e,1}}{2}$. Vertices from $S_{E,2}$ become activated in the first round since all of them have two endpoints in $S'$. Thus $S'$ is now a target set of size not greater than $k - \frac{k_{e,1}}{2}$ activating at least $\ell - k_{e,1}$ vertices in $G'$.

Note that any vertex from $S_{E,1}$ can be activated by adding one more vertex to $S'$. Consider set $H = N(S_{E,1}) \setminus V_1$. If $|H| \le \frac{k_{e,1}}{2}$ then consider $S_1 = H \cup S'$. $S_1$ compared to $S'$
of CUTTING $\ell$ VERTICES given by Marx in [25], with a somewhat different construction. Inspired by his proof, we show that this result holds even when all thresholds are constant.

**Theorem 11.** TARGET SET SELECTION parameterized by $\ell$ is $W[1]$-hard even when all thresholds are equal to two.

**Proof.** Let $(G, k)$ be an instance of the CLIQUE problem. In order to provide the reduction, we construct a graph $G'$ in which each vertex corresponds to a vertex or an edge of graph $G$ i.e. $V(G') = V(G) \sqcup E(G)$. We add edges in $G'$ between vertices corresponding to $v \in V(G)$ and $e \in E(G)$ if and only if $v$ and $e$ are incident in $G$.

We will refer to the vertex in $G'$ corresponding to an edge $e \in E(G)$ as $v_e \in V(G')$. If a vertex from $G'$ corresponds to a vertex $u \in G$ we refer to it as $v_u$. Slightly abusing notation we will refer to the set of vertices in $G'$ corresponding to the vertices $V(G)$ as $V$ and to the set of vertices corresponding to the edges $E(G)$ as $E$, $V \sqcup E = V(G')$. Consider now an instance of TARGET SET SELECTION for $G'$, with the same $k$, $\ell = k + \binom{k}{2}$ and all thresholds equal to $t=2$.

If $G$ has a clique of size $k$, then selecting corresponding vertices as a target set of $G'$ leads to activation of the vertices corresponding to the edges of the clique. Hence, $k + \binom{k}{2}$ vertices will be activated in total.

Let us now prove that if $G'$ has a target set of size at most $k$ activating at least $\ell = k + \binom{k}{2}$ vertices, then $G$ has a clique on $k$ vertices. Let $S$ be such target set of $G'$. Denote by $k_v = |S \cap V|$ the number of vertices in $S$ corresponding to the vertices of $G$ and by $k_e = |S \cap E|$ the number of vertices in $S$ corresponding to the edges of $G$, $k_v + k_e \le k$.

Now, we show how to convert any target set $S$ of size at most $k$ activating at least $k + \binom{k}{2}$ vertices into a target set $S'$ such that $|S'| \le k$, $S' \subseteq V$ and $S'$ activates at least $k + \binom{k}{2}$ vertices.

Observe that if there is an edge $u_1u_2 = e \in E(G)$ such that $v_e \in S$ and $v_{u_1} \in S$ then $S' = S \setminus \{v_e\} \cup \{v_{u_2}\}$ also activates at least $k + \binom{k}{2}$ vertices and the size of $S'$ is at most $k$. Thus we can assume that if $v_{u_1u_2} \in S$, then $v_{u_1}, v_{u_2} \notin S$.

Observe that any initially not activated vertex in $E$ becomes activated only if all two of its neighbours are activated. It means that any such vertex does not influence the activation process in future. Hence, since $G'$ is bipartite, the activation process always finishes within two rounds, and no vertex in $V$ becomes activated in the second round.

Let $V_1$ be the set of vertices of $V$ that become activated by $S$ in the first round, i.e. $V_1 = S_1(S) \setminus S_0(S) \cap V$. Note that these vertices are activated directly by $k_e$ vertices in $S \cap E$. Let $S_{E,i}$ be the set of vertices in $S \cap E$ that have exactly $i$ endpoints in $V_1$. Denote by $k_{e,i}$ the size of $S_{E,i}$. Then we have $k_{e,0} + k_{e,1} + k_{e,2} = k_e$. Note that if there is a vertex in $S \cap E$ with no endpoints in $V_1$ then one can replace it with any neighbour and size of $S$ will not change and it will activate at least the same number of vertices in $G'$. Thus we can assume that $k_{e,0} = 0$.

We show that $|V_1| \le \frac{k_{e,1}}{2} + k_{e,2}$. Indeed, in order to be activated, any vertex from $V_1$ requires at least two vertices from $E$ to be in the target set. Each vertex from $S_{E,i}$ contributes to exactly $i$ vertices from $V_1$, and the total number of contributions is $k_{e,1} + 2k_{e,2}$. This number should be at least $2|V_1|$. Hence, $|V_1| \le \frac{k_{e,1}}{2} + k_{e,2}$.

Consider $S' = S \setminus E \cup V_1$ i.e. we replace all $k_e$ vertices from $E$ with all vertices from $V_1$. Note that $|S'| \le |S| - \frac{k_{e,1}}{2}$. Vertices from $S_{E,2}$ become activated in the first round since all of them have two endpoints in $S'$. Thus $S'$ is now a target set of size not greater than $k - \frac{k_{e,1}}{2}$ activating at least $\ell - k_{e,1}$ vertices in $G'$.

Note that any vertex from $S_{E,1}$ can be activated by adding one more vertex to $S'$. Consider set $H = N(S_{E,1}) \setminus V_1$. If $|H| \le \frac{k_{e,1}}{2}$ then consider $S_1 = H \cup S'$. $S_1$ compared to $S'$
will additionally activate all vertices in $S_{E,1}$. Note that $S_1$ is a target set $S$ of size at most $k$ activating at least $\ell$ vertices.

If $|H| > \frac{k_{e,1}}{2}$ then construct $S_1$ from $S'$ by simply adding $\frac{k_{e,1}}{2}$ arbitrary vertices from $H$. Each of these vertices will additionally activate at least one vertex corresponding to edge, thus $S_1$ is a target set of size at most $k$ activating at least $\ell$ vertices.

We have shown how to transform any target set $S$ activating at least $k + \binom{k}{2}$ vertices in $G'$ into a target set $S_1$ such that $S_1 \subseteq V$ and $S_1$ activates at least the same number of vertices in $G'$. As we have shown earlier, no vertex in $E \setminus S_1$ influence the activation process after becoming activated. Then, since $S_1 \cap E = \emptyset$, $S_1$ activates only vertices in $E$ in the first round and the process finishes. Hence, if the instance for $G'$ has a solution, then $G$ has a clique of size $k$. ◀

References

1. Karl A. Abrahamson, Rodney G. Downey, and Michael R. Fellows. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues. *Annals of Pure and Applied Logic*, 73(3):235–276, June 1995. doi:10.1016/0168-0072(94)00034-z.

2. Eyal Ackerman, Oren Ben-Zwi, and Guy Wolfovitz. Combinatorial model and bounds for target set selection. *Theoretical Computer Science*, 411(44-46):4017–4022, October 2010. doi:10.1016/j.tcs.2010.08.021.

3. R.T. Araújo, R.M. Sampaio, and J.L. Szwartfiter. The convexity of induced paths of order three. *Electronic Notes in Discrete Mathematics*, 44:109–114, November 2013. doi:10.1016/j.endm.2013.10.017.

4. József Balogh, Béla Bollobás, and Robert Morris. Bootstrap percolation in high dimensions. *Combinatorics, Probability and Computing*, 19(5-6):643–692, 2010.

5. Cristina Bazgan, Morgan Chopin, André Nichterlein, and Florian Sikora. Parameterized approximability of maximizing the spread of influence in networks. *Journal of Discrete Algorithms*, 27:54–65, July 2014. doi:10.1016/j.jda.2014.05.001.

6. Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, and Ilan Newman. Treewidth governs the complexity of target set selection. *Discrete Optimization*, 8(1):87–96, February 2011. doi:10.1016/j.disopt.2010.09.007.

7. Daniel Binkele-Raible, Ljiljana Brankovic, Marek Cygan, Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Marcin Pilipczuk, Peter Rossmanith, and Jakub Onufry Wojtaszczyk. Breaking the 2ⁿ-barrier for IRREDUNDANCE: Two lines of attack. *Journal of Discrete Algorithms*, 9(3):214–230, September 2011. doi:10.1016/j.jda.2011.03.002.

8. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. The traveling salesman problem in bounded degree graphs. *ACM Transactions on Algorithms*, 8(2):1–13, April 2012. doi:10.1145/2151171.2151181.

9. Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk, and Yngve Villanger. Largest Chordal and Interval Subgraphs Faster Than 2ⁿ. In *Lecture Notes in Computer Science*, pages 193–204. Springer Berlin Heidelberg, 2013. doi:10.1007/978-3-642-40450-4_17.

10. Carmen C. Centeno, Mitre C. Dourado, Lucia Draque Penso, Dieter Rautenbach, and Jayme L. Szwartfiter. Irreversible conversion of graphs. *Theoretical Computer Science*, 412(29):3693–3700, July 2011. doi:10.1016/j.tcs.2011.03.029.

11. Ning Chen. On the Approximability of Influence in Social Networks. *SIAM Journal on Discrete Mathematics*, 23(3):1400–1415, January 2009. doi:10.1137/08073617x.

12. Morgan Chopin, André Nichterlein, Rolf Niedermeier, and Mathias Weller. Constant Thresholds Can Make Target Set Selection Tractable. *Theory of Computing Systems*, 55(1):61–83, September 2013. doi:10.1007/s00224-013-9499-3.
will additionally activate all vertices in $S_{E,1}$. Note that $S_1$ is a target set $S$ of size at most $k$ activating at least $\ell$ vertices.

If $|H| > \frac{k_{e,1}}{2}$ then construct $S_1$ from $S'$ by simply adding $\frac{k_{e,1}}{2}$ arbitrary vertices from $H$. Each of these vertices will additionally activate at least one vertex corresponding to edge, thus $S_1$ is a target set of size at most $k$ activating at least $\ell$ vertices.

We have shown how to transform any target set $S$ activating at least $k + \binom{k}{2}$ vertices in $G'$ into a target set $S_1$ such that $S_1 \subseteq V$ and $S_1$ activates at least the same number of vertices in $G'$. As we have shown earlier, no vertex in $E \setminus S_1$ influence the activation process after becoming activated. Then, since $S_1 \cap E = \emptyset$, $S_1$ activates only vertices in $E$ in the first round and the process finishes. Hence, if the instance for $G'$ has a solution, then $G$ has a clique of size $k$. ◀

References

1. Karl A. Abrahamson, Rodney G. Downey, and Michael R. Fellows. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues. *Annals of Pure and Applied Logic*, 73(3):235–276, June 1995. doi:10.1016/0168-0072(94)00034-z.

2. Eyal Ackerman, Oren Ben-Zwi, and Guy Wolfovitz. Combinatorial model and bounds for target set selection. *Theoretical Computer Science*, 411(44-46):4017–4022, October 2010. doi:10.1016/j.tcs.2010.08.021.

3. R.T. Araújo, R.M. Sampaio, and J.L. Szwartfiter. The convexity of induced paths of order three. *Electronic Notes in Discrete Mathematics*, 44:109–114, November 2013. doi:10.1016/j.endm.2013.10.017.

4. József Balogh, Béla Bollobás, and Robert Morris. Bootstrap percolation in high dimensions. *Combinatorics, Probability and Computing*, 19(5-6):643–692, 2010.

5. Cristina Bazgan, Morgan Chopin, André Nichterlein, and Florian Sikora. Parameterized approximability of maximizing the spread of influence in networks. *Journal of Discrete Algorithms*, 27:54–65, July 2014. doi:10.1016/j.jda.2014.05.001.

6. Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, and Ilan Newman. Treewidth governs the complexity of target set selection. *Discrete Optimization*, 8(1):87–96, February 2011. doi:10.1016/j.disopt.2010.09.007.

7. Daniel Binkele-Raible, Ljiljana Brankovic, Marek Cygan, Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Marcin Pilipczuk, Peter Rossmanith, and Jakub Onufry Wojtaszczyk. Breaking the 2ⁿ-barrier for IRREDUNDANCE: Two lines of attack. *Journal of Discrete Algorithms*, 9(3):214–230, September 2011. doi:10.1016/j.jda.2011.03.002.

8. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. The traveling salesman problem in bounded degree graphs. *ACM Transactions on Algorithms*, 8(2):1–13, April 2012. doi:10.1145/2151171.2151181.

9. Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk, and Yngve Villanger. Largest Chordal and Interval Subgraphs Faster Than 2ⁿ. In *Lecture Notes in Computer Science*, pages 193–204. Springer Berlin Heidelberg, 2013. doi:10.1007/978-3-642-40450-4_17.

10. Carmen C. Centeno, Mitre C. Dourado, Lucia Draque Penso, Dieter Rautenbach, and Jayme L. Szwartfiter. Irreversible conversion of graphs. *Theoretical Computer Science*, 412(29):3693–3700, July 2011. doi:10.1016/j.tcs.2011.03.029.

11. Ning Chen. On the Approximability of Influence in Social Networks. *SIAM Journal on Discrete Mathematics*, 23(3):1400–1415, January 2009. doi:10.1137/08073617x.

12. Morgan Chopin, André Nichterlein, Rolf Niedermeier, and Mathias Weller. Constant Thresholds Can Make Target Set Selection Tractable. *Theory of Computing Systems*, 55(1):61–83, September 2013. doi:10.1007/s00224-013-9499-3.
13 Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Wojtaszczyk. Scheduling Partially Ordered Jobs Faster than 2ⁿ. Algorithmica, 68(3):692-714, October 2012. doi:10.1007/s00453-012-9694-7.

14 Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Wojtaszczyk. Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2ⁿ. Algorithmica, 70(2):195-207, May 2013. doi:10.1007/s00453-013-9796-x.

15 Marek Cygan, Marcin Pilipczuk, and Jakub Onufry Wojtaszczyk. Capacitated Domination Faster Than O(2ⁿ). In Lecture Notes in Computer Science, pages 74-80. Springer Berlin Heidelberg, 2010. doi:10.1007/978-3-642-13731-0_8.

16 Paul A. Dreyer Jr. and Fred S. Roberts. Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion. Discrete Applied Mathematics, 157(7):1615-1627, 2009.

17 Pavel Dvořák, Dušan Knop, and Tomáš Toufar. Target Set Selection in Dense Graph Classes. arXiv preprint arXiv:1610.07530, 2016.

18 Fedor V. Fomin, Serge Gaspers, Artem V. Pyatkin, and Igor Razgon. On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms. Algorithmica, 52(2):293-307, December 2007. doi:10.1007/s00453-007-9152-0.

19 Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch. Solving Connected Dominating Set Faster than 2ⁿ. Algorithmica, 52(2):153-166, December 2007. doi:10.1007/s00453-007-9145-z.

20 Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Charis Papadopoulos, and Yngve Villanger. Enumerating Minimal Subset Feedback Vertex Sets. Algorithmica, 69(1):216-231, December 2012. doi:10.1007/s00453-012-9731-6.

21 Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Springer-Verlag, Berlin, Heidelberg, 1st edition, 2010.

22 Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. Exact Algorithm for the Maximum Induced Planar Subgraph Problem. In Algorithms - ESA 2011, pages 287-298. Springer Berlin Heidelberg, 2011. doi:10.1007/978-3-642-23719-5_25.

23 Tim A. Hartmann. Target Set Selection Parameterized by Clique-Width and Maximum Threshold. In SOFSEM 2018: Theory and Practice of Computer Science, pages 137-149. Springer International Publishing, December 2017. doi:10.1007/978-3-319-73117-9_10.

24 David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '03. ACM Press, 2003. doi:10.1145/956750.956769.

25 Dániel Marx. Parameterized graph separation problems. Theoretical Computer Science, 351(3):394-406, February 2006. doi:10.1016/j.tcs.2005.10.007.

26 André Nichterlein, Rolf Niedermeier, Johannes Uhlmann, and Mathias Weller. On tractable cases of Target Set Selection. Social Network Analysis and Mining, 3(2):233-256, May 2012. doi:10.1007/s13278-012-0067-7.

27 D. Peleg. Size bounds for dynamic monopolies. Discrete Applied Mathematics, 86(2-3):263-273, September 1998. doi:10.1016/s0166-218x(98)00043-2.

28 Marcin Pilipczuk and Michał Pilipczuk. Finding a Maximum Induced Degenerate Subgraph Faster Than 2ⁿ. In Parameterized and Exact Computation, pages 3-12. Springer Berlin Heidelberg, 2012. doi:10.1007/978-3-642-33293-7_3.

29 Michał Pilipczuk. Exact Algorithms for Induced Subgraph Problems. In Encyclopedia of Algorithms, pages 1-5. Springer US, 2015. doi:10.1007/978-3-642-27848-8_520-1.

30 Igor Razgon. Computing Minimum Directed Feedback Vertex Set in O*(1.9977ⁿ). In Theoretical Computer Science, pages 70-81. World Scientific, 2007.
13 Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Wojtaszczyk. Scheduling Partially Ordered Jobs Faster than 2ⁿ. Algorithmica, 68(3):692–714, October 2012. doi:10.1007/s00453-012-9694-7.

14 Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, and Jakub Onufry Wojtaszczyk. Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2ⁿ. Algorithmica, 70(2):195–207, May 2013. doi:10.1007/s00453-013-9796-x.

15 Marek Cygan, Marcin Pilipczuk, and Jakub Onufry Wojtaszczyk. Capacitated Domination Faster Than O(2ⁿ). In Lecture Notes in Computer Science, pages 74–80. Springer Berlin Heidelberg, 2010. doi:10.1007/978-3-642-13731-0_8.

16 Paul A. Dreyer Jr. and Fred S. Roberts. Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion. Discrete Applied Mathematics, 157(7):1615–1627, 2009.

17 Pavel Dvořák, Dušan Knop, and Tomáš Toufar. Target Set Selection in Dense Graph Classes. arXiv preprint arXiv:1610.07530, 2016.

18 Fedor V. Fomin, Serge Gaspers, Artem V. Pyatkin, and Igor Razgon. On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms. Algorithmica, 52(2):293–307, December 2007. doi:10.1007/s00453-007-9152-0.

19 Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch. Solving Connected Dominating Set Faster than 2ⁿ. Algorithmica, 52(2):153–166, December 2007. doi:10.1007/s00453-007-9145-z.

20 Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Charis Papadopoulos, and Yngve Villanger. Enumerating Minimal Subset Feedback Vertex Sets. Algorithmica, 69(1):216–231, December 2012. doi:10.1007/s00453-012-9731-6.

21 Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Springer-Verlag, Berlin, Heidelberg, 1st edition, 2010.

22 Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. Exact Algorithm for the Maximum Induced Planar Subgraph Problem. In Algorithms – ESA 2011, pages 287–298. Springer Berlin Heidelberg, 2011. doi:10.1007/978-3-642-23719-5_25.

23 Tim A. Hartmann. Target Set Selection Parameterized by Clique-Width and Maximum Threshold. In SOFSEM 2018: Theory and Practice of Computer Science, pages 137–149. Springer International Publishing, December 2017. doi:10.1007/978-3-319-73117-9_10.

24 David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '03. ACM Press, 2003. doi:10.1145/956750.956769.

25 Dániel Marx. Parameterized graph separation problems. Theoretical Computer Science, 351(3):394–406, February 2006. doi:10.1016/j.tcs.2005.10.007.

26 André Nichterlein, Rolf Niedermeier, Johannes Uhlmann, and Mathias Weller. On tractable cases of Target Set Selection. Social Network Analysis and Mining, 3(2):233–256, May 2012. doi:10.1007/s13278-012-0067-7.

27 D. Peleg. Size bounds for dynamic monopolies. Discrete Applied Mathematics, 86(2-3):263–273, September 1998. doi:10.1016/s0166-218x(98)00043-2.

28 Marcin Pilipczuk and Michał Pilipczuk. Finding a Maximum Induced Degenerate Subgraph Faster Than 2ⁿ. In Parameterized and Exact Computation, pages 3–12. Springer Berlin Heidelberg, 2012. doi:10.1007/978-3-642-33293-7_3.

29 Michał Pilipczuk. Exact Algorithms for Induced Subgraph Problems. In Encyclopedia of Algorithms, pages 1–5. Springer US, 2015. doi:10.1007/978-3-642-27848-8_520-1.

30 Igor Razgon. Computing Minimum Directed Feedback Vertex Set in O*(1.9977ⁿ). In Theoretical Computer Science, pages 70–81. World Scientific, 2007.
# Resolving Conflicts for Lower-Bounded Clustering

## Katrin Casel

Hasso Plattner Institute, University of Potsdam, Potsdam, Germany
Universität Trier, Fachbereich IV - Informatikwissenschaften, Germany
casel@informatik.uni-trier.de

## Abstract

This paper considers the effect of non-metric distances for lower-bounded clustering, i.e., the problem of computing a partition for a given set of objects with pairwise distance, such that each set has a certain minimum cardinality (as required for anonymisation or balanced facility location problems). We discuss lower-bounded clustering with the objective to minimise the maximum radius or diameter of the clusters. For these problems there exists a 2-approximation but only if the pairwise distance on the objects satisfies the triangle inequality, without this property no polynomial-time constant factor approximation is possible, unless P = NP. We try to resolve or at least soften this effect of non-metric distances by devising particular strategies to deal with violations of the triangle inequality (*conflicts*). With parameterised algorithmics, we find that if the number of such conflicts is not too large, constant factor approximations can still be computed efficiently.

In particular, we introduce parameterised approximations with respect to not just the number of conflicts but also for the vertex cover number of the *conflict graph* (graph induced by conflicts). Interestingly, we salvage the approximation ratio of 2 for diameter while for radius it is only possible to show a ratio of 3. For the parameter vertex cover number of the conflict graph this worsening in ratio is shown to be unavoidable, unless FPT = W[2]. We further discuss improvements for diameter by choosing the (induced) $P_3$-cover number of the conflict graph as parameter and complement these by showing that, unless FPT = W[1], there exists no constant factor parameterised approximation with respect to the parameter split vertex deletion set.

**2012 ACM Subject Classification** Theory of computation → Approximation algorithms analysis, Theory of computation → Parameterized complexity and exact algorithms, Theory of computation → Facility location and clustering

**Keywords and phrases** clustering, triangle inequality, parameterised approximation

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

**Acknowledgements** I would like to thank Lorik Dumani for his invaluable help with implementing and testing the algorithms in this paper. This work was supported by the DFG, grant FE 560/6-1.

## 1 Introduction

For most clustering problems, the quality of a solution is usually assessed with respect to a given pairwise distance on the input objects. Approximate solutions for such tasks often rely on this distance to be a metric. But what happens if this property does not hold? Many clustering problems are much more difficult to solve or even approximate if the pairwise distance violates the triangle inequality. The problem **UNCAPACITATED FACILITY LOCATION**, for example, can be approximated with ratio 1.488 if restricted to metric instances, see [20]. For general, possibly non-metric, distances, it is only possible to compute a $log(n)$-approximation; see [18] for one of many algorithms with this performance. The relation to the **SET COVER** problem does not just provide the basis for this positive approximation result,

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

© Katrin Casel;

licensed under Creative Commons License CC-BY

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

Editors: Christophe Paul and Michal Pilipczuk; Article No. 23; pp. 23:1–23:14

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

LIPICS

Leibniz International Proceedings in Informatics

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
# Resolving Conflicts for Lower-Bounded Clustering

## Katrin Casel

Hasso Plattner Institute, University of Potsdam, Potsdam, Germany
Universität Trier, Fachbereich IV - Informatikwissenschaften, Germany
casel@informatik.uni-trier.de

### Abstract

This paper considers the effect of non-metric distances for lower-bounded clustering, i.e., the problem of computing a partition for a given set of objects with pairwise distance, such that each set has a certain minimum cardinality (as required for anonymisation or balanced facility location problems). We discuss lower-bounded clustering with the objective to minimise the maximum radius or diameter of the clusters. For these problems there exists a 2-approximation but only if the pairwise distance on the objects satisfies the triangle inequality, without this property no polynomial-time constant factor approximation is possible, unless P = NP. We try to resolve or at least soften this effect of non-metric distances by devising particular strategies to deal with violations of the triangle inequality (conflicts). With parameterised algorithmics, we find that if the number of such conflicts is not too large, constant factor approximations can still be computed efficiently.

In particular, we introduce parameterised approximations with respect to not just the number of conflicts but also for the vertex cover number of the conflict graph (graph induced by conflicts). Interestingly, we salvage the approximation ratio of 2 for diameter while for radius it is only possible to show a ratio of 3. For the parameter vertex cover number of the conflict graph this worsening in ratio is shown to be unavoidable, unless FPT = W[2]. We further discuss improvements for diameter by choosing the (induced) $P_3$-cover number of the conflict graph as parameter and complement these by showing that, unless FPT = W[1], there exists no constant factor parameterised approximation with respect to the parameter split vertex deletion set.

**2012 ACM Subject Classification** Theory of computation → Approximation algorithms analysis, Theory of computation → Parameterized complexity and exact algorithms, Theory of computation → Facility location and clustering

**Keywords and phrases** clustering, triangle inequality, parameterised approximation

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

**Acknowledgements** I would like to thank Lorik Dumani for his invaluable help with implementing and testing the algorithms in this paper. This work was supported by the DFG, grant FE 560/6-1.

## 1 Introduction

For most clustering problems, the quality of a solution is usually assessed with respect to a given pairwise distance on the input objects. Approximate solutions for such tasks often rely on this distance to be a metric. But what happens if this property does not hold? Many clustering problems are much more difficult to solve or even approximate if the pairwise distance violates the triangle inequality. The problem UNCAPACITATED FACILITY LOCATION, for example, can be approximated with ratio 1.488 if restricted to metric instances, see [20]. For general, possibly non-metric, distances, it is only possible to compute a $log(n)$-approximation; see [18] for one of many algorithms with this performance. The relation to the SET COVER problem does not just provide the basis for this positive approximation result,

<figure><img src="image_118.png" /></figure>
but also transfers non-approximability. In particular, is known that that $log(n)$ is the best approximation ratio for SET COVER by [10], assuming $P \neq NP$, and this hardness transfers to UNCAPACITATED FACILITY LOCATION by a very simple approximation-preserving reduction identifying sets with facilities and the universe with the set of customers.

Such helpful consequences of a restriction to triangle inequality have lead to many approaches which assume that this property holds. Another example of this kind is given in [13], where the properties that come with a restriction to distances which satisfy the triangle inequality are used to speed up the famous heuristic algorithm *k-means*, named after the clustering problem it is designed to approximate efficiently.

For many applications, the requirement that the associated distance is a metric seems to be pretty natural and is not really considered a restriction. For lower-bounded clustering, the problem of computing a partition for a given set of objects with pairwise distance such that each set has a certain minimum cardinality, we also made this assumption in order to enable approximation algorithms with a provable performance ratio, see [1]. In particular, with the objective to minimise the maximum radius or diameter of the clusters, it turned out that, unless $P = NP$, there exists no polynomial-time constant factor approximation if the pairwise distance on the objects violates the triangle inequality while a ratio of 2 can be achieved without such violations. With an attempt to use this problem to model a clustering which can be used for recommender systems, we however found that the pairwise distance does not in general satisfy the triangle inequality. The so-called *Pearson distance*, which is usually used for recommendations, does not have this useful property and, as also observed in [23], practical instances actually show this non-metric behaviour. Such unfortunate situations seem to be unavoidable when it comes to human preferences which raises the question of how the resulting negative effects can be avoided, or at least controlled.

One option that comes to mind concerning non-metric instances in general is editing, i.e., a pre-processing step which tries to transform a given instance, with preferably few changes, such that triangle inequality holds and known algorithms for such well-behaved instances can then be applied. This idea however has several drawbacks. Changes to a given instance always come at the price of distortion; altering distances or even deleting objects results in perturbation of the original input. This effect hence raises the task to find alterations which bring as little change to the original instance as possible. Such editing problems are then usually already difficult to solve themselves. In our specific case of lower-bounded clustering, the task to find a minimum number of vertices such that their removal from a given instance deletes all violations of the triangle inequality is closely related to the 3-hitting set problem. But much more troublesome than the complexity of computing such minimal alterations for these types of problems is the danger of accidentally worsening the optimum value with vertex deletion. Observe that by requiring a lower bound on the cardinality of the clusters, the optimum value is not necessarily monotone, in the sense that a larger set of input objects might enable a better solution.

Here, we therefore seek a different approach which employs extra treatment for violations of the triangle inequality within the approximations designed for metric instances. The basic idea is to investigate the consequences of violations and devise strategies to deal with those within moderate exponential time depending on, roughly speaking, how much the given pairwise distance differs from a metric. More precisely, we will, for a pairwise distance $d$, look at the set of pairs $\{u, v\}$ which directly violate the triangle inequality, i.e., there exists another object $x$ such that $d(u, v) > d(u, x) + d(v, x)$. We call such pairs *conflicts*. If the set of conflicts for a given instance is empty, the associated distance obviously satisfies the triangle inequality, which makes the cardinality of the set of conflicts a reasonable measure
but also transfers non-approximability. In particular, is known that that $log(n)$ is the best approximation ratio for SET COVER by [10], assuming $P \neq NP$, and this hardness transfers to UNCAPACITATED FACILITY LOCATION by a very simple approximation-preserving reduction identifying sets with facilities and the universe with the set of customers.

Such helpful consequences of a restriction to triangle inequality have lead to many approaches which assume that this property holds. Another example of this kind is given in [13], where the properties that come with a restriction to distances which satisfy the triangle inequality are used to speed up the famous heuristic algorithm *k-means*, named after the clustering problem it is designed to approximate efficiently.

For many applications, the requirement that the associated distance is a metric seems to be pretty natural and is not really considered a restriction. For lower-bounded clustering, the problem of computing a partition for a given set of objects with pairwise distance such that each set has a certain minimum cardinality, we also made this assumption in order to enable approximation algorithms with a provable performance ratio, see [1]. In particular, with the objective to minimise the maximum radius or diameter of the clusters, it turned out that, unless $P = NP$, there exists no polynomial-time constant factor approximation if the pairwise distance on the objects violates the triangle inequality while a ratio of 2 can be achieved without such violations. With an attempt to use this problem to model a clustering which can be used for recommender systems, we however found that the pairwise distance does not in general satisfy the triangle inequality. The so-called *Pearson distance*, which is usually used for recommendations, does not have this useful property and, as also observed in [23], practical instances actually show this non-metric behaviour. Such unfortunate situations seem to be unavoidable when it comes to human preferences which raises the question of how the resulting negative effects can be avoided, or at least controlled.

One option that comes to mind concerning non-metric instances in general is editing, i.e., a pre-processing step which tries to transform a given instance, with preferably few changes, such that triangle inequality holds and known algorithms for such well-behaved instances can then be applied. This idea however has several drawbacks. Changes to a given instance always come at the price of distortion; altering distances or even deleting objects results in perturbation of the original input. This effect hence raises the task to find alterations which bring as little change to the original instance as possible. Such editing problems are then usually already difficult to solve themselves. In our specific case of lower-bounded clustering, the task to find a minimum number of vertices such that their removal from a given instance deletes all violations of the triangle inequality is closely related to the 3-hitting set problem. But much more troublesome than the complexity of computing such minimal alterations for these types of problems is the danger of accidentally worsening the optimum value with vertex deletion. Observe that by requiring a lower bound on the cardinality of the clusters, the optimum value is not necessarily monotone, in the sense that a larger set of input objects might enable a better solution.

Here, we therefore seek a different approach which employs extra treatment for violations of the triangle inequality within the approximations designed for metric instances. The basic idea is to investigate the consequences of violations and devise strategies to deal with those within moderate exponential time depending on, roughly speaking, how much the given pairwise distance differs from a metric. More precisely, we will, for a pairwise distance $d$, look at the set of pairs $\{u, v\}$ which directly violate the triangle inequality, i.e., there exists another object $x$ such that $d(u, v) > d(u, x) + d(v, x)$. We call such pairs *conflicts*. If the set of conflicts for a given instance is empty, the associated distance obviously satisfies the triangle inequality, which makes the cardinality of the set of conflicts a reasonable measure
for our purposes. Our strategy then is to alter the algorithms for metric instances in such a
way that they also yield constant-factor approximations for non-metric instances while only
spending exponential effort with respect to the conflicts. Formally, this gives a parameterised
approximation with structural parameterisation by the number of conflicts.

This kind of parameterisation by conflicts to improve approximability can be seen as a
generalisation of the *distance from triviality* approach introduced in [17]. The idea there is to
define some *distance* which specifies how much a given instance differs from some structural
property which makes it easy to solve, and use this measure as parameter. The term *triviality*
there already refers to the broader case of polynomial time solvable instances, not just trivial
inputs as one might think, and in our case we go one step further and see the number of
conflicts as the distance to an instance which can be approximated efficiently.

We discuss conflicts for the problems of minimising the maximum radius or diameter for lower-bounded clustering. We first develop parameterised approximations with respect to conflicts and then improve those to only require exponential time with respect to the vertex cover number of the *conflict graph* $G_c$ (the graph induced by conflicts interpreted as edges). For diameter, we then consider even smaller parameters given by the size of an (induced) $P_3$-cover of $G_c$, but conversely show that the even smaller size of a split vertex deletion set for $G_c$ is not a suitable parameter. Curiously, we find that while the ratio of 2 remains for diameter, it is only possible to prove a ratio of 3 for radius. For the parameter vertex cover of $G_c$, we prove that this worsening is unavoidable under the assumption that FPT ≠ W[2].

## 2 Preliminaries

We mostly use standard notation and refer to textbooks such as [6] for graph theory, [3] for approximation algorithms and [12] for parameterised complexity terminology.

When estimating running times we use $O^*$-notation which, compared to $O$-notation, also suppresses factors which are polynomial in the input size. We use $B_n$ to denote the nth *Bell number* which is the number of partitions of a set of size $n$.

The algorithms discussed here combine parameterisation and approximation and fall into
the category of *fpt-approximation algorithms with parameter $\kappa$, as discussed for example
in [22], i.e., approximation algorithms with provable ratio and running time in $O(g(\kappa) \cdot f(n))$,
for computable function $g$ and polynomial $f$, so $O^*(g(\kappa))$ in $O^*$-notation. For lower bounds
in this context, there does not seem to exist a unified notation, so for these kinds of results, we
will not use hardness notions but link the existence of certain parameterised approximations
to the (unlikely) equivalence of certain complexity classes.

## 2.1 Problem Definition

As formal model for lower-bounded clustering we use the abstract problem ($\|\cdot\|$, $f$)-*k*-CLUSTER from [1]. An instance of this problem is an undirected graph $G = (V, E)$ with edge-weights $w_E: E \to \mathbb{R}_+$ and a lower bound $k \in \mathbb{N}$. A feasible solution is any partition $P_1, \dots, P_s$ of $V$ such that $|P_i| \ge k$ for all $i \in \{1, \dots, s\}$, we refer to such a partition as *k-cluster*.

For two vertices $u, v \in V$ with $u \neq v$ we define $d(u, v) := w_E(\{u, v\})$ if $\{u, v\} \in E$, and if $\{u, v\} \notin E$, the distance $d(u, v)$ is defined by the shortest path from $u$ to $v$ in $G$. For simplicity we always extend $d$ to a function on the whole set $V \times V$ by defining $d(v, v) = 0$ for all $v \in V$. This definition of the *induced distance* $d$ derived from weights only known for a set $E$ of given edges models missing information about pairwise distances.

For the objectives to minimise maximum radius or diameter we formally define $\text{rad}(P) := \min\{\max\{d(x, y): y \in P\}: x \in P\}$ and $\text{diam}(P) := \max\{\max\{d(x, y): y \in P\}: x \in P\}$. The
for our purposes. Our strategy then is to alter the algorithms for metric instances in such a
way that they also yield constant-factor approximations for non-metric instances while only
spending exponential effort with respect to the conflicts. Formally, this gives a parameterised
approximation with structural parameterisation by the number of conflicts.

This kind of parameterisation by conflicts to improve approximability can be seen as a
generalisation of the *distance from triviality* approach introduced in [17]. The idea there is to
define some *distance* which specifies how much a given instance differs from some structural
property which makes it easy to solve, and use this measure as parameter. The term *triviality*
there already refers to the broader case of polynomial time solvable instances, not just trivial
inputs as one might think, and in our case we go one step further and see the number of
conflicts as the distance to an instance which can be approximated efficiently.

We discuss conflicts for the problems of minimising the maximum radius or diameter for lower-bounded clustering. We first develop parameterised approximations with respect to conflicts and then improve those to only require exponential time with respect to the vertex cover number of the *conflict graph* $G_c$ (the graph induced by conflicts interpreted as edges). For diameter, we then consider even smaller parameters given by the size of an (induced) $P_3$-cover of $G_c$, but conversely show that the even smaller size of a split vertex deletion set for $G_c$ is not a suitable parameter. Curiously, we find that while the ratio of 2 remains for diameter, it is only possible to prove a ratio of 3 for radius. For the parameter vertex cover of $G_c$, we prove that this worsening is unavoidable under the assumption that FPT ≠ W[2].

## 2 Preliminaries

We mostly use standard notation and refer to textbooks such as [6] for graph theory, [3] for approximation algorithms and [12] for parameterised complexity terminology.

When estimating running times we use $O^*$-notation which, compared to $O$-notation, also suppresses factors which are polynomial in the input size. We use $B_n$ to denote the nth *Bell number* which is the number of partitions of a set of size $n$.

The algorithms discussed here combine parameterisation and approximation and fall into
the category of *fpt-approximation algorithms with parameter $\kappa$, as discussed for example
in [22], i.e., approximation algorithms with provable ratio and running time in $O(g(\kappa) \cdot f(n))$,
for computable function $g$ and polynomial $f$, so $O^*(g(\kappa))$ in $O^*$-notation. For lower bounds
in this context, there does not seem to exist a unified notation, so for these kinds of results, we
will not use hardness notions but link the existence of certain parameterised approximations
to the (unlikely) equivalence of certain complexity classes.

## 2.1 Problem Definition

As formal model for lower-bounded clustering we use the abstract problem ($\|\cdot\|$, $f$)-*k*-CLUSTER from [1]. An instance of this problem is an undirected graph $G = (V, E)$ with edge-weights $w_E: E \to \mathbb{R}_+$ and a lower bound $k \in \mathbb{N}$. A feasible solution is any partition $P_1, \dots, P_s$ of $V$ such that $|P_i| \ge k$ for all $i \in \{1, \dots, s\}$, we refer to such a partition as *k-cluster*.

For two vertices $u, v \in V$ with $u \neq v$ we define $d(u, v) := w_E(\{u, v\})$ if $\{u, v\} \in E$, and if $\{u, v\} \notin E$, the distance $d(u, v)$ is defined by the shortest path from $u$ to $v$ in $G$. For simplicity we always extend $d$ to a function on the whole set $V \times V$ by defining $d(v, v) = 0$ for all $v \in V$. This definition of the *induced distance* $d$ derived from weights only known for a set $E$ of given edges models missing information about pairwise distances.

For the objectives to minimise maximum radius or diameter we formally define $\text{rad}(P) := \min\{\max\{d(x, y): y \in P\}: x \in P\}$ and $\text{diam}(P) := \max\{\max\{d(x, y): y \in P\}: x \in P\}$. The
<figure><img src="image_118.png" /><figcaption>Figure 1 In the graph on the left, {$c, d$} has a weight larger than the shortest path from $c$ to $d$ but is not in $C$. Lowering the weights on {$a, d$} and {$b, c$} to 2 to remove these conflicts turns {$c, d$} into a conflict. The graph on the right has a 2-cluster of maximum radius and diameter 1. Removing $a$ to delete conflicts results in a graph for which only a trivial 2-cluster of radius $\Delta$ is possible.</figcaption></figure>

resulting problems ($\|\cdot\|_{\infty}$, rad)-k-CLUSTER and ($\|\cdot\|_{\infty}$, diam)-k-CLUSTER ask for a k-cluster $P_1, \dots, P_s$ minimising $\max\{\mathrm{rad}(P_i): 1 \le i \le s\}$ and $\max\{\mathrm{diam}(P_i): 1 \le i \le s\}$, respectively. A vertex $x \in V$ with $\max\{d(x, y): y \in P\} = \mathrm{rad}(P)$ is called central for $P$.

## 2.2 Conflicts

A function $d: V \times V \to \mathbb{R}^+$ satisfies the *triangle inequality* if $d(u, v) \le d(u, w) + d(w, v)$ for all $u, v, w \in V$. We will call an instance of ($\|\cdot\|$, $f$)-k-CLUSTER *metric* if the induced distance satisfies the triangle inequality although this does not necessarily make $d$ a metric in the classical definition of this word, as we allow the existence of $u \ne v$ with $d(u, v) = 0$ (violation of the so-called *identity of indiscernibles* property of metrics); recall that by the formal definition, $d$ derived from edge-weights is just non-negative, symmetric and reflexive.

Observe that our definition allows non-metric instances, see Figure 1. We define the set of *conflicts* for an instance $(G, k)$ with $G = (V, E)$ and induced distance $d$ as the collection $C$ of vertex pairs $\{u, v\}$ such that the triangle inequality is violated for $u$ and $v$, formally:

$$C = \{\{u, v\} \in V \times V: \exists x \in V: d(u, v) > d(u, x) + d(v, x)\}.$$

One curious property is that the set of conflicts is not necessarily the whole set of edges with a weight larger than the cheapest path in the graph (for a counterexample see Figure 1), it however is always a subset of $E$. Considering the option of weight reduction to achieve triangle inequality, $C$ might be smaller than the set of edge-weights which have to be adjusted in order to arrive at a graph without conflicts. Figure 1 also gives a small example which illustrates why vertex removal can be a dangerous editing step for problems with non-monotone objective function such as lower bounded clustering. Observe how the optimum value may increase arbitrarily from the original graph to a graph created by deleting vertices to avoid conflicts. This effect is another reason to favour parameterisation over editing.

Actually, we will mostly consider parameterisation by the cardinality of the set $P$ of *conflict vertices*, which simply are the vertices involved in a conflict, formally defined by:

$$P = \bigcup_{\{u,v\} \in C} \{u, v\}.$$

In the following we will use $c$ and $p$ for the parameters number of conflicts and number of conflict vertices, respectively. Parameterisation by $p$ yields the same general tractability as parameterisation by $p$ as the parameters are related by the inequalities $p \le 2c \le (p(p-1))$. For the concrete running times, it is however still relevant to distinguish between $p$ and $c$ as the bounds given by this inequality are sharp.

We further refer to the graph $G_c = (P, C)$ as *conflict graph*; observe that $G_c$ is always a subgraph of the input graph. The structure of the conflict graph reflects the entanglement
<figure><img src="image_119.png" /><figcaption>Figure 1 In the graph on the left, {$c, d$} has a weight larger than the shortest path from $c$ to $d$ but is not in $C$. Lowering the weights on {$a, d$} and {$b, c$} to 2 to remove these conflicts turns {$c, d$} into a conflict. The graph on the right has a 2-cluster of maximum radius and diameter 1. Removing $a$ to delete conflicts results in a graph for which only a trivial 2-cluster of radius $\Delta$ is possible.</figcaption></figure>

resulting problems ($\|\cdot\|_{\infty}$, rad)-k-CLUSTER and ($\|\cdot\|_{\infty}$, diam)-k-CLUSTER ask for a k-cluster $P_1, \dots, P_s$ minimising $\max\{\mathrm{rad}(P_i): 1 \le i \le s\}$ and $\max\{\mathrm{diam}(P_i): 1 \le i \le s\}$, respectively. A vertex $x \in V$ with $\max\{d(x, y): y \in P\} = \mathrm{rad}(P)$ is called central for $P$.

## 2.2 Conflicts

A function $d: V \times V \to \mathbb{R}^+$ satisfies the *triangle inequality* if $d(u, v) \le d(u, w) + d(w, v)$ for all $u, v, w \in V$. We will call an instance of ($\|\cdot\|$, $f$)-k-CLUSTER *metric* if the induced distance satisfies the triangle inequality although this does not necessarily make $d$ a metric in the classical definition of this word, as we allow the existence of $u \ne v$ with $d(u, v) = 0$ (violation of the so-called *identity of indiscernibles* property of metrics); recall that by the formal definition, $d$ derived from edge-weights is just non-negative, symmetric and reflexive.

Observe that our definition allows non-metric instances, see Figure 1. We define the set of *conflicts* for an instance $(G, k)$ with $G = (V, E)$ and induced distance $d$ as the collection $C$ of vertex pairs {$u, v$} such that the triangle inequality is violated for $u$ and $v$, formally:

$$C = \{\{u, v\} \in V \times V: \exists x \in V: d(u, v) > d(u, x) + d(v, x)\}.$$

One curious property is that the set of conflicts is not necessarily the whole set of edges with a weight larger than the cheapest path in the graph (for a counterexample see Figure 1), it however is always a subset of $E$. Considering the option of weight reduction to achieve triangle inequality, $C$ might be smaller than the set of edge-weights which have to be adjusted in order to arrive at a graph without conflicts. Figure 1 also gives a small example which illustrates why vertex removal can be a dangerous editing step for problems with non-monotone objective function such as lower bounded clustering. Observe how the optimum value may increase arbitrarily from the original graph to a graph created by deleting vertices to avoid conflicts. This effect is another reason to favour parameterisation over editing.

Actually, we will mostly consider parameterisation by the cardinality of the set $P$ of *conflict vertices*, which simply are the vertices involved in a conflict, formally defined by:

$$P = \bigcup_{\{u,v\} \in C} \{u, v\}.$$

In the following we will use $c$ and $p$ for the parameters number of conflicts and number of conflict vertices, respectively. Parameterisation by $p$ yields the same general tractability as parameterisation by $p$ as the parameters are related by the inequalities $p \le 2c \le (p(p-1))$. For the concrete running times, it is however still relevant to distinguish between $p$ and $c$ as the bounds given by this inequality are sharp.

We further refer to the graph $G_c = (P, C)$ as *conflict graph*; observe that $G_c$ is always a subgraph of the input graph. The structure of the conflict graph reflects the entanglement
of conflicts in a given instance. When designing algorithms which devise specific strategies
to resolve conflicts, it is not surprising that the relations between these can be exploited
for improvement. The structure of the conflict graph hence yields further possibilities for a
parameterisation which measures the distance to a metric instance.

3 Parameterisation by Conflict Vertices

Without restriction to metric instances, there exists no constant factor approximation in poly-
nomial time for (||·||_∞, rad)- or (||·||_∞, diam)-k-CLUSTER, unless P = NP (see Proposition 6
from [1]). The 2-approximation presented for these problems in [1], Theorem 9 hence highly
relies on the assumption that the input instance is metric. In short, on input ((V, E), w_E, k)
with induced distance d, the approximation algorithm with the performance ratio of 2 for
both (||·||_∞, rad)- and (||·||_∞, diam)-k-CLUSTER simply performs a binary search for the
smallest value D for which the following 2-step greedy procedure is successful:

step (1) While V is not empty, pick some $c \in V$, build the set $P(c) := \{w \in V : d(c, w) \le D\}$ and set $V = V \setminus P(c)$.

step (2) Let $P(c_1), \dots, P(c_s)$ be the partition built in step (1). Try to create from this a $k$-cluster $P'(c_1), \dots, P'(c_s)$ such that $c_i \in P'(c_i)$ and $d(v, c_i) \le D$ for all $v \in P'(c_i)$, $i \in \{1, \dots, s\}$. (Such a partition can be efficiently computed with the help of a network flow formulation over vertices $V \cup \{s, t\}$. With arcs of capacity 1 from $s$ to every $v \in V$, arcs of capacity $k$ from $c_i$ to $t$ and arcs of capacity 1 from $v \in V$ to $c_i$ if $d(v, c_i) \le D$ for each $i \in \{1, \dots, s\}$. A flow of value $sk$ in this network interpreted as moving a vertex $v \in P(c_i)$ into the set $P(c_j)$ if and only if the flow uses the arc from $v$ to $c_j$, gives a polynomial procedure to create a $k$-cluster.)

The ratio of 2 for (||·||_∞, rad)- and (||·||_∞, diam)-k-CLUSTER can be shown by proving that the greedy procedure is successful if D is fixed to be twice the optimum radius or the optimum diameter, respectively, which is due to the following two properties for this choice of D:

(i) By the choice of the vertices $c_i$ in step (1), it follows that $d(c_i, c_j) > D$ for all $i \neq j$, which means that $c_i$ and $c_j$ belong to different sets in an optimum solution. So, for each $i$ there exist enough vertices at distance at most $D$ from $c_i$ to be put into $P'(c_i)$ in step (2).

(ii) If the greedy procedure is successful, the construction immediately yields $d(v, c_i) \le D$ for each $v \in P'(c_i)$, so the resulting $k$-cluster $P'(c_1), \dots, P'(c_s)$ has maximum radius $D$ and maximum diameter $2D$.

The above properties however do not hold in case the input instance is not metric. More
precisely, for each objective function (radius, diameter), one of them is no longer true. For
radius, property (i) fails, as without triangle inequality, vertices at distance more than twice
the optimum can still be contained in the same cluster in an optimum solution. For diameter,
property (ii) fails, as a radius of D does no longer guarantee a diameter of 2D.

We will now try to salvage these properties for non-metric instances by adding exponential
effort with respect to conflicts to the above approximation procedure. Given that different
properties are lost for the two objective functions, it is not surprising that this approach
yields two different parameterised approximations, the basic algorithmic idea of fixing a
maximum radius D, building a preliminary clustering with clusters of radius D and then
balancing the cardinalities with a network however always remains and we will only sketch
the crucial points which have to be adjusted in each case.

At first, we observe that starting from the approximation algorithm for metric instances,
it is not too hard to see that a constant number of conflicts does not yield too much trouble.
More precisely, we simply guess a suitable central vertex for each conflict vertex and fix the
of conflicts in a given instance. When designing algorithms which devise specific strategies to resolve conflicts, it is not surprising that the relations between these can be exploited for improvement. The structure of the conflict graph hence yields further possibilities for a parameterisation which measures the distance to a metric instance.

## 3 Parameterisation by Conflict Vertices

Without restriction to metric instances, there exists no constant factor approximation in polynomial time for $(\|\cdot\|_{\infty}, \text{rad})$- or $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER, unless $P = \text{NP}$ (see Proposition 6 from [1]). The 2-approximation presented for these problems in [1], Theorem 9 hence highly relies on the assumption that the input instance is metric. In short, on input $((V, E), w_E, k)$ with induced distance $d$, the approximation algorithm with the performance ratio of 2 for both $(\|\cdot\|_{\infty}, \text{rad})$- and $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER simply performs a binary search for the smallest value $D$ for which the following 2-step greedy procedure is successful:

**step (1)** While $V$ is not empty, pick some $c \in V$, build the set $P(c) := \{w \in V : d(c, w) \le D\}$ and set $V = V \setminus P(c)$.

**step (2)** Let $P(c_1), \dots, P(c_s)$ be the partition built in step (1). Try to create from this a k-cluster $P'(c_1), \dots, P'(c_s)$ such that $c_i \in P'(c_i)$ and $d(v, c_i) \le D$ for all $v \in P'(c_i)$, $i \in \{1, \dots, s\}$. (Such a partition can be efficiently computed with the help of a network flow formulation over vertices $V \cup \{s, t\}$. With arcs of capacity 1 from $s$ to every $v \in V$, arcs of capacity $k$ from $c_i$ to $t$ and arcs of capacity 1 from $v \in V$ to $c_i$ if $d(v, c_i) \le D$ for each $i \in \{1, \dots, s\}$. A flow of value $sk$ in this network interpreted as moving a vertex $v \in P(c_i)$ into the set $P(c_j)$ if and only if the flow uses the arc from $v$ to $c_j$, gives a polynomial procedure to create a k-cluster.)

The ratio of 2 for $(\|\cdot\|_{\infty}, \text{rad})$- and $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER can be shown by proving that the greedy procedure is successful if $D$ is fixed to be twice the optimum radius or the optimum diameter, respectively, which is due to the following two properties for this choice of $D$:

(i) By the choice of the vertices $c_i$ in step (1), it follows that $d(c_i, c_j) > D$ for all $i \neq j$, which means that $c_i$ and $c_j$ belong to different sets in an optimum solution. So, for each $i$ there exist enough vertices at distance at most $D$ from $c_i$ to be put into $P'(c_i)$ in step (2).

(ii) If the greedy procedure is successful, the construction immediately yields $d(v, c_i) \le D$ for each $v \in P'(c_i)$, so the resulting k-cluster $P'(c_1), \dots, P'(c_s)$ has maximum radius $D$ and maximum diameter $2D$.

The above properties however do not hold in case the input instance is not metric. More precisely, for each objective function (radius, diameter), one of them is no longer true. For radius, property (i) fails, as without triangle inequality, vertices at distance more than twice the optimum can still be contained in the same cluster in an optimum solution. For diameter, property (ii) fails, as a radius of $D$ does no longer guarantee a diameter of $2D$.

We will now try to salvage these properties for non-metric instances by adding exponential effort with respect to conflicts to the above approximation procedure. Given that different properties are lost for the two objective functions, it is not surprising that this approach yields two different parameterised approximations, the basic algorithmic idea of fixing a maximum radius $D$, building a preliminary clustering with clusters of radius $D$ and then balancing the cardinalities with a network however always remains and we will only sketch the crucial points which have to be adjusted in each case.

At first, we observe that starting from the approximation algorithm for metric instances, it is not too hard to see that a constant number of conflicts does not yield too much trouble. More precisely, we simply guess a suitable central vertex for each conflict vertex and fix the
resulting partition of $P$ and centres for step (1). This optimal guessing for the problematic vertices resolves the problems for both objective functions, as the fixed centres are optimal by choice and the greedy algorithm is only responsible for partitioning remaining vertices in $V \setminus P$ for which the triangle inequality holds. This kind of guessing yields:

**Theorem 1.** A 2-approximation for ($\|\cdot\|_{\infty}$, rad)- and ($\|\cdot\|_{\infty}$, diam)-*k*-CLUSTER can be computed with a running time in $O^*(n^p)$.

This result raises the question whether an improvement to a more efficient running time is possible, i.e., some constant factor parameterised approximation. To this end, we want to mention that an improvement of the approximation ratio of 2 is unlikely, as this is already shown to imply $P = NP$ for metric instances in [1], Corollaries 1 and 3.

For diameter, we have to only be careful with property (ii) which means that in the above guessing, we did not really require the knowledge of centres but only the partition they imply on the vertices in $P$. In fact, it can be shown that knowing this partition is enough, and simply enforcing it in the metric approximation algorithm still yields a 2-approximation for ($\|\cdot\|_{\infty}$, diam)-*k*-CLUSTER. The cost of trying all partitions of $P$ can be estimated with the Bell number (which can be bounded by $B_n < \left( \frac{0.792n}{\log(n+1)} \right)^n$, see [5]) and yields:

**Theorem 2.** A 2-approximation for ($\|\cdot\|_{\infty}$, diam)-*k*-CLUSTER can be computed with a running time in $O^*(B_p)$.

For radius, the fixed centres are important, but by compromising a little on the approximation ratio it is still possible to design a parameterised approximation with parameter $p$. This algorithm only requires guessing which vertices in $P$ are central in an optimal solution and accordingly forcing step (1) to build clusters around those first; observe that this knowledge salvages property (i). Picking a suitable cluster for the vertices in $P$ which are not chosen to be central however blows up the approximation ratio to 3 (an effect which is explained later in connection to the lower bounds), which yields:

**Theorem 3.** A 3-approximation for ($\|\cdot\|_{\infty}$, rad)-*k*-CLUSTER can be computed with a running time in $O^*(2^p)$.

# 4 Structural Parameters of the Conflict Graph

One possibility to speed up the parameterised approximation algorithms presented so far, is to choose a smaller parameter. In this section, we want to focus on strategies to only spend exponential time for vertices in a subset of $P$. More precisely, as advertised in the section-title, we will consider parameterisation by structural parameters of the conflict graph.

## 4.1 Vertex Cover

Looking closer at the problems caused by the conflicts in $C$, it is not necessary to consider all vertices in $P$ but it appears to be sufficient to pick a subset which covers all conflicts. Formally, this idea translates into parameterisation by a vertex cover for the conflict graph $G_c = (P, C)$. In the following, we will use $p_c$ to denote the size of a minimum vertex cover for $G_c$ and discuss parameterised approximation with respect to this parameter.

Again, a first easy observation is that, at least for ($\|\cdot\|_{\infty}$, rad)-*k*-CLUSTER, instances for which $p_c$ is a constant can be approximated efficiently. In fact, we can simply switch from the set $P$ to a minimum vertex cover for $G_c$ in the procedure discussed for Theorem 1, as property (i) can only be violated if the algorithm can choose two vertices of a conflict as centres. The additionally required computing of a constant size vertex cover for $G_c$ is not an expensive task, so this idea immediately yields:
resulting partition of $P$ and centres for step (1). This optimal guessing for the problematic vertices resolves the problems for both objective functions, as the fixed centres are optimal by choice and the greedy algorithm is only responsible for partitioning remaining vertices in $V \setminus P$ for which the triangle inequality holds. This kind of guessing yields:

**Theorem 1.** A 2-approximation for ($\|\cdot\|_{\infty}$, rad)- and ($\|\cdot\|_{\infty}$, diam)-*k*-CLUSTER can be computed with a running time in $O^*(n^p)$.

This result raises the question whether an improvement to a more efficient running time is possible, i.e., some constant factor parameterised approximation. To this end, we want to mention that an improvement of the approximation ratio of 2 is unlikely, as this is already shown to imply $P = NP$ for metric instances in [1], Corollaries 1 and 3.

For diameter, we have to only be careful with property (ii) which means that in the above guessing, we did not really require the knowledge of centres but only the partition they imply on the vertices in $P$. In fact, it can be shown that knowing this partition is enough, and simply enforcing it in the metric approximation algorithm still yields a 2-approximation for ($\|\cdot\|_{\infty}$, diam)-*k*-CLUSTER. The cost of trying all partitions of $P$ can be estimated with the Bell number (which can be bounded by $B_n < \left( \frac{0.792n}{\log(n+1)} \right)^n$, see [5]) and yields:

**Theorem 2.** A 2-approximation for ($\|\cdot\|_{\infty}$, diam)-*k*-CLUSTER can be computed with a running time in $O^*(B_p)$.

For radius, the fixed centres are important, but by compromising a little on the approximation ratio it is still possible to design a parameterised approximation with parameter $p$. This algorithm only requires guessing which vertices in $P$ are central in an optimal solution and accordingly forcing step (1) to build clusters around those first; observe that this knowledge salvages property (i). Picking a suitable cluster for the vertices in $P$ which are not chosen to be central however blows up the approximation ratio to 3 (an effect which is explained later in connection to the lower bounds), which yields:

**Theorem 3.** A 3-approximation for ($\|\cdot\|_{\infty}$, rad)-*k*-CLUSTER can be computed with a running time in $O^*(2^p)$.

# 4 Structural Parameters of the Conflict Graph

One possibility to speed up the parameterised approximation algorithms presented so far, is to choose a smaller parameter. In this section, we want to focus on strategies to only spend exponential time for vertices in a subset of $P$. More precisely, as advertised in the section-title, we will consider parameterisation by structural parameters of the conflict graph.

## 4.1 Vertex Cover

Looking closer at the problems caused by the conflicts in $C$, it is not necessary to consider all vertices in $P$ but it appears to be sufficient to pick a subset which covers all conflicts. Formally, this idea translates into parameterisation by a vertex cover for the conflict graph $G_c = (P, C)$. In the following, we will use $p_c$ to denote the size of a minimum vertex cover for $G_c$ and discuss parameterised approximation with respect to this parameter.

Again, a first easy observation is that, at least for ($\|\cdot\|_{\infty}$, rad)-*k*-CLUSTER, instances for which $p_c$ is a constant can be approximated efficiently. In fact, we can simply switch from the set $P$ to a minimum vertex cover for $G_c$ in the procedure discussed for Theorem 1, as property (i) can only be violated if the algorithm can choose two vertices of a conflict as centres. The additionally required computing of a constant size vertex cover for $G_c$ is not an expensive task, so this idea immediately yields:
**► Theorem 4.** *A 2-approximation for ($\|\cdot\|_{\infty}$, rad)-k-CLUSTER can be computed with a running time in $O^*(n^{p_c})$.*

The parameterised approximation for ($\|\cdot\|_{\infty}$, diam)-k-CLUSTER from Section 3 requires little algorithmic adjustment to switch from parameter $p$ to parameter $p_c$. Proving correctness of the given procedure, i.e., guaranteeing a performance ratio, is however more complicated.

Consider only guessing a partition of a vertex cover $\mathcal{V}$ of the conflict graph and fixing this partition for step (1). The only further change required to make sure that property (ii) remains true, is to adjust the algorithm when building clusters including the guessed sets $V_1, \dots, V_t$ in the partition of $\mathcal{V}$. Now, both when building the preliminary clusters including some $V_i$ in step (1) and moving vertices in step (2) into such a cluster, we not just require a distance of at most $D$ to one chosen centre but to all vertices in $V_i$. Then all distances in a set of the resulting $k$-cluster involving vertices in the cover $\mathcal{V}$ are bounded by $D$. As $\mathcal{V}$ is a vertex cover of $G_c$, distances not involving a vertex in $\mathcal{V}$ are not a conflict which means triangle inequality can be used for all remaining cases to prove that property (ii) still holds.

This approach requires computing a vertex cover for the conflict graph, a problem which can be solved by [9] with a running time in $O^*(1.2738^{p_c})$. As this single-exponential effort is only performed once in the beginning and dominated by the Bell number, we can conclude:

**► Theorem 5.** *A 2-approximation for ($\|\cdot\|_{\infty}$, diam)-k-CLUSTER can be computed with a running time in $O^*(B_{p_c})$.*

For ($\|\cdot\|_{\infty}$, rad)-k-CLUSTER, it is not obvious how to reduce $p$ in Theorem 3 to $p_c$. While knowing which vertices in a vertex cover are central is sufficient to avoid picking centres from the same cluster in step (1), the problem is finding a suitable cluster for the vertices from the vertex cover which are not central. In particular, this is a problem when two vertices from the vertex cover which are not central are wrongfully put in the same cluster; more precisely, if two vertices $u, v \in \mathcal{V}$ are not central in any optimal solution but belong to two different clusters, with centres $c_u, c_v \notin \mathcal{V}$, while these two correct centres are put into $P(c)$ with $\{u, c\}, \{v, c\} \in C$ in step (1) of our algorithm. In such a case there is no general clean way to identify how to split up $P(c)$ into sets of cardinality at least $k$ and such that $u$ and $v$ can be assigned at a radius which can in any way be bounded by the optimum.

With a more involved algorithm which additionally guesses a partition, like for the diameter measure, it is possible to find an approximation for ($\|\cdot\|_{\infty}$, rad)-k-CLUSTER parameterised by $p_c$. After guessing a partition and a set of centres for the vertex cover, this approach further requires computing a suitable centre for each set in the partition before running steps (1) and (2), which are altered to respect the fixed partition and central vertices. This just means finding for each set $V_i$ in the partition of the vertex cover $\mathcal{V}$ for which no vertex in $V_i$ is fixed as center, a vertex $v \in V \setminus \mathcal{V}$ such that $d(v, w) \le \frac{D}{2}$ for all $w \in V_i$ (where $\frac{D}{2}$ relates to the optimum radius). As two sets $V_i$ and $V_j$ might compete over such candidates for centres, we use maximum matching to enable finding, in case our fixed guesses are correct, a centre for each set $V_i$. These adjustments are sufficient to salvage property (i). Although now there is no longer the problem of finding a suitable cluster for vertices which are not allowed to be central, the performance ratio is still only 3, as for this procedure the worst-case now comes from choosing a wrong center $c' \in V \setminus \mathcal{V}$ for some $V_i$: If $P \subseteq V$ is the cluster containing $V_i$ in an optimum solution and $c$ is its correct center, it follows that the distance of $v \in P$ to the wrong center $c'$ can only be bounded by $d(v, c') \le d(v, c) + d(c, c') \le \frac{D}{2} + d(c, v_i) + d(c', v_i) \le 3\frac{D}{2}$ (using some $v_i \in V_i$ for this equation). The asymptotic running time of this approach is dominated by guessing the partition and centre-choice for a minimum vertex cover of $G_c$, so:
**► Theorem 4.** *A 2-approximation for ($\|\cdot\|_{\infty}$, rad)-k-CLUSTER can be computed with a running time in $O^*(n^{p_c})$.*

The parameterised approximation for ($\|\cdot\|_{\infty}$, diam)-k-CLUSTER from Section 3 requires little algorithmic adjustment to switch from parameter $p$ to parameter $p_c$. Proving correctness of the given procedure, i.e., guaranteeing a performance ratio, is however more complicated.

Consider only guessing a partition of a vertex cover $\mathcal{V}$ of the conflict graph and fixing this partition for step (1). The only further change required to make sure that property (ii) remains true, is to adjust the algorithm when building clusters including the guessed sets $V_1, \dots, V_t$ in the partition of $\mathcal{V}$. Now, both when building the preliminary clusters including some $V_i$ in step (1) and moving vertices in step (2) into such a cluster, we not just require a distance of at most $D$ to one chosen centre but to all vertices in $V_i$. Then all distances in a set of the resulting $k$-cluster involving vertices in the cover $\mathcal{V}$ are bounded by $D$. As $\mathcal{V}$ is a vertex cover of $G_c$, distances not involving a vertex in $\mathcal{V}$ are not a conflict which means triangle inequality can be used for all remaining cases to prove that property (ii) still holds.

This approach requires computing a vertex cover for the conflict graph, a problem which can be solved by [9] with a running time in $O^*(1.2738^{p_c})$. As this single-exponential effort is only performed once in the beginning and dominated by the Bell number, we can conclude:

**► Theorem 5.** *A 2-approximation for ($\|\cdot\|_{\infty}$, diam)-k-CLUSTER can be computed with a running time in $O^*(B_{p_c})$.*

For ($\|\cdot\|_{\infty}$, rad)-k-CLUSTER, it is not obvious how to reduce $p$ in Theorem 3 to $p_c$. While knowing which vertices in a vertex cover are central is sufficient to avoid picking centres from the same cluster in step (1), the problem is finding a suitable cluster for the vertices from the vertex cover which are not central. In particular, this is a problem when two vertices from the vertex cover which are not central are wrongfully put in the same cluster; more precisely, if two vertices $u, v \in \mathcal{V}$ are not central in any optimal solution but belong to two different clusters, with centres $c_u, c_v \notin \mathcal{V}$, while these two correct centres are put into $P(c)$ with $\{u, c\}, \{v, c\} \in C$ in step (1) of our algorithm. In such a case there is no general clean way to identify how to split up $P(c)$ into sets of cardinality at least $k$ and such that $u$ and $v$ can be assigned at a radius which can in any way be bounded by the optimum.

With a more involved algorithm which additionally guesses a partition, like for the diameter measure, it is possible to find an approximation for ($\|\cdot\|_{\infty}$, rad)-k-CLUSTER parameterised by $p_c$. After guessing a partition and a set of centres for the vertex cover, this approach further requires computing a suitable centre for each set in the partition before running steps (1) and (2), which are altered to respect the fixed partition and central vertices. This just means finding for each set $V_i$ in the partition of the vertex cover $\mathcal{V}$ for which no vertex in $V_i$ is fixed as center, a vertex $v \in V \setminus \mathcal{V}$ such that $d(v, w) \le \frac{D}{2}$ for all $w \in V_i$ (where $\frac{D}{2}$ relates to the optimum radius). As two sets $V_i$ and $V_j$ might compete over such candidates for centres, we use maximum matching to enable finding, in case our fixed guesses are correct, a centre for each set $V_i$. These adjustments are sufficient to salvage property (i). Although now there is no longer the problem of finding a suitable cluster for vertices which are not allowed to be central, the performance ratio is still only 3, as for this procedure the worst-case now comes from choosing a wrong center $c' \in V \setminus \mathcal{V}$ for some $V_i$: If $P \subseteq V$ is the cluster containing $V_i$ in an optimum solution and $c$ is its correct center, it follows that the distance of $v \in P$ to the wrong center $c'$ can only be bounded by $d(v, c') \le d(v, c) + d(c, c') \le \frac{D}{2} + d(c, v_i) + d(c', v_i) \le 3\frac{D}{2}$ (using some $v_i \in V_i$ for this equation). The asymptotic running time of this approach is dominated by guessing the partition and centre-choice for a minimum vertex cover of $G_c$, so:
**► Theorem 6.** A 3-approximation for $(\|\cdot\|_{\infty}, \text{rad})$-k-CLUSTER can be computed with a running time in $O^*(2^{p_c} \cdot B_{p_c})$.

## 4.2 $P_3$-Covers

With more changes to the algorithms discussed for $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER, it is possible to further reduce the size of the subset of $P$ which requires the expensive guessing of the partition. When building the first partition in step (1), it is always possible to correctly assign conflict vertices to a set, by branching on the conflicts to decide which vertex has to be excluded. This way it is possible to find a correct choice of central vertices. The network used to model the reassignment of vertices according to the fixed centres can be altered to prevent two conflict vertices to move into the same cluster, by routing their flow through an additional network-vertex with a capacity of only 1 to move into a cluster. If the conflicts are isolated, an additional network-vertex for each conflict can be used to correctly model all conflict-free reassignments.

We can of course not assume that conflicts are pairwise disjoint, but we can fix the partition of a subset of conflict vertices, as we did for the vertex cover of the conflict graph, and use the above ideas for the remaining vertices which induce a graph with isolated conflicts. The set of vertices which have to be removed in order to arrive at a graph with isolated edges, or equivalently a graph which does not contain any path of length 2 usually denoted $P_3$, is smaller than the vertex cover of the conflict graph (unless the instance is initially metric). Formally, such a set is called a *$P_3$-cover*. In the following, we use $p_{3c}$ to denote the cardinality of a smallest $P_3$-cover for $G_c$ and with the parameterised algorithm from [24], such a set can be computed with a running time in $O^*(1.7485^{p_{3c}})$. Using the more expensive strategy of guessing the correct partition only for a minimum $P_3$-cover of the conflict graph computed with the algorithm in [24], branching on the remaining isolated conflicts for the pre-clustering and modifying the network to avoid conflicts as described above gives the following result; observe that the number of remaining conflicts is bounded by $\frac{p}{2}$:

**► Theorem 7.** A 2-approximation for $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER can be computed with a running time in $O^*(\sqrt{2^p} \cdot B_{p_{3c}})$.

As already mentioned, branching on conflicts in step (1) works for any set of conflicts, not just for the restriction to isolated ones. The reassignment restriction for conflict vertices modelled with the capacities in the network however requires a situation where, in case of conflict, at most one vertex can be moved into a cluster. Capacities on arcs from some additional network-vertices which handle conflicts, can not model a scenario where out of three vertices $u, v, w$, a cluster is restricted to either only contain $u$ or any subset of $\{v, w\}$; this situation occurs if $u$ is in conflict with $v$ and $w$ but $\{u, w\}$ is not a conflict. This structure means that the vertices $u, v, w$ induce a $P_3$ in the conflict graph. If the conflict graph, or any graph for that matter, does not contain an induced $P_3$, its connected components are cliques. For this structure, the network can be adjusted to correctly model conflict-free vertex-reassignments. The problem to find, for a given graph, a smallest vertex set whose removal yields a $P_3$-free graph is called *INDUCED $P_3$-COVER* or *CLUSTER VERTEX DELETION*.

It is possible to, in a sense, generalise the algorithm for Theorem 7 to consider a cluster vertex deletion set instead of a $P_3$-cover to reduce the cost for guessing the partition. We denote the corresponding parameter, size of a cluster vertex deletion set for the conflict graph, by $p_{3d}$. While the relation $p_{3d} \le p_{3c}$ obviously makes this generalisation an improvement, we have to pay for this in the branching for the pre-clustering, as the remaining conflicts are no longer bounded by $\frac{1}{2}|P|$. A minimum cluster vertex deletion set for $G_c$ can be computed in
**► Theorem 6.** A 3-approximation for ($\|\cdot\|_{\infty}$, rad)-k-CLUSTER can be computed with a running time in $O^*(2^{p_c} \cdot B_{p_c})$.

## 4.2 $P_3$-Covers

With more changes to the algorithms discussed for ($\|\cdot\|_{\infty}$, diam)-k-CLUSTER, it is possible to further reduce the size of the subset of $P$ which requires the expensive guessing of the partition. When building the first partition in step (1), it is always possible to correctly assign conflict vertices to a set, by branching on the conflicts to decide which vertex has to be excluded. This way it is possible to find a correct choice of central vertices. The network used to model the reassignment of vertices according to the fixed centres can be altered to prevent two conflict vertices to move into the same cluster, by routing their flow through an additional network-vertex with a capacity of only 1 to move into a cluster. If the conflicts are isolated, an additional network-vertex for each conflict can be used to correctly model all conflict-free reassignments.

We can of course not assume that conflicts are pairwise disjoint, but we can fix the partition of a subset of conflict vertices, as we did for the vertex cover of the conflict graph, and use the above ideas for the remaining vertices which induce a graph with isolated conflicts. The set of vertices which have to be removed in order to arrive at a graph with isolated edges, or equivalently a graph which does not contain any path of length 2 usually denoted $P_3$, is smaller than the vertex cover of the conflict graph (unless the instance is initially metric). Formally, such a set is called a *$P_3$-cover*. In the following, we use $p_{3c}$ to denote the cardinality of a smallest $P_3$-cover for $G_c$ and with the parameterised algorithm from [24], such a set can be computed with a running time in $O^*(1.7485^{p_{3c}})$. Using the more expensive strategy of guessing the correct partition only for a minimum $P_3$-cover of the conflict graph computed with the algorithm in [24], branching on the remaining isolated conflicts for the pre-clustering and modifying the network to avoid conflicts as described above gives the following result; observe that the number of remaining conflicts is bounded by $\frac{p}{2}$:

**► Theorem 7.** A 2-approximation for ($\|\cdot\|_{\infty}$, diam)-k-CLUSTER can be computed with a running time in $O^*(\sqrt{2^p} \cdot B_{p_{3c}})$.

As already mentioned, branching on conflicts in step (1) works for any set of conflicts, not just for the restriction to isolated ones. The reassignment restriction for conflict vertices modelled with the capacities in the network however requires a situation where, in case of conflict, at most one vertex can be moved into a cluster. Capacities on arcs from some additional network-vertices which handle conflicts, can not model a scenario where out of three vertices $u, v, w$, a cluster is restricted to either only contain $u$ or any subset of $\{v, w\}$; this situation occurs if $u$ is in conflict with $v$ and $w$ but $\{u, w\}$ is not a conflict. This structure means that the vertices $u, v, w$ induce a $P_3$ in the conflict graph. If the conflict graph, or any graph for that matter, does not contain an induced $P_3$, its connected components are cliques. For this structure, the network can be adjusted to correctly model conflict-free vertex-reassignments. The problem to find, for a given graph, a smallest vertex set whose removal yields a $P_3$-free graph is called *INDUCED $P_3$-COVER* or *CLUSTER VERTEX DELETION*.

It is possible to, in a sense, generalise the algorithm for Theorem 7 to consider a cluster vertex deletion set instead of a $P_3$-cover to reduce the cost for guessing the partition. We denote the corresponding parameter, size of a cluster vertex deletion set for the conflict graph, by $p_{3d}$. While the relation $p_{3d} \le p_{3c}$ obviously makes this generalisation an improvement, we have to pay for this in the branching for the pre-clustering, as the remaining conflicts are no longer bounded by $\frac{1}{2}|P|$. A minimum cluster vertex deletion set for $G_c$ can be computed in
<table><caption>**Table 1** Summary of the running time of the parameterised 2-approximation for $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER, where $p_c, p_{3c}$ and $p_{3d}$ denote the size of a minimum vertex, $\mathcal{P}_3$ and induced $\mathcal{P}_3$-cover for the conflict graph, respectively.</caption><thead><tr><th>$p_c$</th><th>$p_{3c}$</th><th>$p_{3d}$</th></tr></thead><tbody><tr><td>$O^*(B_{p_c})$<br>(Theorem 5)</td><td>$O^*(\sqrt{2^p}B_{p_{3c}})$<br>(Theorem 7)</td><td>$O^*(2^c B_{p_{3d}})$<br>(Theorem 8)</td></tr></tbody></table>

time $O^*(1.9102^{p_{3d}})$ with the help of the parameterised algorithm in [7], so again a negligible effort compared to checking all partitions, and this idea hence yields the following result:

**Theorem 8.** A 2-approximation for $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER can be computed with a running time in $O^*(2^c \cdot B_{p_{3d}})$.

The results to improve the parameterised approximation from Theorem 5 are presented here in a way which suggest a stepwise improvement of the running time. In principle, reducing the number of vertices which require partitioning appears to be the best option. But the reductions of this set used for Theorems 7 and 8 require additional branching costs on conflict vertices and conflicts, respectively. Depending on the structure of the conflict graph, any one of the three algorithms can have the best worst-case running time. An overview of the parameterised 2-approximations for $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER with respect to the structural parameters of the conflict graph discussed in this section is given in Table 1.

# 5 Lower Bounds

In this section, we investigate the limitations of parameterised approximation for lower bounded clustering with structural parameters of the conflict graph. Especially the increase from ratio 2 for metric instances to ratio 3 for non-metric instances for $(\|\cdot\|_{\infty}, \text{rad})$-k-CLUSTER appears strange. We will however see that ratio 3 is, under certain complexity theoretic assumptions, optimal for parameter $p_c$ and that the approach we use to design parameterised approximations is generally limited to the performance ratio of 3 for radius. Further, we will discuss the limits of choosing structural parameters for $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER. More precisely, we will see that while the previous section gave approaches to move from $p$ to $p_c, p_{3c}$ and $p_{3d}$, a next step towards a parameterisation by a split vertex deletion set does not seem to allow for a constant factor parameterised approximation.

For the negative results of this section, we use a kind of reduction which links the existence of a parameterised approximation with certain ratio to a parameterised algorithm for a problem which is believed not to be in FPT. Such an algorithm can be seen as *fpt gap-reduction* as introduced in [4]. As the problem to reduce from for $(\|\cdot\|_{\infty}, \text{rad})$-k-CLUSTER, we use MULTICOLOURED DOMINATING SET, which asks for input graph $G = (V, E)$ with vertex partition $V = V_1, \dots, V_\ell$ for the existence of a subset $\mathcal{D} \subseteq V$ such that $N[\mathcal{D}] = V$ ($\mathcal{D}$ is a dominating set for $G$) and $|\mathcal{D} \cap V_i| = 1$ for all $i \in \{1, \dots, \ell\}$. The colour-coding technique from [2] shows that the W[2]-hardness of classical MINIMUM DOMINATING SET, which is shown in [11], transfers to this restricted version we called *multicoloured* in reference to MULTICOLOURED CLIQUE and the corresponding reduction technique introduced in [15].

We will in the following sketch a reduction from MULTICOLOURED DOMINATING SET to $(\|\cdot\|_{\infty}, \text{rad})$-k-CLUSTER which shows that a parameterised approximation with parameter $p_c$ for the clustering problem could be used to show fixed parameter tractability of the W[2]-hard domination problem. This kind of reduction yields a lower bound for parameterised approximation of $(\|\cdot\|_{\infty}, \text{rad})$-k-CLUSTER under the assumption FPT $\neq$ W[2].
<table><caption>**Table 1** Summary of the running time of the parameterised 2-approximation for $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER, where $p_c, p_{3c}$ and $p_{3d}$ denote the size of a minimum vertex, $P_3$ and induced $P_3$-cover for the conflict graph, respectively.</caption><thead><tr><th>$p_c$</th><th>$p_{3c}$</th><th>$p_{3d}$</th></tr></thead><tbody><tr><td>$O^*(B_{p_c})$<br>(Theorem 5)</td><td>$O^*(\sqrt{2^p}B_{p_{3c}})$<br>(Theorem 7)</td><td>$O^*(2^c B_{p_{3d}})$<br>(Theorem 8)</td></tr></tbody></table>

time $O^*(1.9102^{p_{3d}})$ with the help of the parameterised algorithm in [7], so again a negligible effort compared to checking all partitions, and this idea hence yields the following result:

**Theorem 8.** A 2-approximation for $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER can be computed with a running time in $O^*(2^c \cdot B_{p_{3d}})$.

The results to improve the parameterised approximation from Theorem 5 are presented here in a way which suggest a stepwise improvement of the running time. In principle, reducing the number of vertices which require partitioning appears to be the best option. But the reductions of this set used for Theorems 7 and 8 require additional branching costs on conflict vertices and conflicts, respectively. Depending on the structure of the conflict graph, any one of the three algorithms can have the best worst-case running time. An overview of the parameterised 2-approximations for $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER with respect to the structural parameters of the conflict graph discussed in this section is given in Table 1.

# 5 Lower Bounds

In this section, we investigate the limitations of parameterised approximation for lower bounded clustering with structural parameters of the conflict graph. Especially the increase from ratio 2 for metric instances to ratio 3 for non-metric instances for $(\|\cdot\|_{\infty}, \text{rad})$-k-CLUSTER appears strange. We will however see that ratio 3 is, under certain complexity theoretic assumptions, optimal for parameter $p_c$ and that the approach we use to design parameterised approximations is generally limited to the performance ratio of 3 for radius. Further, we will discuss the limits of choosing structural parameters for $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER. More precisely, we will see that while the previous section gave approaches to move from $p$ to $p_c, p_{3c}$ and $p_{3d}$, a next step towards a parameterisation by a split vertex deletion set does not seem to allow for a constant factor parameterised approximation.

For the negative results of this section, we use a kind of reduction which links the existence of a parameterised approximation with certain ratio to a parameterised algorithm for a problem which is believed not to be in FPT. Such an algorithm can be seen as *fpt gap-reduction* as introduced in [4]. As the problem to reduce from for $(\|\cdot\|_{\infty}, \text{rad})$-k-CLUSTER, we use MULTICOLOURED DOMINATING SET, which asks for input graph $G = (V, E)$ with vertex partition $V = V_1, \dots, V_\ell$ for the existence of a subset $D \subseteq V$ such that $N[D] = V$ ($D$ is a dominating set for $G$) and $|D \cap V_i| = 1$ for all $i \in \{1, \dots, \ell\}$. The colour-coding technique from [2] shows that the W[2]-hardness of classical MINIMUM DOMINATING SET, which is shown in [11], transfers to this restricted version we called *multicoloured* in reference to MULTICOLOURED CLIQUE and the corresponding reduction technique introduced in [15].

We will in the following sketch a reduction from MULTICOLOURED DOMINATING SET to $(\|\cdot\|_{\infty}, \text{rad})$-k-CLUSTER which shows that a parameterised approximation with parameter $p_c$ for the clustering problem could be used to show fixed parameter tractability of the W[2]-hard domination problem. This kind of reduction yields a lower bound for parameterised approximation of $(\|\cdot\|_{\infty}, \text{rad})$-k-CLUSTER under the assumption FPT $\neq$ W[2].
<figure><img src="image_119.png" /><figcaption>■ **Figure 2** Illustration of the reduction used for Theorem 9, vertices in the vertex cover for the conflict graph drawn with thick border.</figcaption></figure>

For an instance $G = (V, E)$ with $V = V_1, \dots, V_\ell$ and $|V| = n$ of MULTICOLOURED DOMINATING SET, we construct an instance $((V', E'), w_{E'}, n + 2)$ of $(\|\cdot\|_\infty, \text{rad})$-k-CLUSTER with vertex set $V'$ containing $V$, a copy of $V$, denoted $\bar{V} = \{\bar{v}: v \in V\}$, $\ell + 2$ vertices (which will become the vertex cover of the conflict graph) denoted $u_1, \dots, u_\ell$ and $u_r, u_R$ and an additional set $X$ of $(\ell - 1)n + \ell$ vertices. These vertices are connected with the following edges of weight 1 (see also the illustrated in Figure 9):

- $\{v, \bar{w}\}, \{\bar{w}, v\} \in E'$ iff $\{v, w\} \in E$ (these model the structure of the original graph),

- $\{u_i, v\} \in E'$ for all $v \in V_i$, $i \in \{1, \dots, \ell\}$ (these force to pick one center from each $V_i$),

- $\{v, x\} \in E'$ for all $x \in X$, $v \in V \cup \{u_r\}$ (enables balancing cardinalities with the set $X$),

- $\{u_r, v\} \in E'$ for all $v \in V$ and $\{u_r, u_R\} \in E'$ (forces $u_r$ to be central and allows to assign $v \in V$ not picked for the dominating set at radius 1 to the corresponding cluster).

Further $E'$ contains all other edges involving the vertices $u_1, \dots, u_\ell$ and $u_r, u_R$ with weight 3 which clearly makes this set of $\ell + 2$ vertices a vertex cover of the conflict graph for the resulting $(\|\cdot\|_\infty, \text{rad})$-k-CLUSTER instance $((V', E'), w_{E'}, n + 2)$.

Assuming the existence of a parameterised approximation with parameter $p_c$ and ratio better than 3 for $(\|\cdot\|_\infty, \text{rad})$-k-CLUSTER, this algorithm would be able to build clusters with maximum radius less than 3 for $((V', E'), w_{E'}, n + 2)$ if and only if there exists a multicoloured dominating set for $G = (V, E)$; more precisely, the centres of the clusters containing the vertices $u_1, \dots, u_\ell$ in a k-cluster of maximum radius less than 3 for $((V', E'), w_{E'}, n + 2)$ correspond to a multicoloured dominating set for $G = (V, E)$. To understand why this is true, observe that the lower bound $n + 2$ only allows to build at most $\ell + 1$ clusters, while a maximum radius of less than 3 requires at least one cluster with $u_r$ and one cluster with a vertex from $V_i \cup \{u_i\}$ for each $i \in \{1, \dots, \ell\}$ as centre. A vertex $\bar{V}$ can then only be at distance less than 3 from a centre if the corresponding vertex in the original graph $G$ is adjacent to this centre. As this parameterised approximation has a running-time in $O^*(g(p_c))$ for some computable function $g$, and $p_c$ is bounded by $\ell + 2$, the given polynomial construction of $((V', E'), w_{E'}, n + 2)$ combined with this assumed parameterised approximation could be used to solve MULTICOLOURED DOMINATING SET in $O^*(g(\ell))$, which formally yields:

► **Theorem 9.** There exists no $(3 - \varepsilon)$-approximation for $(\|\cdot\|_\infty, \text{rad})$-k-CLUSTER with a running time in $O^*(g(p_c))$ for any $\varepsilon > 0$ and computable function $g$, unless FPT = W[2].
<figure><img src="image_120.png" /><figcaption>■ **Figure 2** Illustration of the reduction used for Theorem 9, vertices in the vertex cover for the conflict graph drawn with thick border.</figcaption></figure>

For an instance $G = (V, E)$ with $V = V_1, \dots, V_\ell$ and $|V| = n$ of MULTICOLOURED DOMINATING SET, we construct an instance $((V', E'), w_{E'}, n + 2)$ of $(\|\cdot\|_\infty, \text{rad})$-k-CLUSTER with vertex set $V'$ containing $V$, a copy of $V$, denoted $\bar{V} = \{\bar{v}: v \in V\}$, $\ell + 2$ vertices (which will become the vertex cover of the conflict graph) denoted $u_1, \dots, u_\ell$ and $u_r, u_R$ and an additional set $X$ of $(\ell - 1)n + \ell$ vertices. These vertices are connected with the following edges of weight 1 (see also the illustrated in Figure 9):

- $\{v, \bar{w}\}, \{\bar{w}, v\} \in E'$ iff $\{v, w\} \in E$ (these model the structure of the original graph),

- $\{u_i, v\} \in E'$ for all $v \in V_i$, $i \in \{1, \dots, \ell\}$ (these forces to pick one center from each $V_i$),

- $\{v, x\} \in E'$ for all $x \in X$, $v \in V \cup \{u_r\}$ (enables balancing cardinalities with the set $X$),

- $\{u_r, v\} \in E'$ for all $v \in V$ and $\{u_r, u_R\} \in E'$ (forces $u_r$ to be central and allows to assign $v \in V$ not picked for the dominating set at radius 1 to the corresponding cluster).

Further $E'$ contains all other edges involving the vertices $u_1, \dots, u_\ell$ and $u_r, u_R$ with weight 3 which clearly makes this set of $\ell + 2$ vertices a vertex cover of the conflict graph for the resulting $(\|\cdot\|_\infty, \text{rad})$-k-CLUSTER instance $((V', E'), w_{E'}, n + 2)$.

Assuming the existence of a parameterised approximation with parameter $p_c$ and ratio better than 3 for $(\|\cdot\|_\infty, \text{rad})$-k-CLUSTER, this algorithm would be able to build clusters with maximum radius less than 3 for $((V', E'), w_{E'}, n + 2)$ if and only if there exists a multicoloured dominating set for $G = (V, E)$; more precisely, the centres of the clusters containing the vertices $u_1, \dots, u_\ell$ in a k-cluster of maximum radius less than 3 for $((V', E'), w_{E'}, n + 2)$ correspond to a multicoloured dominating set for $G = (V, E)$. To understand why this is true, observe that the lower bound $n + 2$ only allows to build at most $\ell + 1$ clusters, while a maximum radius of less than 3 requires at least one cluster with $u_r$ and one cluster with a vertex from $V_i \cup \{u_i\}$ for each $i \in \{1, \dots, \ell\}$ as centre. A vertex $\bar{V}$ can then only be at distance less than 3 from a centre if the corresponding vertex in the original graph $G$ is adjacent to this centre. As this parameterised approximation has a running-time in $O^*(g(p_c))$ for some computable function $g$, and $p_c$ is bounded by $\ell + 2$, the given polynomial construction of $((V', E'), w_{E'}, n + 2)$ combined with this assumed parameterised approximation could be used to solve MULTICOLOURED DOMINATING SET in $O^*(g(\ell))$, which formally yields:

► **Theorem 9.** There exists no $(3 - \varepsilon)$-approximation for $(\|\cdot\|_\infty, \text{rad})$-k-CLUSTER with a running time in $O^*(g(p_c))$ for any $\varepsilon > 0$ and computable function $g$, unless FPT = W[2].
<figure><img src="image_120.png" /><figcaption>Figure 3 Illustration of the reduction used for Theorem 10, bold lines represent conflict edges with weight $r+1$, all other edges in the complete graph have weight 1. Vertices $u, v \in V$ are such that $\{u, v\} \in E$, $1 \in L(u)$, $1 \notin L(v)$, $2 \in L(u) \cap L(v)$ and $\ell \notin L(u) \cup L(v)$.</figcaption></figure>

The reduction used to prove Theorem 9 also illustrates why our parameterised approximation for $(\|\cdot\|_{\infty}, \text{rad})$-k-CLUSTER with parameter $p$ does not have a performance ratio better than 3. The situation illustrated in Figure 2 is also a case where our algorithmic strategy fails; if the algorithm chooses $w$ instead of $v$ as central vertex in step (1) (observe that these two are both not in the set $P$), then $q$ is one of the vertices in $P \setminus P'$ (in fact $P' = \emptyset$ is the only correct choice) which has to be put into a suitable cluster without choosing it as centre, which places it at the worst possible distance (3 times the optimum) from the central vertex.

For diameter, we want to investigate the limits of choosing smaller sets of vertices which require partitioning in our parameterised approximations. A graph $G = (V, E)$ is called a split graph, if its vertex set can be partitioned into two disjoint sets $A$ and $B$ such that $A$ is an independent set in $G$ and $G[B]$ is the complete graph on vertex set $B$. Especially for the application to ratings to build recommendation systems, it appears that the conflict graph almost has the structure of a split graph: with a small set of users which give unusual ratings and are hence in conflict among each other (set $B$) and with a larger set of more average users (set $A$). This observation raises the question whether it is helpful to turn the conflict graph into a split graph, as this transformation appears to require very little change.

Formally, a split vertex deletion set of a graph $G = (V, E)$ is a subset $V'$ of $V$ such that $G[V \setminus V']$ is a split graph. Looking at the previous strategies to lower the parameter from vertex cover to $P_3$-cover to cluster vertex deletion, the size of a minimum split vertex deletion set appears to be a promising next smaller parameter-choice. Unfortunately, it seems that this parameterisation can not be used for $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER as the following result will show. We will use a similar kind of fpt gap-reduction between $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER parameterised by split deletion set from the problem LIST COLOURING, which for a given graph $G = (V, E)$, colours $\{1, \dots, \ell\}$ and a set of possible colours for each vertex $v \in V$, given by a list $L(v) \subseteq \{1, \dots, \ell\}$ for each $v \in V$ asks if there exists a colouring $f: V \to \{1, \dots, r\}$ such that $f(v) \in L(v)$ for all $v \in V$ and $f(v) \neq f(w)$ for all $\{v, w\} \in E$. LIST COLOURING with parameter $\tau(G)$ (vertex cover number of $G$) is W[1]-hard, see [14, 16].

Our reduction from LIST COLOURING to $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER constructs a clustering instance $((V', E'), w_{E'}, n+2)$ as sketched in Figure 3, where $G$ is the input graph for LIST COLOURING and each $L_i$, is a set of $n+2$ new vertices. Observe that a vertex cover for $G$ is a split vertex deletion set of the conflict graph for this instance. It can be shown that a "yes"-instance for LIST COLOURING corresponds to a k-cluster of maximum diameter 1 while a "no"-instance yields a diameter of at least $r+1$.
<figure><img src="image_121.png" /><figcaption>■ **Figure 3** Illustration of the reduction used for Theorem 10, bold lines represent conflict edges with weight $r+1$, all other edges in the complete graph have weight 1. Vertices $u, v \in V$ are such that $\{u, v\} \in E$, $1 \in L(u)$, $1 \notin L(v)$, $2 \in L(u) \cap L(v)$ and $\ell \notin L(u) \cup L(v)$.</figcaption></figure>

The reduction used to prove Theorem 9 also illustrates why our parameterised approximation for $(\|\cdot\|_{\infty}, \text{rad})$-k-CLUSTER with parameter $p$ does not have a performance ratio better than 3. The situation illustrated in Figure 2 is also a case where our algorithmic strategy fails; if the algorithm chooses $w$ instead of $v$ as central vertex in step (1) (observe that these two are both not in the set $P$), then $q$ is one of the vertices in $P \setminus P'$ (in fact $P' = \emptyset$ is the only correct choice) which has to be put into a suitable cluster without choosing it as centre, which places it at the worst possible distance (3 times the optimum) from the central vertex.

For diameter, we want to investigate the limits of choosing smaller sets of vertices which require partitioning in our parameterised approximations. A graph $G = (V, E)$ is called a *split graph*, if its vertex set can be partitioned into two disjoint sets *A* and *B* such that *A* is an independent set in *G* and *G[B]* is the complete graph on vertex set *B*. Especially for the application to ratings to build recommendation systems, it appears that the conflict graph almost has the structure of a split graph: with a small set of users which give unusual ratings and are hence in conflict among each other (set *B*) and with a larger set of more average users (set *A*). This observation raises the question whether it is helpful to turn the conflict graph into a split graph, as this transformation appears to require very little change.

Formally, a *split vertex deletion set* of a graph $G = (V, E)$ is a subset $V'$ of $V$ such that $G[V \setminus V']$ is a split graph. Looking at the previous strategies to lower the parameter from vertex cover to $P_3$-cover to cluster vertex deletion, the size of a minimum split vertex deletion set appears to be a promising next smaller parameter-choice. Unfortunately, it seems that this parameterisation can not be used for $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER as the following result will show. We will use a similar kind of ftpt gap-reduction between $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER parameterised by split deletion set from the problem LIST COLOURING, which for a given graph $G = (V, E)$, colours $\{1, \dots, \ell\}$ and a set of possible colours for each vertex $v \in V$, given by a list $L(v) \subseteq \{1, \dots, \ell\}$ for each $v \in V$ asks if there exists a colouring $f: V \to \{1, \dots, r\}$ such that $f(v) \in L(v)$ for all $v \in V$ and $f(v) \neq f(w)$ for all $\{v, w\} \in E$. LIST COLOURING with parameter $\tau(G)$ (vertex cover number of $G$) is W[1]-hard, see [14, 16].

Our reduction from LIST COLOURING to $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER constructs a clustering instance $((V', E'), w_{E'}, n + 2)$ as sketched in Figure 3, where $G$ is the input graph for LIST COLOURING and each $L_i$, is a set of $n + 2$ new vertices. Observe that a vertex cover for $G$ is a split vertex deletion set of the conflict graph for this instance. It can be shown that a "yes"-instance for LIST COLOURING corresponds to a k-cluster of maximum diameter 1 while a "no"-instance yields a diameter of at least $r + 1$.
This would enable solving LIST COLOURING in $O^*(g(\tau))$ if there existed a parameterised approximation with ratio $r$ and cluster vertex deletion set as parameter for $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER, hence:

**Theorem 10.** There exists no constant factor approximation for $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER with a running time in $O^*(f(p_s))$, for any computable function $f$, unless FPT = W[1].

## 6 Conclusions

As the exponential time hypothesis implies FPT $\neq$ W[1] by [8], the negative results in this paper especially hold assuming the exponential time hypothesis [19]. Both reductions used to show these create instances of $(\|\cdot\|, f)$-k-CLUSTER with large values for $k$. In most applications however, $k$ is a fixed, not too large integer, which raises the question whether an additional parameterisation by $k$ (additional to the number of conflicts) would help overcome the negative results. For the greedy strategies used for the parameterised approximations in this paper, it is not clear how $k$ could be included in a useful way. An improvement with parameterisation by both conflicts and $k$ probably means using a very different algorithmic approach. The gap between our positive results and the presented lower bounds further suggests room for improvement. Stronger lower bounds seem to require new techniques for reductions which consider both parameterisation and approximation.

We would like to mention that a relaxation of the cardinality constraint, i.e., asking for an approximate solution in the sense that this partition is allowed to contain clusters with only $\alpha k$ vertices, for some factor $0 < \alpha \le 1$, does not help with the problems caused by conflicts. In fact, the inapproximability for general non-metric instances from [1] holds for fixed values of $k$ with $k \ge 3$, which means that this kind of additional cardinality relaxation either yields a polynomial time solvable problem, in case $\alpha k \le 2$, or a problem with the same approximation hardness.

One other aspect we did not consider here is the optimality of the asymptotic running times of our positive results. Techniques for such more fine-grained considerations need a more careful analysis. A concrete question in this regard is whether it is possible to improve the parameterised approximations for $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER to only require single-exponential time. In this regard it would be very interesting to see if slightly superexponential lower bounds as shown in [21] can be proven for a 2-approximation of $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER with parameter $p$. For improvement on the running time on the other hand, it might be interesting to analyse the algorithms with a closer look at the enumerations of the partitions of $P$. We always estimated this with the Bell number although we only consider partitions with specific properties (those which are possible in a clustering of maximum diameter $D$) which in a sense relate to colourings of the conflict graph. It might be possible to enumerate the relevant partitions of $P$ more efficiently with the help of colouring strategies.

Aside from the problems discussed here, there are many other related clustering-type problems which exhibit similar difficulties with violations of the triangle inequality. The parameterisation by conflicts and related parameters might provide a useful way to approach these problems as well.

## References

1. F. N. Abu-Khzam, C. Bazgan, K. Casel, and H. Fernau. Clustering with Lower-Bounded Sizes - A General Graph-Theoretic Framework. Algorithmica, 80(9):2517-2550, 2018.

2. N. Alon, R. Yuster, and U. Zwick. Color Coding. In M.-Y. Kao, editor, Encyclopedia of Algorithms. Springer, 2008.
This would enable solving LIST COLOURING in $O^*(g(\tau))$ if there existed a parameterised approximation with ratio $r$ and cluster vertex deletion set as parameter for $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER, hence:

**Theorem 10.** There exists no constant factor approximation for $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER with a running time in $O^*(f(p_s))$, for any computable function $f$, unless FPT = W[1].

## 6 Conclusions

As the exponential time hypothesis implies FPT $\neq$ W[1] by [8], the negative results in this paper especially hold assuming the exponential time hypothesis [19]. Both reductions used to show these create instances of $(\|\cdot\|, f)$-k-CLUSTER with large values for $k$. In most applications however, $k$ is a fixed, not too large integer, which raises the question whether an additional parameterisation by $k$ (additional to the number of conflicts) would help overcome the negative results. For the greedy strategies used for the parameterised approximations in this paper, it is not clear how $k$ could be included in a useful way. An improvement with parameterisation by both conflicts and $k$ probably means using a very different algorithmic approach. The gap between our positive results and the presented lower bounds further suggests room for improvement. Stronger lower bounds seem to require new techniques for reductions which consider both parameterisation and approximation.

We would like to mention that a relaxation of the cardinality constraint, i.e., asking for an approximate solution in the sense that this partition is allowed to contain clusters with only $\alpha k$ vertices, for some factor $0 < \alpha \le 1$, does not help with the problems caused by conflicts. In fact, the inapproximability for general non-metric instances from [1] holds for fixed values of $k$ with $k \ge 3$, which means that this kind of additional cardinality relaxation either yields a polynomial time solvable problem, in case $\alpha k \le 2$, or a problem with the same approximation hardness.

One other aspect we did not consider here is the optimality of the asymptotic running times of our positive results. Techniques for such more fine-grained considerations need a more careful analysis. A concrete question in this regard is whether it is possible to improve the parameterised approximations for $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER to only require single-exponential time. In this regard it would be very interesting to see if slightly superexponential lower bounds as shown in [21] can be proven for a 2-approximation of $(\|\cdot\|_{\infty}, \text{diam})$-k-CLUSTER with parameter $p$. For improvement on the running time on the other hand, it might be interesting to analyse the algorithms with a closer look at the enumerations of the partitions of $P$. We always estimated this with the Bell number although we only consider partitions with specific properties (those which are possible in a clustering of maximum diameter $D$) which in a sense relate to colourings of the conflict graph. It might be possible to enumerate the relevant partitions of $P$ more efficiently with the help of colouring strategies.

Aside from the problems discussed here, there are many other related clustering-type problems which exhibit similar difficulties with violations of the triangle inequality. The parameterisation by conflicts and related parameters might provide a useful way to approach these problems as well.

## References

1. F. N. Abu-Khzam, C. Bazgan, K. Casel, and H. Fernau. Clustering with Lower-Bounded Sizes - A General Graph-Theoretic Framework. *Algorithmica*, 80(9):2517-2550, 2018.

2. N. Alon, R. Yuster, and U. Zwick. Color Coding. In M.-Y. Kao, editor, *Encyclopedia of Algorithms*. Springer, 2008.
3 G. Ausiello. *Complexity and approximation: combinatorial optimization problems and their approximability properties*. Springer, 1999.

4 C. Bazgan, M. Chopin, A. Nichterlein, and F. Sikora. Parameterized Inapproximability of Target Set Selection and Generalizations. *Computability*, 3(2):135–145, 2014.

5 D. Berend and T. Tassa. Improved bounds on Bell numbers and on moments of sums of random variables. *Probability and Mathematical Statistics*, 30(2):185–205, 2010.

6 B. Bollobás. *Modern Graph Theory*, volume 184 of *Graduate texts in mathematics*. Springer, 1998.

7 A. Boral, M. Cygan, T. Kociumaka, and M. Pilipczuk. A Fast Branching Algorithm for Cluster Vertex Deletion. *Theory Comput. Syst.*, 58(2):357–376, 2016.

8 J. Chen, X. Huang, I. A. Kanj, and G. Xia. Strong computational lower bounds via parameterized complexity. *J. Comput. Syst. Sci.*, 72(8):1346–1367, 2006. doi:10.1016/j.jcss.2006.04.007.

9 J. Chen, I. A. Kanj, and G. Xia. Improved upper bounds for vertex cover. *Theor. Comput. Sci.*, 411(40–42):3736–3756, 2010. doi:10.1016/j.tcs.2010.06.026.

10 I. Dinur and D. Steurer. Analytical approach to parallel repetition. In D. B. Shmoys, editor, *Symposium on Theory of Computing, STOC*, pages 624–633. ACM, 2014.

11 R. G. Downey and M. Fellows. Fixed parameter tractability and completeness. *Congressus Numerantium*, 87:161–187, 1992.

12 R. G. Downey and M. Fellows. *Fundamentals of Parameterized Complexity*. Texts in Computer Science. Springer, 2013.

13 C. Elkan. Using the Triangle Inequality to Accelerate k-Means. In T. Fawcett and N. Mishra, editors, *Machine Learning, Proceedings of the Twentieth International Conference (ICML 2003), August 21-24, 2003, Washington, DC, USA*, pages 147–153. AAAI Press, 2003.

14 M. Fellows, F. Fomin, D. Lokshtanov, F. Rosamond, S. Saurabh, S. Szeider, and C. Thomassen. On the complexity of some colorful problems parameterized by treewidth. *Information and Computation*, 209(2):143–153, 2011.

15 M. Fellows, D. Hermelin, F. A. Rosamond, and S. Vialette. On the parameterized complexity of multiple-interval graph problems. *Theor. Comput. Sci.*, 410(1):53–61, 2009.

16 J. Fiala, P. Golovach, and J. Kratochvíl. Parameterized complexity of coloring problems: Treewidth versus vertex cover. *Theor. Comput. Sci.*, 412(23):2513–2523, 2011. doi:10.1016/j.tcs.2010.10.043.

17 J. Guo, F. Hüffner, and R. Niedermeier. A Structural View on Parameterizing Problems: Distance from Triviality. In R. G. Downey, M. Fellows, and F. K. H. A. Dehne, editors, *Parameterized and Exact Computation, First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004, Proceedings*, volume 3162 of LNCS. Springer, 2004.

18 D. S. Hochbaum. Heuristics for the fixed cost median problem. *Mathematical Programming*, 22(1):148–162, 1982.

19 R. Impagliazzo and R. Paturi. On the Complexity of k-SAT. *J. Comput. Syst. Sci.*, 62(2):367–375, 2001.

20 S. Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. *Information and Computation*, 222:45–58, 2013.

21 D. Lokshtanov, D. Marx, and S. Saurabh. Slightly Superexponential Parameterized Problems. *SIAM J. Comput.*, 47(3):675–702, 2018.

22 D. Marx. Parameterized complexity and approximation algorithms. *The Computer Journal*, 51(1):60–78, 2008.

23 J. B. Schafer, D. Frankowski, J. L. Herlocker, and S. Sen. Collaborative Filtering Recommender Systems. In P. Brusilovsky, A. Kobsa, and W. Nejdl, editors, *The Adaptive Web, Methods and Strategies of Web Personalization*, volume 4321 of LNCS, pages 291–324. Springer, 2007.
3 G. Ausiello. *Complexity and approximation: combinatorial optimization problems and their approximability properties*. Springer, 1999.

4 C. Bazgan, M. Chopin, A. Nichterlein, and F. Sikora. Parameterized Inapproximability of Target Set Selection and Generalizations. *Computability*, 3(2):135–145, 2014.

5 D. Berend and T. Tassa. Improved bounds on Bell numbers and on moments of sums of random variables. *Probability and Mathematical Statistics*, 30(2):185–205, 2010.

6 B. Bollobás. *Modern Graph Theory*, volume 184 of *Graduate texts in mathematics*. Springer, 1998.

7 A. Boral, M. Cygan, T. Kociumaka, and M. Pilipczuk. A Fast Branching Algorithm for Cluster Vertex Deletion. *Theory Comput. Syst.*, 58(2):357–376, 2016.

8 J. Chen, X. Huang, I. A. Kanj, and G. Xia. Strong computational lower bounds via parameterized complexity. *J. Comput. Syst. Sci.*, 72(8):1346–1367, 2006. doi:10.1016/j.jcss.2006.04.007.

9 J. Chen, I. A. Kanj, and G. Xia. Improved upper bounds for vertex cover. *Theor. Comput. Sci.*, 411(40–42):3736–3756, 2010. doi:10.1016/j.tcs.2010.06.026.

10 I. Dinur and D. Steurer. Analytical approach to parallel repetition. In D. B. Shmoys, editor, *Symposium on Theory of Computing, STOC*, pages 624–633. ACM, 2014.

11 R. G. Downey and M. Fellows. Fixed parameter tractability and completeness. *Congressus Numerantium*, 87:161–187, 1992.

12 R. G. Downey and M. Fellows. *Fundamentals of Parameterized Complexity*. Texts in Computer Science. Springer, 2013.

13 C. Elkan. Using the Triangle Inequality to Accelerate k-Means. In T. Fawcett and N. Mishra, editors, *Machine Learning, Proceedings of the Twentieth International Conference (ICML 2003), August 21-24, 2003, Washington, DC, USA*, pages 147–153. AAAI Press, 2003.

14 M. Fellows, F. Fomin, D. Lokshtanov, F. Rosamond, S. Saurabh, S. Szeider, and C. Thomassen. On the complexity of some colorful problems parameterized by treewidth. *Information and Computation*, 209(2):143–153, 2011.

15 M. Fellows, D. Hermelin, F. A. Rosamond, and S. Vialette. On the parameterized complexity of multiple-interval graph problems. *Theor. Comput. Sci.*, 410(1):53–61, 2009.

16 J. Fiala, P. Golovach, and J. Kratochvíl. Parameterized complexity of coloring problems: Treewidth versus vertex cover. *Theor. Comput. Sci.*, 412(23):2513–2523, 2011. doi:10.1016/j.tcs.2010.10.043.

17 J. Guo, F. Hüffner, and R. Niedermeier. A Structural View on Parameterizing Problems: Distance from Triviality. In R. G. Downey, M. Fellows, and F. K. H. A. Dehne, editors, *Parameterized and Exact Computation, First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004, Proceedings*, volume 3162 of LNCS. Springer, 2004.

18 D. S. Hochbaum. Heuristics for the fixed cost median problem. *Mathematical Programming*, 22(1):148–162, 1982.

19 R. Impagliazzo and R. Paturi. On the Complexity of k-SAT. *J. Comput. Syst. Sci.*, 62(2):367–375, 2001.

20 S. Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. *Information and Computation*, 222:45–58, 2013.

21 D. Lokshtanov, D. Marx, and S. Saurabh. Slightly Superexponential Parameterized Problems. *SIAM J. Comput.*, 47(3):675–702, 2018.

22 D. Marx. Parameterized complexity and approximation algorithms. *The Computer Journal*, 51(1):60–78, 2008.

23 J. B. Schafer, D. Frankowski, J. L. Herlocker, and S. Sen. Collaborative Filtering Recommender Systems. In P. Brusilovsky, A. Kobsa, and W. Nejdl, editors, *The Adaptive Web, Methods and Strategies of Web Personalization*, volume 4321 of LNCS, pages 291–324. Springer, 2007.
# Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness

## Marc Roth

Saarland University and Cluster of Excellence (MMCI), Saarbrücken, Germany
mroth@mmci.uni-saarland.de

## Johannes Schmitt<fnref n="1" />

ETH Zürich, Zürich, Switzerland
johannes.schmitt@math.ethz.ch

### Abstract

We investigate the problem #IndSub($\Phi$) of counting all induced subgraphs of size $k$ in a graph $G$ that satisfy a given property $\Phi$. This continues the work of Jerrum and Meeks who proved the problem to be #W[1]-hard for some families of properties which include, among others, (dis)connectedness [JCSS 15] and even- or oddness of the number of edges [Combinatorica 17]. Using the recent framework of graph motif parameters due to Curticapean, Dell and Marx [STOC 17], we discover that for monotone properties $\Phi$, the problem #IndSub($\Phi$) is hard for #W[1] if the reduced Euler characteristic of the associated simplicial (graph) complex of $\Phi$ is non-zero. This observation links #IndSub($\Phi$) to Karp's famous Evasiveness Conjecture, as every graph complex with non-vanishing reduced Euler characteristic is known to be evasive. Applying tools from the "topological approach to evasiveness" which was introduced in the seminal paper of Khan, Saks and Sturtevant [FOCS 83], we prove that #IndSub($\Phi$) is #W[1]-hard for every monotone property $\Phi$ that does not hold on the Hamilton cycle as well as for some monotone properties that hold on the Hamilton cycle such as being triangle-free or not $k$-edge-connected for $k > 2$. Moreover, we show that for those properties #IndSub($\Phi$) can not be solved in time $f(k) \cdot n^{o(k)}$ for any computable function $f$ unless the Exponential Time Hypothesis (ETH) fails. In the final part of the paper, we investigate non-monotone properties and prove that #IndSub($\Phi$) is #W[1]-hard if $\Phi$ is any non-trivial modularity constraint on the number of edges with respect to some prime $q$ or if $\Phi$ enforces the presence of a fixed isolated subgraph.

**2012 ACM Subject Classification** Theory of computation → Parameterized complexity and exact algorithms, Theory of computation → Problems, reductions and completeness, Mathematics of computing → Combinatorics, Mathematics of computing → Graph theory, General and reference → General literature

**Keywords and phrases** counting complexity, Euler characteristic, homomorphisms, parameterized complexity, simplicial complexes

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

**Related Version** https://arxiv.org/abs/1807.01920

**Acknowledgements** We are very grateful to Cornelius Brand, Radu Curticapean, Holger Dell and Johannes Lengler for helpful advice and fruitful discussions. Furthermore we wish to point out that Sloane's OEIS [1] was very useful in the course of this work.

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

<footnote n="1">¹ The second author was supported by the grants SNF-200020162928 and ERC-2017-AdG-786580-MACI.</footnote>
# Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness

## Marc Roth

Saarland University and Cluster of Excellence (MMCI), Saarbrücken, Germany
mroth@mmci.uni-saarland.de

## Johannes Schmitt<fnref n="1" />

ETH Zürich, Zürich, Switzerland
johannes.schmitt@math.ethz.ch

### Abstract

We investigate the problem #IndSub($\Phi$) of counting all induced subgraphs of size $k$ in a graph $G$ that satisfy a given property $\Phi$. This continues the work of Jerrum and Meeks who proved the problem to be #W[1]-hard for some families of properties which include, among others, (dis)connectedness [JCSS 15] and even- or oddness of the number of edges [Combinatorica 17]. Using the recent framework of graph motif parameters due to Curticapean, Dell and Marx [STOC 17], we discover that for monotone properties $\Phi$, the problem #IndSub($\Phi$) is hard for #W[1] if the reduced Euler characteristic of the associated simplicial (graph) complex of $\Phi$ is non-zero. This observation links #IndSub($\Phi$) to Karp's famous Evasiveness Conjecture, as every graph complex with non-vanishing reduced Euler characteristic is known to be evasive. Applying tools from the "topological approach to evasiveness" which was introduced in the seminal paper of Khan, Saks and Sturtevant [FOCS 83], we prove that #IndSub($\Phi$) is #W[1]-hard for every monotone property $\Phi$ that does not hold on the Hamilton cycle as well as for some monotone properties that hold on the Hamilton cycle such as being triangle-free or not $k$-edge-connected for $k > 2$. Moreover, we show that for those properties #IndSub($\Phi$) can not be solved in time $f(k) \cdot n^{o(k)}$ for any computable function $f$ unless the Exponential Time Hypothesis (ETH) fails. In the final part of the paper, we investigate non-monotone properties and prove that #IndSub($\Phi$) is #W[1]-hard if $\Phi$ is any non-trivial modularity constraint on the number of edges with respect to some prime $q$ or if $\Phi$ enforces the presence of a fixed isolated subgraph.

**2012 ACM Subject Classification** Theory of computation → Parameterized complexity and exact algorithms, Theory of computation → Problems, reductions and completeness, Mathematics of computing → Combinatorics, Mathematics of computing → Graph theory, General and reference → General literature

**Keywords and phrases** counting complexity, Euler characteristic, homomorphisms, parameterized complexity, simplicial complexes

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

**Related Version** https://arxiv.org/abs/1807.01920

**Acknowledgements** We are very grateful to Cornelius Brand, Radu Curticapean, Holger Dell and Johannes Lengler for helpful advice and fruitful discussions. Furthermore we wish to point out that Sloane's OEIS [1] was very useful in the course of this work.

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

<footnote n="1">¹ The second author was supported by the grants SNF-200020162928 and ERC-2017-AdG-786580-MACI.</footnote>
# 1 Introduction

In their work about the parameterized complexity of counting problems [11] Flum and Grohe introduced the parameterized analogue of the theory of computational counting as layed out by Valiant in his seminal paper about the complexity of computing the permanent [28]. Since then parameterized counting has evolved into a well-studied subfield of parameterized complexity theory. In particular, there has been remarkable progress in the classification of problems that require to count small structures in large graphs. It turned out that many families of such counting problems allow so-called dichotomy results, that is, every problem in the family is either fixed-parameter tractable or hard for the class #W[1] — the counting equivalent of W[1]. One result of that kind is the dichotomy for counting homomorphisms [10, 13]. Here one is given a graph $H$ from a class of graphs $\mathcal{H}$ and an arbitrary graph $G$ and the task is to compute the number of homomorphisms from $H$ to $G$. When parameterized by $|H|$ this problem is fixed-parameter tractable if there exists a constant upper bound on the treewidth of graphs in $\mathcal{H}$ and #W[1]-hard otherwise. Similar results have been shown for the problems of counting subgraph embeddings [9], induced subgraphs [7] and locally injective homomorphisms [26]. As results like Ladner's theorem (see e.g. [19, 2]) rule out such dichotomies in the general case one might ask why all of the above problems indeed do allow such complexity classifications. The answer to that question was given very recently by Curticapean, Dell and Marx [8] who proved that, in some sense, all of those problems are the same. To this end, they defined the problem of computing linear combinations of homomorphisms which they called *graph motif parameters*. Here one is given a graph $G$ and a function $a$ of finite support that maps graphs to rational numbers and the task is to compute

$$ \sum_H a(H) \cdot \#\mathrm{Hom}(H, G), \qquad (1) $$

where the sum is over all (unlabeled) simple graphs and $\#\mathrm{Hom}(H, G)$ denotes the number of homomorphisms from $H$ to $G$. A result of Lovász (see e.g. Chapt. 5 in [20]) implies that the number of subgraph embeddings $\#\mathrm{Emb}(H, G)$ as well as the number of induced subgraphs $\#\mathrm{IndSub}(H, G)$ can be expressed as a linear combination of homomorphisms. In case of embeddings the result states that

$$ \#\mathrm{Emb}(H, G) = \sum_{\rho \ge \emptyset} \mu(\emptyset, \rho) \cdot \#\mathrm{Hom}(H/\rho, G), \qquad (2) $$

where the sum is over the partition lattice of the vertices of $H$, $\mu$ is the Möbius function over that lattice and $H/\rho$ is obtained from $H$ by identifying vertices along $\rho$. Now, intuitively, the main result of Curticapean, Dell and Marx states that computing a linear combination of homomorphisms is precisely as hard as computing the hardest term in the linear combination. Together with the dichotomy for counting homomorphisms this implies that every problem expressible as a linear combination of homomorphisms is either fixed-parameter tractable or #W[1]-hard. The purpose of this work is a thorough investigation of the problem of counting induced subgraphs through the lens of the framework of graph motif parameters. Chen, Thurley and Weyer [7] proved that the problem $\#\mathrm{IndSub}(\mathcal{H})$ of, given a graph $H \in \mathcal{H}$ and an arbitrary graph $G$, computing $\#\mathrm{IndSub}(H, G)$, is fixed-parameter tractable when parameterized by $|H|$ if and only if $\mathcal{H}$ is finite and #W[1]-hard otherwise. While this result resolves the parameterized complexity of problems such as computing the number of induced
# 1 Introduction

In their work about the parameterized complexity of counting problems [11] Flum and Grohe introduced the parameterized analogue of the theory of computational counting as layed out by Valiant in his seminal paper about the complexity of computing the permanent [28]. Since then parameterized counting has evolved into a well-studied subfield of parameterized complexity theory. In particular, there has been remarkable progress in the classification of problems that require to count small structures in large graphs. It turned out that many families of such counting problems allow so-called dichotomy results, that is, every problem in the family is either fixed-parameter tractable or hard for the class #W[1] — the counting equivalent of W[1]. One result of that kind is the dichotomy for counting homomorphisms [10, 13]. Here one is given a graph $H$ from a class of graphs $\mathcal{H}$ and an arbitrary graph $G$ and the task is to compute the number of homomorphisms from $H$ to $G$. When parameterized by $|H|$ this problem is fixed-parameter tractable if there exists a constant upper bound on the treewidth of graphs in $\mathcal{H}$ and #W[1]-hard otherwise. Similar results have been shown for the problems of counting subgraph embeddings [9], induced subgraphs [7] and locally injective homomorphisms [26]. As results like Ladner's theorem (see e.g. [19, 2]) rule out such dichotomies in the general case one might ask why all of the above problems indeed do allow such complexity classifications. The answer to that question was given very recently by Curticapean, Dell and Marx [8] who proved that, in some sense, all of those problems are the same. To this end, they defined the problem of computing linear combinations of homomorphisms which they called graph motif parameters. Here one is given a graph $G$ and a function $a$ of finite support that maps graphs to rational numbers and the task is to compute

$$ \sum_{H} a(H) \cdot \#\mathrm{Hom}(H, G), \qquad (1) $$

where the sum is over all (unlabeled) simple graphs and $\#\mathrm{Hom}(H, G)$ denotes the number of homomorphisms from $H$ to $G$. A result of Lovász (see e.g. Chapt. 5 in [20]) implies that the number of subgraph embeddings $\#\mathrm{Emb}(H, G)$ as well as the number of induced subgraphs $\#\mathrm{IndSub}(H, G)$ can be expressed as a linear combination of homomorphisms. In case of embeddings the result states that

$$ \#\mathrm{Emb}(H, G) = \sum_{\rho \ge \emptyset} \mu(\emptyset, \rho) \cdot \#\mathrm{Hom}(H/\rho, G), \qquad (2) $$

where the sum is over the partition lattice of the vertices of $H$, $\mu$ is the Möbius function over that lattice and $H/\rho$ is obtained from $H$ by identifying vertices along $\rho$. Now, intuitively, the main result of Curticapean, Dell and Marx states that computing a linear combination of homomorphisms is precisely as hard as computing the hardest term in the linear combination. Together with the dichotomy for counting homomorphisms this implies that every problem expressible as a linear combination of homomorphisms is either fixed-parameter tractable or #W[1]-hard. The purpose of this work is a thorough investigation of the problem of counting induced subgraphs through the lens of the framework of graph motif parameters. Chen, Thurley and Weyer [7] proved that the problem $\#\mathrm{IndSub}(\mathcal{H})$ of, given a graph $H \in \mathcal{H}$ and an arbitrary graph $G$, computing $\#\mathrm{IndSub}(H, G)$, is fixed-parameter tractable when parameterized by $|H|$ if and only if $\mathcal{H}$ is finite and #W[1]-hard otherwise. While this result resolves the parameterized complexity of problems such as computing the number of induced
cycles of length $k$,<fnref n="2" /> it is not applicable to problems such as computing the number of connected induced subgraphs of size $k$. For this reason, Jerrum and Meeks [15, 14, 22, 16] introduced and studied the following problem: Let $\Phi$ be a (computable) graph property, then the problem #IndSub($\Phi$) asks, given a graph $G$ and a natural number $k$, to count all induced subgraphs of size $k$ in $G$ that satisfy $\Phi$.<fnref n="3" /> In other words, the goal is to compute $\sum_{H \in \Phi_k} \#\text{IndSub}(H, G)$, where $\Phi_k$ is the set of all (unlabeled) graphs with $k$ vertices that satisfy $\Phi$. The generality of #IndSub($\Phi$) allows to count almost arbitrary substructures in graphs, subsuming lots of parameterized counting problems that have been studied before, and hence the problem deserves a thorough complexity analysis with respect to the property $\Phi$. Jerrum and Meeks proved it to be #W[1]-hard for the property of connectivity [15], for the property of having an even (or odd) number of edges [16] as well as for some other properties (see Section 1.2). As noted in [8], the theory of graph motif parameters immediately implies that for every property $\Phi$, the problem #IndSub($\Phi$) is either fixed-parameter tractable or #W[1]-hard. However, for a concrete $\Phi$ it might be highly non-trivial to prove for which graphs $H$ the term #Hom($H$, $G$) is contained with a non-zero coefficient in the equivalent expression as linear combination of homomorphisms. Unfortunately, this is precisely what needs to be done to find out whether #IndSub($\Phi$) is fixed-parameter tractable or #W[1]-hard. In our investigation we will focus on the coefficient of #Hom($K_k$, $G$), where $K_k$ is the complete graph on $k$ vertices. We will see that for monotone properties, non-zeroness of this coefficient is sufficient for the property to be evasive.

## 1.1 Results and techniques

The framework of graph motif parameters [8] implies that for every property $\Phi$ and natural number $k$, there exists a function $a$ from graphs to rationals such that for all graphs $G$ it holds that $\sum_{H \in \Phi_k} \#\text{IndSub}(H, G) = \sum_H a(H) \cdot \#\text{Hom}(H, G)$. Our most important observation is concerned with the coefficient of the complete graph.

**► Theorem 1 (Intuitive version).** Let $\Phi$, $k$ and $a$ be as above. Then it holds that $a(K_k) = 0$ if and only if $\sum_{A \in E_k^\Phi} (-1)^{#A} = 0$, where $E_k^\Phi$ is the set of all edge-subsets $A$ of the labeled complete graph with $k$ vertices such that $\Phi$ holds for the graph induced by $A$.

We will provide an introduction to the theory of graph motif parameters as well as the proof of Theorem 1 in Section 3. In Section 4 we turn towards monotone properties, i.e., properties that are closed under the removal of edges, and observe that in this case the term $\sum_{A \in E_k^\Phi} (-1)^{#A}$ is equal to the reduced Euler characteristic $\hat{\chi}$ of the simplicial graph complex $\Delta(\Phi_k)$ of $\Phi_k$. Recall that a simplicial complex is a set of sets that is closed under taking non-empty subsets and a simplicial graph complex is a simplicial complex whose elements are subsets of the edges of the labeled complete graph. We will make this formal in Section 2. As computing the number of cliques of size $k$ is #W[1]-complete [11] and computing a linear combination of homomorphisms is precisely as hard as computing its hardest term [8], the complexity of #IndSub($\Phi$) is resolved whenever $\Phi$ is monotone and the reduced Euler characteristic of $\Delta(\Phi_k)$ is known to be non-zero for infinitely many $k$.

<footnote n="2">² This problem can be equivalently expressed as #IndSub($C$), where $C$ is the class of all cycles.</footnote>

<footnote n="3">³ Strictly speaking, #IndSub($\Phi$) is the unlabeled version of p-#INDUCED SUBGRAPH WITH PROPERTY($\Phi$), both of which have been introduced in [15]. However, as Jerrum and Meeks point out, those problems are equivalent for graph properties that are invariant under relabeling of vertices (see Section 1.3.1 in [15]), which is true for all properties we are concerned with in this work.</footnote>
cycles of length $k$,<fnref n="2" /> it is not applicable to problems such as computing the number of connected induced subgraphs of size $k$. For this reason, Jerrum and Meeks [15, 14, 22, 16] introduced and studied the following problem: Let $\Phi$ be a (computable) graph property, then the problem #IndSub($\Phi$) asks, given a graph $G$ and a natural number $k$, to count all induced subgraphs of size $k$ in $G$ that satisfy $\Phi$.<fnref n="3" /> In other words, the goal is to compute $\sum_{H \in \Phi_k} \#\text{IndSub}(H, G)$, where $\Phi_k$ is the set of all (unlabeled) graphs with $k$ vertices that satisfy $\Phi$. The generality of #IndSub($\Phi$) allows to count almost arbitrary substructures in graphs, subsuming lots of parameterized counting problems that have been studied before, and hence the problem deserves a thorough complexity analysis with respect to the property $\Phi$. Jerrum and Meeks proved it to be #W[1]-hard for the property of connectivity [15], for the property of having an even (or odd) number of edges [16] as well as for some other properties (see Section 1.2). As noted in [8], the theory of graph motif parameters immediately implies that for every property $\Phi$, the problem #IndSub($\Phi$) is either fixed-parameter tractable or #W[1]-hard. However, for a concrete $\Phi$ it might be highly non-trivial to prove for which graphs $H$ the term #Hom($H$, $G$) is contained with a non-zero coefficient in the equivalent expression as linear combination of homomorphisms. Unfortunately, this is precisely what needs to be done to find out whether #IndSub($\Phi$) is fixed-parameter tractable or #W[1]-hard. In our investigation we will focus on the coefficient of #Hom($K_k$, $G$), where $K_k$ is the complete graph on $k$ vertices. We will see that for monotone properties, non-zeroness of this coefficient is sufficient for the property to be evasive.

## 1.1 Results and techniques

The framework of graph motif parameters [8] implies that for every property $\Phi$ and natural number $k$, there exists a function $a$ from graphs to rationals such that for all graphs $G$ it holds that $\sum_{H \in \Phi_k} \#\text{IndSub}(H, G) = \sum_H a(H) \cdot \#\text{Hom}(H, G)$. Our most important observation is concerned with the coefficient of the complete graph.

**► Theorem 1 (Intuitive version).** Let $\Phi$, $k$ and $a$ be as above. Then it holds that $a(K_k) = 0$ if and only if $\sum_{A \in E_k^\Phi} (-1)^{#A} = 0$, where $E_k^\Phi$ is the set of all edge-subsets $A$ of the labeled complete graph with $k$ vertices such that $\Phi$ holds for the graph induced by $A$.

We will provide an introduction to the theory of graph motif parameters as well as the proof of Theorem 1 in Section 3. In Section 4 we turn towards monotone properties, i.e., properties that are closed under the removal of edges, and observe that in this case the term $\sum_{A \in E_k^\Phi} (-1)^{#A}$ is equal to the reduced Euler characteristic $\hat{\chi}$ of the simplicial graph complex $\Delta(\Phi_k)$ of $\Phi_k$. Recall that a simplicial complex is a set of sets that is closed under taking non-empty subsets and a simplicial graph complex is a simplicial complex whose elements are subsets of the edges of the labeled complete graph. We will make this formal in Section 2. As computing the number of cliques of size $k$ is #W[1]-complete [11] and computing a linear combination of homomorphisms is precisely as hard as computing its hardest term [8], the complexity of #IndSub($\Phi$) is resolved whenever $\Phi$ is monotone and the reduced Euler characteristic of $\Delta(\Phi_k)$ is known to be non-zero for infinitely many $k$.

<footnote n="2">² This problem can be equivalently expressed as #IndSub($C$), where $C$ is the class of all cycles.</footnote>

<footnote n="3">³ Strictly speaking, #IndSub($\Phi$) is the unlabeled version of p-#INDUCED SUBGRAPH WITH PROPERTY($\Phi$), both of which have been introduced in [15]. However, as Jerrum and Meeks point out, those problems are equivalent for graph properties that are invariant under relabeling of vertices (see Section 1.3.1 in [15]), which is true for all properties we are concerned with in this work.</footnote>
**Corollary 2.** Let $\Phi$ be a monotone graph property such that $\hat{\chi}(\Delta(\Phi_k)) \neq 0$ for infinitely many $k$. Then the problem #IndSub($\Phi$) is #W[1]-hard.

We will also obtain a matching lower bound under the Exponential Time Hypothesis (ETH) if the set of all $k$ for which $\hat{\chi}(\Delta(\Phi_k)) \neq 0$ satisfies a certain density condition (see Section 2).

The (reduced) Euler characteristic is well-understood for many graph complexes. For example, Chapt. 10.5 in the book of Jonsson [17] provides a large list of graph properties, each of whose reduced Euler characteristics are non-zero infinitely often. For those properties Corollary 2 is hence applicable. The study of the (reduced) Euler characteristic is, among others, motivated by Karp's famous evasiveness conjecture, stating that every non-trivial monotone graph property is evasive. A property $\Phi_k$ on graphs with $k$ vertices is evasive if every decision-tree algorithm that branches on the presence or absence of edges of a given graph $G$ needs to perform $\binom{k}{2}$ branches in the worst case to correctly decide whether $\Phi_k$ holds on $G$. We refer the reader to Miller's survey [23] for a detailed introduction. While the conjecture is still unresolved, there has been a major breakthrough due to Khan, Saks and Sturtevant [18] who proved the conjecture to be true whenever $k$ is a prime power. Their paper "A Topological Approach to Evasiveness" was, as the name suggests, the first one to use topological tools such as fixed-point complexes under group operations to prove evasiveness of a given graph complex. One of their results reads as follows:

**Theorem 3 ([18]<fnref n="4" />).** Let $\Phi_k$ be a non-trivial monotone graph property. If $\hat{\chi}(\Delta(\Phi_k)) \neq 0$ then $\Phi_k$ is evasive.

Unfortunately, the converse of this theorem does not hold. A counterexample is given in Chapt. 10.6 in Jonsson's book [17]. Nevertheless it turns out that some tools of the topological approach to evasiveness suit as well for a topological approach to #W[1]-hardness of #IndSub($\Phi$). The most important ingredient in our proofs is a theorem that goes back to Smith [27] (see also [24] and Chapt. 3 in [3]), intuitively stating that, given a simplicial complex $\Delta$ and a $p$-power group $\Gamma$ for some prime $p$ that operates on the ground set of $\Delta$ in a way that leaves the complex stable, it holds that $\hat{\chi}(\Delta) \equiv \hat{\chi}(\Delta^\Gamma) \mod p$, where $\Delta^\Gamma$ is the fixed-point complex of $\Delta$ with respect to $\Gamma$. Again, this will be made formal in Section 2. Applying this theorem to a rather simple group, we will be able to prove our main result which reads as follows:

**Theorem 4.** Let $\Phi$ be a non-trivial monotone graph property. Then #IndSub($\Phi$) is #W[1]-hard and, assuming ETH, can not be solved in time $f(k) \cdot n^{o(k)}$ for any computable function $f$ if at least one of the following conditions is true

1. $\Phi$ is false for odd cycles.

2. $\Phi$ is true for odd anti-holes.

3. There exists $c \in \mathbb{N}$ such that for all $H$ it holds that $\Phi(H) = 1$ if and only if $H$ is not $c$-edge-connected.

4. There exists a graph $F$ such that for all $H$ it holds that $\Phi(H) = 1$ if and only if there is no homomorphism from $F$ to $H$.

We remark that Rivest and Vuillemin [25] implicitly proved that the reduced Euler characteristic of a graph complex does not vanish if the first condition is true. Furthermore

<footnote n="4">⁴ In fact, Khan, Saks and Sturtevant show that any non-evasive complex is collapsible. However, every collapsible complex has a reduced Euler characteristic of zero (see e.g. [21]). Hence the contraposition implies the theorem as stated.</footnote>
**Corollary 2.** Let $\Phi$ be a monotone graph property such that $\hat{\chi}(\Delta(\Phi_k)) \neq 0$ for infinitely many $k$. Then the problem #IndSub($\Phi$) is #W[1]-hard.

We will also obtain a matching lower bound under the Exponential Time Hypothesis (ETH) if the set of all $k$ for which $\hat{\chi}(\Delta(\Phi_k)) \neq 0$ satisfies a certain density condition (see Section 2).

The (reduced) Euler characteristic is well-understood for many graph complexes. For example, Chapt. 10.5 in the book of Jonsson [17] provides a large list of graph properties, each of whose reduced Euler characteristics are non-zero infinitely often. For those properties Corollary 2 is hence applicable. The study of the (reduced) Euler characteristic is, among others, motivated by Karp's famous evasiveness conjecture, stating that every non-trivial monotone graph property is evasive. A property $\Phi_k$ on graphs with $k$ vertices is evasive if every decision-tree algorithm that branches on the presence or absence of edges of a given graph $G$ needs to perform $\binom{k}{2}$ branches in the worst case to correctly decide whether $\Phi_k$ holds on $G$. We refer the reader to Miller's survey [23] for a detailed introduction. While the conjecture is still unresolved, there has been a major breakthrough due to Khan, Saks and Sturtevant [18] who proved the conjecture to be true whenever $k$ is a prime power. Their paper "A Topological Approach to Evasiveness" was, as the name suggests, the first one to use topological tools such as fixed-point complexes under group operations to prove evasiveness of a given graph complex. One of their results reads as follows:

**Theorem 3 ([18]<fnref n="4" />).** Let $\Phi_k$ be a non-trivial monotone graph property. If $\hat{\chi}(\Delta(\Phi_k)) \neq 0$ then $\Phi_k$ is evasive.

Unfortunately, the converse of this theorem does not hold. A counterexample is given in Chapt. 10.6 in Jonsson's book [17]. Nevertheless it turns out that some tools of the topological approach to evasiveness suit as well for a topological approach to #W[1]-hardness of #IndSub($\Phi$). The most important ingredient in our proofs is a theorem that goes back to Smith [27] (see also [24] and Chapt. 3 in [3]), intuitively stating that, given a simplicial complex $\Delta$ and a $p$-power group $\Gamma$ for some prime $p$ that operates on the ground set of $\Delta$ in a way that leaves the complex stable, it holds that $\hat{\chi}(\Delta) \equiv \hat{\chi}(\Delta^\Gamma) \mod p$, where $\Delta^\Gamma$ is the fixed-point complex of $\Delta$ with respect to $\Gamma$. Again, this will be made formal in Section 2. Applying this theorem to a rather simple group, we will be able to prove our main result which reads as follows:

**Theorem 4.** Let $\Phi$ be a non-trivial monotone graph property. Then #IndSub($\Phi$) is #W[1]-hard and, assuming ETH, can not be solved in time $f(k) \cdot n^{o(k)}$ for any computable function $f$ if at least one of the following conditions is true

1. $\Phi$ is false for odd cycles.

2. $\Phi$ is true for odd anti-holes.

3. There exists $c \in \mathbb{N}$ such that for all $H$ it holds that $\Phi(H) = 1$ if and only if $H$ is not $c$-edge-connected.

4. There exists a graph $F$ such that for all $H$ it holds that $\Phi(H) = 1$ if and only if there is no homomorphism from $F$ to $H$.

We remark that Rivest and Vuillemin [25] implicitly proved that the reduced Euler characteristic of a graph complex does not vanish if the first condition is true. Furthermore

<footnote n="4">⁴ In fact, Khan, Saks and Sturtevant show that any non-evasive complex is collapsible. However, every collapsible complex has a reduced Euler characteristic of zero (see e.g. [21]). Hence the contraposition implies the theorem as stated.</footnote>
we note that (non-)triviality of a monotone property needs to be defined with some care to exclude properties that depend only on the number of vertices of a graph. Details are given in Section 4. Examples of properties that satisfy the first condition are the ones of being bipartite, cycle-free, disconnected and non-hamiltonian. One example for the second condition is the property of having a chromatic number smaller or equal than half of the size of the graph (rounded up) and the third condition includes the properties of exclusion of a fixed complete graph as a subgraph.

In Section 5 we turn to non-monotone properties and illustrate that Theorem 1 itself is a useful criterion when it comes to establishing #W[1]-hardness of #IndSub($\Phi$). In particular, we will prove hardness whenever $\Phi$ is a non-trivial modularity constraint on the number of edges with respect to some prime or if $\Phi$ enforces the presence of a fixed isolated subgraph.

## 1.2 Related work

Jerrum and Meeks introduced and studied the problem #IndSub($\Phi$) for the following properties. In [15] they prove the problem to be #W[1]-hard if $\Phi$ is the property of being connected, which immediately follows from Theorem 4 as #IndSub($\Phi$) and #IndSub($\neg\Phi$) are equivalent<fnref n="5" /> and the property of being disconnected is monotone and false for every cycle. In [16] hardness is established for the property of having an even (or odd) number of edges, which follows from Theorem 1 as every term in the sum $\sum_{A \in E_k^\Phi} (-1)^{\#A}$ will have the same sign. In [14] Jerrum and Meeks prove the problem to be #W[1]-hard whenever the edge-density of graphs in $\Phi_k$ grows asymptotically slower than $k^2$ and in [22] Meeks shows that whenever $\Phi$ is co-monotone, i.e., $\neg\Phi$ is monotone, and the set of (edge-)minimal elements of $\Phi$ has unbounded treewidth, the problem is hard as well. Those latter results are independent from ours in the sense that ours do not imply theirs and vice versa. One example of a property whose hardness does not follow from the results of Jerrum and Meeks is bipartiteness: The edge-densities of both, the properties of being bipartite and not bipartite grow asymptotically as fast as $k^2$ and the edge-minimal non-bipartite graphs are odd cycles, hence having treewidth 2. However hardness for the property of being bipartite follows from the first condition of Theorem 4 as odd cycles are not bipartite. Moreover, we point out that Meeks' reduction in [22] uses the Excluded Grid Theorem and hence does not imply a tight lower bound under ETH. Finally we remark that due to space constraints some proofs are only sketched or omitted and we refer the interested reader to the related version of this paper.

# 2 Preliminaries

First we will introduce some basic notions. Given a finite set $S$, we write #S for the cardinality of $S$. We say that a set $\mathcal{K}$ of natural numbers is dense if there exists a constant $c > 0$ such that for all but finitely many $k \in \mathbb{N}$ there exists $k' \in \mathcal{K}$ such that $k \le k' \le c \cdot k$. Given a function $a$ from a (not necessarily finite) set $S$ to rational numbers, the support of $a$ is the set of elements $s \in S$ such that $a(s) \ne 0$. We write $\text{supp}(a)$ for the support of $a$. Given a natural number $k$, we write $[k]$ for the set $\{0, \dots, k - 1\}$. Given a finite group $\Gamma$ of order $p^s$ for some prime $p$ and natural number $s$, we say that $\Gamma$ is a *p-power group*.

<footnote n="5">⁵ We just need to subtract one from $\binom{n}{k}$ to get the other.</footnote>
we note that (non-)triviality of a monotone property needs to be defined with some care to exclude properties that depend only on the number of vertices of a graph. Details are given in Section 4. Examples of properties that satisfy the first condition are the ones of being bipartite, cycle-free, disconnected and non-hamiltonian. One example for the second condition is the property of having a chromatic number smaller or equal than half of the size of the graph (rounded up) and the third condition includes the properties of exclusion of a fixed complete graph as a subgraph.

In Section 5 we turn to non-monotone properties and illustrate that Theorem 1 itself is a useful criterion when it comes to establishing #W[1]-hardness of #IndSub($\Phi$). In particular, we will prove hardness whenever $\Phi$ is a non-trivial modularity constraint on the number of edges with respect to some prime or if $\Phi$ enforces the presence of a fixed isolated subgraph.

## 1.2 Related work

Jerrum and Meeks introduced and studied the problem #IndSub($\Phi$) for the following properties. In [15] they prove the problem to be #W[1]-hard if $\Phi$ is the property of being connected, which immediately follows from Theorem 4 as #IndSub($\Phi$) and #IndSub($\neg\Phi$) are equivalent<fnref n="5" /> and the property of being disconnected is monotone and false for every cycle. In [16] hardness is established for the property of having an even (or odd) number of edges, which follows from Theorem 1 as every term in the sum $\sum_{A \in E_k^\Phi} (-1)^{\#A}$ will have the same sign. In [14] Jerrum and Meeks prove the problem to be #W[1]-hard whenever the edge-density of graphs in $\Phi_k$ grows asymptotically slower than $k^2$ and in [22] Meeks shows that whenever $\Phi$ is co-monotone, i.e., $\neg\Phi$ is monotone, and the set of (edge-)minimal elements of $\Phi$ has unbounded treewidth, the problem is hard as well. Those latter results are independent from ours in the sense that ours do not imply theirs and vice versa. One example of a property whose hardness does not follow from the results of Jerrum and Meeks is bipartiteness: The edge-densities of both, the properties of being bipartite and not bipartite grow asymptotically as fast as $k^2$ and the edge-minimal non-bipartite graphs are odd cycles, hence having treewidth 2. However hardness for the property of being bipartite follows from the first condition of Theorem 4 as odd cycles are not bipartite. Moreover, we point out that Meeks' reduction in [22] uses the Excluded Grid Theorem and hence does not imply a tight lower bound under ETH. Finally we remark that due to space constraints some proofs are only sketched or omitted and we refer the interested reader to the related version of this paper.

# 2 Preliminaries

First we will introduce some basic notions. Given a finite set $S$, we write #S for the cardinality of $S$. We say that a set $\mathcal{K}$ of natural numbers is dense if there exists a constant $c > 0$ such that for all but finitely many $k \in \mathbb{N}$ there exists $k' \in \mathcal{K}$ such that $k \le k' \le c \cdot k$. Given a function $a$ from a (not necessarily finite) set $S$ to rational numbers, the support of $a$ is the set of elements $s \in S$ such that $a(s) \neq 0$. We write $\text{supp}(a)$ for the support of $a$. Given a natural number $k$, we write $[k]$ for the set $\{0, \dots, k - 1\}$. Given a finite group $\Gamma$ of order $p^s$ for some prime $p$ and natural number $s$, we say that $\Gamma$ is a *p-power group*.

<footnote n="5">⁵ We just need to subtract one from $\binom{n}{k}$ to get the other.</footnote>
## Graph theory

In this work all graphs are considered to be undirected, simple and to not contain self-loops. Given a graph $G$ we write $V(G)$ for the vertices and $E(G)$ for the edges of $G$. We denote the complete graph on $\ell$ vertices as $K_\ell$. A labeled graph is a graph $G$ with a bijective labeling $\ell: V(G) \to [\#V(G)]$ of the vertices and we will sloppily identify vertices with their labels. A subgraph of $G$ is a graph obtained from $G$ by deleting vertices (including incident edges) and/or edges. Given a subset $S \subseteq V(G)$, the induced subgraph $G[S]$ is the graph with vertices $S$ and edges $E(G) \cap S^2$. A homomorphism from a graph $H$ to a graph $G$ is a function $\varphi: V(H) \to V(G)$ that is edge-preserving, i.e. for every edge $\{u, v\} \in E(H)$ it holds that $\{\varphi(u), \varphi(v)\} \in E(G)$. We write $\text{Hom}(H, G)$ for the set of all homomorphisms from $H$ to $G$. A homomorphism $\varphi$ is called an embedding if $\varphi$ is injective. We write $\text{Emb}(H, G)$ for the set of all embeddings from $H$ to $G$. An isomorphism from a graph $H$ to a graph $G$ is a bijective homomorphism. We say that $H$ and $G$ are isomorphic, denoted by $H \cong G$, if such an isomorphism exists and we denote $\mathcal{G}$ as the set of all (isomorphism types of) graphs. An automorphism of a graph $H$ is an isomorphism from $H$ to $H$. We write $\text{Aut}(H)$ for the set of all automorphisms of $H$. An embedding $\varphi$ from $H$ to $G$ is called a strong embedding if for all vertices $u, v \in V(H)$ it holds that $\{u, v\} \in E(H) \Leftrightarrow \{\varphi(u), \varphi(v)\} \in E(G)$. We write $\text{StrEmb}(H, G)$ for the set of all strong embeddings from $H$ to $G$. Given graphs $H$ and $G$, we write $\text{Sub}(H, G)$ for the set of all subgraphs of $G$ that are isomorphic to $H$ and $\text{IndSub}(H, G)$ for the set of all induced subgraphs of $G$ that are isomorphic to $H$.

**Fact 5.** For all graphs $H$ and $G$ it holds that $\#\text{Emb}(H, G) = \#\text{Sub}(H, G) \cdot \#\text{Aut}(H)$ and that $\#\text{StrEmb}(H, G) = \#\text{IndSub}(H, G) \cdot \#\text{Aut}(H)$.

A graph property $\Phi$ is a function from graphs to $\{0, 1\}$ such that $\Phi(G) = \Phi(G')$ whenever $G$ and $G'$ are isomorphic. We say that $\Phi$ holds on $G$ if $\Phi(G) = 1$ and we are not going not distinguish between $\Phi$ and the set of graphs for which $\Phi$ holds as this will be clear from the context. We write $\Phi_k$ for the set of all (isomorphism types of) graphs with $k$ vertices on which $\Phi$ holds. For technical reasons we define $E_k^\Phi$ to be the set of all edge-subsets $A$ of the labeled complete graph with $k$ vertices such that $\Phi$ holds on the graph with the same vertices and edges $A$. A graph property is called monotone if it is closed under the removal of edges, that is, if $G'$ is obtained from $G$ by removing edges and $\Phi$ holds for $G$, then $\Phi$ holds for $G'$ as well. A property is called co-monotone if its complement is monotone$^6$.

## Transformation groups and simplicial (graph) complexes

Let $\Omega$ be a finite set. A simplicial complex over the ground set $\Omega$ is a set $\Delta$ of non-empty subsets of $\Omega$ such that whenever a set $A$ is contained in $\Delta$ and $A'$ is a non-empty subset of $A$, then $A'$ is contained in $\Delta$ as well. An element $A$ of $\Delta$ is called a simplex and the dimension of $A$, denoted as $\dim(A)$, is defined to be $\#A - 1$. The Euler characteristic $\chi$ of a simplicial complex $\Delta$ is defined to be $\chi(\Delta) := \sum_{i \ge 0} (-1)^i \cdot \#\{A \in \Delta \mid \dim(A) = i\}$ and the reduced Euler characteristic of $\Delta$ is defined to be $\hat{\chi}(\Delta) := 1 - \chi(\Delta)$.

**Fact 6.** $\hat{\chi}(\Delta) = \sum_{i \ge 0} (-1)^i \cdot \#\{A \in \Delta \cup \{\emptyset\} \mid \#A = i\}$.

Given a simplicial complex $\Delta$ and a finite group $\Gamma$ that operates on the ground set $\Omega$ of $\Delta$, we say that $\Delta$ is a $\Gamma$-simplicial complex if the induced action of $\Gamma$ on subsets of $\Omega$

<footnote n="6">⁶ We remark that in some literature, e.g. [22, 25], the notions of monotonicity and co-monotonicity are reversed.</footnote>
## Graph theory

In this work all graphs are considered to be undirected, simple and to not contain self-loops. Given a graph $G$ we write $V(G)$ for the vertices and $E(G)$ for the edges of $G$. We denote the complete graph on $l$ vertices as $K_l$. A labeled graph is a graph $G$ with a bijective labeling $l: V(G) \to [\#V(G)]$ of the vertices and we will sloppily identify vertices with their labels. A subgraph of $G$ is a graph obtained from $G$ by deleting vertices (including incident edges) and/or edges. Given a subset $S \subseteq V(G)$, the induced subgraph $G[S]$ is the graph with vertices $S$ and edges $E(G) \cap S^2$. A homomorphism from a graph $H$ to a graph $G$ is a function $\varphi: V(H) \to V(G)$ that is edge-preserving, i.e. for every edge $\{u, v\} \in E(H)$ it holds that $\{\varphi(u), \varphi(v)\} \in E(G)$. We write $\text{Hom}(H, G)$ for the set of all homomorphisms from $H$ to $G$. A homomorphism $\varphi$ is called an embedding if $\varphi$ is injective. We write $\text{Emb}(H, G)$ for the set of all embeddings from $H$ to $G$. An isomorphism from a graph $H$ to a graph $G$ is a bijective homomorphism. We say that $H$ and $G$ are isomorphic, denoted by $H \cong G$, if such an isomorphism exists and we denote $\mathcal{G}$ as the set of all (isomorphism types of) graphs. An automorphism of a graph $H$ is an isomorphism from $H$ to $H$. We write $\text{Aut}(H)$ for the set of all automorphisms of $H$. An embedding $\varphi$ from $H$ to $G$ is called a strong embedding if for all vertices $u, v \in V(H)$ it holds that $\{u, v\} \in E(H) \Leftrightarrow \{\varphi(u), \varphi(v)\} \in E(G)$. We write $\text{StrEmb}(H, G)$ for the set of all strong embeddings from $H$ to $G$. Given graphs $H$ and $G$, we write $\text{Sub}(H, G)$ for the set of all subgraphs of $G$ that are isomorphic to $H$ and $\text{IndSub}(H, G)$ for the set of all induced subgraphs of $G$ that are isomorphic to $H$.

**Fact 5.** For all graphs $H$ and $G$ it holds that $\#\text{Emb}(H, G) = \#\text{Sub}(H, G) \cdot \#\text{Aut}(H)$ and that $\#\text{StrEmb}(H, G) = \#\text{IndSub}(H, G) \cdot \#\text{Aut}(H)$.

A graph property $\Phi$ is a function from graphs to $\{0, 1\}$ such that $\Phi(G) = \Phi(G')$ whenever $G$ and $G'$ are isomorphic. We say that $\Phi$ holds on $G$ if $\Phi(G) = 1$ and we are not going not distinguish between $\Phi$ and the set of graphs for which $\Phi$ holds as this will be clear from the context. We write $\Phi_k$ for the set of all (isomorphism types of) graphs with $k$ vertices on which $\Phi$ holds. For technical reasons we define $E_k^\Phi$ to be the set of all edge-subsets $A$ of the labeled complete graph with $k$ vertices such that $\Phi$ holds on the graph with the same vertices and edges $A$. A graph property is called *monotone* if it is closed under the removal of edges, that is, if $G'$ is obtained from $G$ by removing edges and $\Phi$ holds for $G$, then $\Phi$ holds for $G'$ as well. A property is called *co-monotone* if its complement is monotone$^6$.

## Transformation groups and simplicial (graph) complexes

Let $\Omega$ be a finite set. A simplicial complex over the ground set $\Omega$ is a set $\Delta$ of non-empty subsets of $\Omega$ such that whenever a set $A$ is contained in $\Delta$ and $A'$ is a non-empty subset of $A$, then $A'$ is contained in $\Delta$ as well. An element $A$ of $\Delta$ is called a simplex and the dimension of $A$, denoted as $\dim(A)$, is defined to be $\#A - 1$. The Euler characteristic $\chi$ of a simplicial complex $\Delta$ is defined to be $\chi(\Delta) := \sum_{i \ge 0} (-1)^i \cdot \#\{A \in \Delta \mid \dim(A) = i\}$ and the reduced Euler characteristic of $\Delta$ is defined to be $\hat{\chi}(\Delta) := 1 - \chi(\Delta)$.

**Fact 6.** $\hat{\chi}(\Delta) = \sum_{i \ge 0} (-1)^i \cdot \#\{A \in \Delta \cup \{\emptyset\} \mid \#A = i\}$.

Given a simplicial complex $\Delta$ and a finite group $\Gamma$ that operates on the ground set $\Omega$ of $\Delta$, we say that $\Delta$ is a $\Gamma$-simplicial complex if the induced action of $\Gamma$ on subsets of $\Omega$

<footnote>$^6$ We remark that in some literature, e.g. [22, 25], the notions of monotonicity and co-monotonicity are reversed.</footnote>
preserves $\Delta$. More precisely, if $A \in \Delta$ and $g \in \Gamma$ then the set $g \triangleright A := \{g \triangleright a \mid a \in A\}$ is contained in $\Delta$ as well. If this is the case we can define the fixed-point complex $\Delta^{\Gamma}$ as follows. Let $O_1, \dots, O_k$ be the orbits of $\Omega$ with respect to $\Gamma$. Then

$$ \Delta^{\Gamma} := \left\{ S \subseteq \{1, \dots, k\} \mid S \neq \emptyset \wedge \bigcup_{i \in S} O_i \in \Delta \right\} $$

The following theorem, which is due to Smith [27] (see also [24] and Chapt. 3 in [3]), will be of crucial importance in Section 4.

**► Theorem 7.** Let $\Gamma$ a group of order $p^s$ for some prime $p$ and natural number $s$ and let $\Delta$ be a $\Gamma$-simplicial complex. Then $\chi(\Delta) \equiv \chi(\Delta^{\Gamma}) \mod p$ and hence $\hat{\chi}(\Delta) \equiv \hat{\chi}(\Delta^{\Gamma}) \mod p$.

Now let $\Phi$ be a monotone graph property. Then $E_k^{\Phi} \setminus \{\emptyset\}$ is a simplicial complex, called the graph complex of $\Phi_k$. The ground set is the set of all edges of the complete labeled graph $K_k$ on $k$ vertices and we emphasize $E_k^{\Phi} \setminus \{\emptyset\}$ being a simplicial complex for monotone properties by denoting it as $\Delta(\Phi_k)$. If $\Gamma$ is any permutation group on the set $[k]$ then $\Gamma$ induces a group operation on the ground set of $\Phi_k$, i.e. the edges of the labeled complete graph of size $k$, by relabeling the vertices according to the group element. In particular, $\Delta(\Phi_k)$ is a $\Gamma$-simplicial complex as $\Phi_k$ is invariant under relabeling of vertices. We write $\Delta^{\Gamma}(\Phi_k)$ for the fixed-point complex $\Delta(\Phi_k)^{\Gamma}$ under this operation.

## Parameterized (counting) complexity

We will follow the definitions of Chapt. 14 of the textbook of Flum and Grohe [12]. A parameterized counting problem is a function $F: \{0, 1\}^* \to \mathbb{N}$ together with a computable parameterization $\kappa: \{0, 1\}^* \to \mathbb{N}$. ($F, \kappa$) is called fixed-parameter tractable (FPT) if there exists a deterministic algorithm $A$ and a computable function $f$ such that $A$ computes $F$ in time $f(\kappa(x)) \cdot |x|^{O(1)}$ for any input $x$. Given two parameterized counting problems ($F, \kappa$) and ($F', \kappa'$), a parameterized Turing reduction from ($F, \kappa$) to ($F', \kappa'$) is an FPT algorithm w.r.t. $\kappa$ that has oracle access to $F'$ and that on input $x$ computes $F(x)$ with the additional restriction that there exists a computable function $g$ such that for any oracle query $y$ it holds that $\kappa'(y) \le g(\kappa(x))$. We write $(F, \kappa) \le_P^{T}(F', \kappa')$.

The parameterized counting problem #Clique aks, given a graph $G$ and a natural number $k$, to compute the number of complete subgraphs of size $k$ in $G$ and the problem is parameterized by $k$. The class #W[1] contains all problems $(F, \kappa)$ such that $(F, \kappa) \le_P^{T}$ #Clique holds. Given a recursively enumerable class of graphs $\mathcal{H}$ the problems #Hom($\mathcal{H}$), #Emb($\mathcal{H}$), #Sub($\mathcal{H}$), #StrEmb($\mathcal{H}$) and #IndSub($\mathcal{H}$) ask, given a graph $H \in \mathcal{H}$ and an arbitrary (unlabeled) graph $G$, to compute #Hom($H, G$), #Emb($H, G$), #Sub($H, G$), #StrEmb($H, G$) and #IndSub($H, G$), respectively. All problems are parameterized by $|H|$. As stated in the introduction, there are dichotomy results for each of the aforementioned problems [10, 13, 9, 7]. We emphasize on the following, which is crucial for the framework of graph motif parameters.

**► Theorem 8 ([10, 13]).** The problem #Hom($\mathcal{H}$) is fixed-parameter tractable if there exists $b \in \mathbb{N}$ such that the treewidth$^7$ of every graph in $\mathcal{H}$ is bounded by $b$. Otherwise, the problem is #W[1]-hard.

<footnote>$^7$ We remark that the graph parameter of treewidth is not used explicitly in this work. Hence we refer the reader e.g. to Chapt. 11 in [12].</footnote>
preserves $\Delta$. More precisely, if $A \in \Delta$ and $g \in \Gamma$ then the set $g \triangleright A := \{g \triangleright a \mid a \in A\}$ is contained in $\Delta$ as well. If this is the case we can define the fixed-point complex $\Delta^{\Gamma}$ as follows. Let $O_1, \dots, O_k$ be the orbits of $\Omega$ with respect to $\Gamma$. Then

$$ \Delta^{\Gamma} := \left\{ S \subseteq \{1, \dots, k\} \mid S \neq \emptyset \wedge \bigcup_{i \in S} O_i \in \Delta \right\} $$

The following theorem, which is due to Smith [27] (see also [24] and Chapt. 3 in [3]), will be of crucial importance in Section 4.

**Theorem 7.** Let $\Gamma$ a group of order $p^s$ for some prime $p$ and natural number $s$ and let $\Delta$ be a $\Gamma$-simplicial complex. Then $\chi(\Delta) \equiv \chi(\Delta^{\Gamma}) \mod p$ and hence $\hat{\chi}(\Delta) \equiv \hat{\chi}(\Delta^{\Gamma}) \mod p$.

Now let $\Phi$ be a monotone graph property. Then $E_k^{\Phi} \setminus \{\emptyset\}$ is a simplicial complex, called the graph complex of $\Phi_k$. The ground set is the set of all edges of the complete labeled graph $K_k$ on $k$ vertices and we emphasize $E_k^{\Phi} \setminus \{\emptyset\}$ being a simplicial complex for monotone properties by denoting it as $\Delta(\Phi_k)$. If $\Gamma$ is any permutation group on the set $[k]$ then $\Gamma$ induces a group operation on the ground set of $\Phi_k$, i.e. the edges of the labeled complete graph of size $k$, by relabeling the vertices according to the group element. In particular, $\Delta(\Phi_k)$ is a $\Gamma$-simplicial complex as $\Phi_k$ is invariant under relabeling of vertices. We write $\Delta^{\Gamma}(\Phi_k)$ for the fixed-point complex $\Delta(\Phi_k)^{\Gamma}$ under this operation.

## Parameterized (counting) complexity

We will follow the definitions of Chapt. 14 of the textbook of Flum and Grohe [12]. A parameterized counting problem is a function $F: \{0, 1\}^* \to \mathbb{N}$ together with a computable parameterization $\kappa: \{0, 1\}^* \to \mathbb{N}$. ($F, \kappa$) is called fixed-parameter tractable (FPT) if there exists a deterministic algorithm $A$ and a computable function $f$ such that $A$ computes $F$ in time $f(\kappa(x)) \cdot |x|^{O(1)}$ for any input $x$. Given two parameterized counting problems ($F, \kappa$) and ($F', \kappa'$), a parameterized Turing reduction from ($F, \kappa$) to ($F', \kappa'$) is an FPT algorithm w.r.t. $\kappa$ that has oracle access to $F'$ and that on input $x$ computes $F(x)$ with the additional restriction that there exists a computable function $g$ such that for any oracle query $y$ it holds that $\kappa'(y) \le g(\kappa(x))$. We write $(F, \kappa) \le_P^{T}(F', \kappa')$.

The parameterized counting problem #Clique aks, given a graph $G$ and a natural number $k$, to compute the number of complete subgraphs of size $k$ in $G$ and the problem is parameterized by $k$. The class #W[1] contains all problems $(F, \kappa)$ such that $(F, \kappa) \le_P^{T}$ #Clique holds. Given a recursively enumerable class of graphs $\mathcal{H}$ the problems #Hom($\mathcal{H}$), #Emb($\mathcal{H}$), #Sub($\mathcal{H}$), #StrEmb($\mathcal{H}$) and #IndSub($\mathcal{H}$) ask, given a graph $H \in \mathcal{H}$ and an arbitrary (unlabeled) graph $G$, to compute #Hom($H, G$), #Emb($H, G$), #Sub($H, G$), #StrEmb($H, G$) and #IndSub($H, G$), respectively. All problems are parameterized by $|H|$. As stated in the introduction, there are dichotomy results for each of the aforementioned problems [10, 13, 9, 7]. We emphasize on the following, which is crucial for the framework of graph motif parameters.

**Theorem 8 ([10, 13]).** The problem #Hom($\mathcal{H}$) is fixed-parameter tractable if there exists $b \in \mathbb{N}$ such that the treewidth$^7$ of every graph in $\mathcal{H}$ is bounded by $b$. Otherwise, the problem is #W[1]-hard.

<footnote>$^7$ We remark that the graph parameter of treewidth is not used explicitly in this work. Hence we refer the reader e.g. to Chapt. 11 in [12].</footnote>
In this work we deal with a generalization of $\#\mathrm{IndSub}(\mathcal{H})$. Let $\Phi$ be a computable graph property. The problem $\#\mathrm{IndSub}(\Phi)$ asks, given a graph $G$ and a number $k \in \mathbb{N}$ to compute $\sum_{H \in \Phi_k} \#\mathrm{IndSub}(H, G)$. The parameter is $k$.

### 3 Graph motif parameters

In [8] Curticapean, Dell and Marx generalized the problem $\#\mathrm{Hom}(\mathcal{H})$ to linear combinations, called *graph motif parameters*. To this end, let $\mathcal{A}$ be a recursively enumerable set of functions $a: \mathcal{G} \to \mathbb{Q}$ such that $\mathrm{supp}(a)$ is finite. Then the problem $\#\mathrm{Hom}(\mathcal{A})$ asks, given $a \in \mathcal{A}$ and a graph $G$, to compute $\sum_{H \in \mathcal{G}} a(H) \cdot \#\mathrm{Hom}(H, G)$. The parameter is the description length of $a$, denoted by $|a|$. Their main result states that computing a linear combination of homomorphisms is as hard as computing all terms with non-zero coefficients:

**Theorem 9 ([8]).** There exists a deterministic algorithm that, on input a function $a: \mathcal{G} \to \mathbb{Q}$ with finite support, a graph $F \in \mathrm{supp}(a)$ and a graph $G$ and given oracle access to the function $G \mapsto \sum_{H \in \mathcal{G}} a(H) \cdot \#\mathrm{Hom}(H, G)$, computes $\#\mathrm{Hom}(F, G)$ in time $g(|a|) \cdot \#V(G)^{o(1)}$ and additionally satisfies that the number of vertices of every graph $G'$ for which the oracle is queried is of size bounded by $\max_{H \in \mathrm{supp}(a)} \#V(H) \cdot \#V(G)$.

Using this result, Curticapean, Dell and Marx proved that the problem $\#\mathrm{Hom}(\mathcal{A})$ is fixed-parameter tractable if there is a constant upper bound on the treewidth of all graphs that occur in the support of a function $a \in \mathcal{A}$, and #W[1]-hard otherwise. After that they showed that all of the problems $\#\mathrm{Emb}(\mathcal{H})$, $\#\mathrm{StrEmb}(\mathcal{H})$, ... are expressible as linear combinations of homomorphisms, immediately implying the existence of dichotomy results for those problems. However, establishing a concrete criterion for fixed-parameter tractability requires to find out which graphs are contained in the support of a function $a$ when the problem is translated to a linear combination of homomorphisms, and this can be highly non-trivial.

In what follows, we will establish a concrete criterion for properties $\Phi$ such that the coefficient of $K_k$ is non-zero when the function $G \mapsto \sum_{H \in \Phi_k} \#\mathrm{IndSub}(H, G)$ is translated to a linear combination of homomorphisms. This is motivated by the fact that, in this case, Theorem 9 allows us to compute the number $\#\mathrm{Hom}(K_k, G)$ which is equal to $k!$ times the number of cliques of size $k$ in $G$. As $\#\mathrm{Clique}$ can not be solved in time $f(k) \cdot \#V(G)^{o(k)}$ for any computable function $f$ under the Exponential Time Hypothesis [5, 6], we will not only obtain #W[1]-hardness but also a tight lower bound under the lense of fine-grained complexity theory.

**Theorem 10 (Theorem 1 restated).** Let $\Phi$ be a graph property, let $k$ be a non-zero natural number and let $a: \mathcal{G} \to \mathbb{Q}$ be the function such that for all graphs $G$ the following is true

$$ \sum_{H \in \Phi_k} \#\mathrm{IndSub}(H, G) = \sum_{H} a(H) \cdot \#\mathrm{Hom}(H, G). $$

$$ \text{Then } |k! \cdot a(K_k)| = |\sum_{A \in \mathcal{E}_k^\Phi} (-1)^{|A|}|. $$

**Proof.** Using the principle of inclusion-exclusion we can express the number of strong embeddings in terms of the number of embeddings (see e.g. Chapt. 5.2.3 in [20]):

$$ \#\mathrm{StrEmb}(H, G) = \sum_{\substack{H' \supseteq H \\ V(H') = V(H)}} (-1)^{\#E(H') - \#E(H)} \cdot \#\mathrm{Emb}(H', G), \quad (3) $$
In this work we deal with a generalization of $\#\mathrm{IndSub}(\mathcal{H})$. Let $\Phi$ be a computable graph property. The problem $\#\mathrm{IndSub}(\Phi)$ asks, given a graph $G$ and a number $k \in \mathbb{N}$ to compute $\sum_{H \in \Phi_k} \#\mathrm{IndSub}(H, G)$. The parameter is $k$.

### 3 Graph motif parameters

In [8] Curticapean, Dell and Marx generalized the problem $\#\mathrm{Hom}(\mathcal{H})$ to linear combinations, called *graph motif parameters*. To this end, let $\mathcal{A}$ be a recursively enumerable set of functions $a: \mathcal{G} \to \mathbb{Q}$ such that $\mathrm{supp}(a)$ is finite. Then the problem $\#\mathrm{Hom}(\mathcal{A})$ asks, given $a \in \mathcal{A}$ and a graph $G$, to compute $\sum_{H \in \mathcal{G}} a(H) \cdot \#\mathrm{Hom}(H, G)$. The parameter is the description length of $a$, denoted by $|a|$. Their main result states that computing a linear combination of homomorphisms is as hard as computing all terms with non-zero coefficients:

**Theorem 9 ([8]).** There exists a deterministic algorithm that, on input a function $a: \mathcal{G} \to \mathbb{Q}$ with finite support, a graph $F \in \mathrm{supp}(a)$ and a graph $G$ and given oracle access to the function $G \mapsto \sum_{H \in \mathcal{G}} a(H) \cdot \#\mathrm{Hom}(H, G)$, computes $\#\mathrm{Hom}(F, G)$ in time $g(|a|) \cdot \#V(G)^{o(1)}$ and additionally satisfies that the number of vertices of every graph $G'$ for which the oracle is queried is of size bounded by $\max_{H \in \mathrm{supp}(a)} \#V(H) \cdot \#V(G)$.

Using this result, Curticapean, Dell and Marx proved that the problem $\#\mathrm{Hom}(\mathcal{A})$ is fixed-parameter tractable if there is a constant upper bound on the treewidth of all graphs that occur in the support of a function $a \in \mathcal{A}$, and #W[1]-hard otherwise. After that they showed that all of the problems $\#\mathrm{Emb}(\mathcal{H})$, $\#\mathrm{StrEmb}(\mathcal{H})$, ... are expressible as linear combinations of homomorphisms, immediately implying the existence of dichotomy results for those problems. However, establishing a concrete criterion for fixed-parameter tractability requires to find out which graphs are contained in the support of a function $a$ when the problem is translated to a linear combination of homomorphisms, and this can be highly non-trivial.

In what follows, we will establish a concrete criterion for properties $\Phi$ such that the coefficient of $K_k$ is non-zero when the function $G \mapsto \sum_{H \in \Phi_k} \#\mathrm{IndSub}(H, G)$ is translated to a linear combination of homomorphisms. This is motivated by the fact that, in this case, Theorem 9 allows us to compute the number $\#\mathrm{Hom}(K_k, G)$ which is equal to $k!$ times the number of cliques of size $k$ in $G$. As $\#\mathrm{Clique}$ can not be solved in time $f(k) \cdot \#V(G)^{o(k)}$ for any computable function $f$ under the Exponential Time Hypothesis [5, 6], we will not only obtain #W[1]-hardness but also a tight lower bound under the lense of fine-grained complexity theory.

**Theorem 10 (Theorem 1 restated).** Let $\Phi$ be a graph property, let $k$ be a non-zero natural number and let $a: \mathcal{G} \to \mathbb{Q}$ be the function such that for all graphs $G$ the following is true

$$ \sum_{H \in \Phi_k} \#\mathrm{IndSub}(H, G) = \sum_H a(H) \cdot \#\mathrm{Hom}(H, G). $$

$$ \text{Then } |k! \cdot a(K_k)| = |\sum_{A \in \mathcal{E}_k^\Phi} (-1)^{|A|}|. $$

**Proof.** Using the principle of inclusion-exclusion we can express the number of strong embeddings in terms of the number of embeddings (see e.g. Chapt. 5.2.3 in [20]):

$$ \#\mathrm{StrEmb}(H, G) = \sum_{\substack{H' \supseteq H \\ V(H') = V(H')}} (-1)^{\#E(H') - \#E(H)} \cdot \#\mathrm{Emb}(H', G), \quad (3) $$
where $H'$ ranges over all graphs obtained from $H$ by adding edges. Next we collect terms in (3) that correspond to isomorphic graphs. To this end we let $\#\{H' \supseteq H\}$ denote the number of possibilities to add edges to $H$ such that the resulting graph is isomorphic to $H'$. Note that $\#\{K_k \supseteq H\} = 1$ if $H$ has $k$ vertices. We obtain

$$ \#\text{StrEmb}(H, G) = \sum_{H' \in \mathcal{G}} (-1)^{\#E(H') - \#E(H)} \cdot \#\{H' \supseteq H\} \cdot \#\text{Emb}(H', G). \quad (4) $$

Next we translate the number of embeddings to a linear combination of homomorphisms. This can be done using Möbius inversion<fnref n="8" /> (see [8] or Chapt. 5.2.3 in [20]):

$$ \#\text{Emb}(H', G) = \sum_{\rho \ge \emptyset} \mu(\emptyset, \rho) \cdot \#\text{Hom}(H'/\rho, G), \quad (5) $$

where the sum and the Möbius function $\mu$ are over the partition lattice of $V(H')$ and $H'/\rho$ is obtained from $H'$ by contracting every pair of vertices that is contained in the same block in $\rho$. We observe that the coefficient of $\#\text{Hom}(K_k, G)$ in the above sum is $\mu(\emptyset, \emptyset) = 1$ if $H'$ is isomorphic to $K_k$ and zero otherwise as every vertex contraction of a graph with $k$ vertices that is not the complete graph can not result in the complete graph with $k$ vertices. Hence the coefficient of $\#\text{Hom}(K_k, G)$ in Equation (4) is precisely $(-1)^{\#E(K_k) - \#E(H)}$. Next we use Fact 5 and obtain that

$$ \sum_{H \in \Phi_k} \#\text{IndSub}(H, G) = \sum_{H \in \Phi_k} \#\text{StrEmb}(H, G) \cdot \#\text{Aut}(H)^{-1}. \quad (6) $$

It follows that the coefficient $a(K_k)$ of $\#\text{Hom}(K_k, G)$ in Equation (6) satisfies

$$ a(K_k) = \sum_{H \in \Phi_k} (-1)^{\#E(K_k) - \#E(H)} \cdot \#\text{Aut}(H)^{-1}. \quad (7) $$

We now multiply this equation by $k!$, which we interpret as the number $\#\text{Sym}_k$ of elements of the symmetric group of the $k$ vertices. Taking also the absolute value on both sides allows us to drop the constant factor $(-1)^{\#E(K_k)}$ and we obtain

$$ |k! \cdot a(K_k)| = \left| \sum_{H \in \Phi_k} (-1)^{\#E(H)} \cdot \frac{\#\text{Sym}_k}{\#\text{Aut}(H)} \right|. \quad (8) $$

For any graph $H$ in the above sum choose a set $A_0$ of edges of the labeled complete graph $K_k$ on $k$ vertices such that the corresponding subgraph $G(A_0)$ is isomorphic to $H$. The group $\text{Sym}_k$ acts on the vertices and thus on the edges of $K_k$ and by the definition of a graph automorphism, the stabilizer of the set $A_0$ has exactly $\#\text{Aut}(H)$ elements. On the other hand the orbit of $A_0$ under $\text{Sym}_k$ is the collection of all sets $A$ such that $G(A) \cong H$. By the Orbit Stabilizer theorem we have $\frac{\#\text{Sym}_k}{\#\text{Aut}(H)} = \#\{A \subseteq E(K_k) | G(A) \cong H\}$. Inserting in equation (8) we obtain $|k! \cdot a(K_k)| = |\sum_{H \in \Phi_k} \sum_{G(A) \cong H} (-1)^{\#E(H)}| = |\sum_{A \in \mathbb{E}_k^\Phi} (-1)^{\#A}|$. $\quad$

Theorem 10 implies the following sufficient criterion for hardness of $\#\text{IndSub}(\Phi)$ which we will use in the remainder of the paper.

<footnote n="8">⁸ We omit the formal introduction to Möbius inversion as we will only need that $\mu(\emptyset, \emptyset) = 1$. We refer the interested reader to [20], where the concept is introduced and Equation (5) is proved.</footnote>
where $H'$ ranges over all graphs obtained from $H$ by adding edges. Next we collect terms in (3) that correspond to isomorphic graphs. To this end we let $\#\{H' \supseteq H\}$ denote the number of possibilities to add edges to $H$ such that the resulting graph is isomorphic to $H'$. Note that $\#\{K_k \supseteq H\} = 1$ if $H$ has $k$ vertices. We obtain

$$ \#\mathrm{StrEmb}(H, G) = \sum_{H' \in \mathcal{G}} (-1)^{\#E(H') - \#E(H)} \cdot \#\{H' \supseteq H\} \cdot \#\mathrm{Emb}(H', G). \quad (4) $$

Next we translate the number of embeddings to a linear combination of homomorphisms. This can be done using Möbius inversion<fnref n="8" /> (see [8] or Chapt. 5.2.3 in [20]):

$$ \#\mathrm{Emb}(H', G) = \sum_{\rho \ge \emptyset} \mu(\emptyset, \rho) \cdot \#\mathrm{Hom}(H'/\rho, G), \quad (5) $$

where the sum and the Möbius function $\mu$ are over the partition lattice of $V(H')$ and $H'/\rho$ is obtained from $H'$ by contracting every pair of vertices that is contained in the same block in $\rho$. We observe that the coefficient of $\#\mathrm{Hom}(K_k, G)$ in the above sum is $\mu(\emptyset, \emptyset) = 1$ if $H'$ is isomorphic to $K_k$ and zero otherwise as every vertex contraction of a graph with $k$ vertices that is not the complete graph can not result in the complete graph with $k$ vertices. Hence the coefficient of $\#\mathrm{Hom}(K_k, G)$ in Equation (4) is precisely $(-1)^{\#E(K_k) - \#E(H)}$. Next we use Fact 5 and obtain that

$$ \sum_{H \in \Phi_k} \#\mathrm{IndSub}(H, G) = \sum_{H \in \Phi_k} \#\mathrm{StrEmb}(H, G) \cdot \#\mathrm{Aut}(H)^{-1}. \quad (6) $$

It follows that the coefficient $a(K_k)$ of $\#\mathrm{Hom}(K_k, G)$ in Equation (6) satisfies

$$ a(K_k) = \sum_{H \in \Phi_k} (-1)^{\#E(K_k) - \#E(H)} \cdot \#\mathrm{Aut}(H)^{-1}. \quad (7) $$

We now multiply this equation by $k!$, which we interpret as the number $\#\mathrm{Sym}_k$ of elements of the symmetric group of the $k$ vertices. Taking also the absolute value on both sides allows us to drop the constant factor $(-1)^{\#E(K_k)}$ and we obtain

$$ |k! \cdot a(K_k)| = \left| \sum_{H \in \Phi_k} (-1)^{\#E(H)} \cdot \frac{\#\mathrm{Sym}_k}{\#\mathrm{Aut}(H)} \right|. \quad (8) $$

For any graph $H$ in the above sum choose a set $A_0$ of edges of the labeled complete graph $K_k$ on $k$ vertices such that the corresponding subgraph $G(A_0)$ is isomorphic to $H$. The group $\mathrm{Sym}_k$ acts on the vertices and thus on the edges of $K_k$ and by the definition of a graph automorphism, the stabilizer of the set $A_0$ has exactly $\#\mathrm{Aut}(H)$ elements. On the other hand the orbit of $A_0$ under $\mathrm{Sym}_k$ is the collection of all sets $A$ such that $G(A) \cong H$. By the Orbit Stabilizer theorem we have $\frac{\#\mathrm{Sym}_k}{\#\mathrm{Aut}(H)} = \#\{A \subseteq E(K_k) | G(A) \cong H\}$. Inserting in equation (8) we obtain $|k! \cdot a(K_k)| = |\sum_{H \in \Phi_k} \sum_{G(A) \cong H} (-1)^{\#E(H)}| = |\sum_{A \in \mathbb{E}_k^\Phi} (-1)^{\#A}|$. $\blacksquare$

Theorem 10 implies the following sufficient criterion for hardness of $\#\mathrm{IndSub}(\Phi)$ which we will use in the remainder of the paper.

<footnote n="8">⁸ We omit the formal introduction to Möbius inversion as we will only need that $\mu(\emptyset, \emptyset) = 1$. We refer the interested reader to [20], where the concept is introduced and Equation (5) is proved.</footnote>
24:10 Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness

**Corollary 11.** Let $\Phi$ be a graph property and let $\mathcal{K} = \{k \in \mathbb{N} \mid \sum_{A \in \mathcal{E}_k^*} (-1)^{\#A} \neq 0\}$. If $\mathcal{K}$ is infinite, then $\#\mathrm{IndSub}(\Phi)$ is $\#\mathrm{W}[1]$-hard. If additionally $\mathcal{K}$ is dense, $\#\mathrm{IndSub}(\Phi)$ can not be solved in time $f(k) \cdot \#V(G)^{o(k)}$ for any computable function $f$, unless ETH fails.

Due to space constraints the proof is deferred to the related version of the paper. However, let us give the rough idea: By Theorem 9 and Theorem 10 there exists a (tight) reduction from the problem $\#\mathrm{Clique}(\mathcal{K})$ of counting cliques of size $k$ where $k \in \mathcal{K}$ is promised.

As $\mathcal{K}$ is infinite we can apply a standard technique using colors and the inclusion-exclusion principle to reduce $\#\mathrm{Clique}$ to $\#\mathrm{Clique}(\mathcal{K})$, the former of which is $\#\mathrm{W}[1]$-complete and, assuming ETH, cannot be solved in time $f(k) \cdot n^{o(k)}$ for any computable function $f$ [5, 6]. This immediately yields $\#\mathrm{W}[1]$-hardness of $\#\mathrm{Clique}(\mathcal{K})$ and hence $\#\mathrm{IndSub}(\Phi)$. If additionally $\mathcal{K}$ is dense, the reduction is tight and the lower bound under ETH transfers as well.

4 Monotone properties

Recall that monotone graph properties are closed under the removal of edges. In what follows we assume every monotone graph property to hold on the independent set, i.e., the graph containing no edges, because otherwise the property would be trivially false. For technical reasons we say that a property is *non-trivial* if it is false on $K_k$ for all but finitely many $k \in \mathbb{N}$.<fnref n="9" /> Due to space constraints we might omit or only sketch proofs and defer the details to the related version of the paper. We start by refining Theorem 10 for monotone properties.

**Lemma 12.** Let $\Phi$ be a monotone graph property and let $k$ be a non-zero natural number. Then it holds that $\sum_{A \in \mathcal{E}_k^*} (-1)^{\#A} = \hat{\chi}(\Delta(\Phi_k))$.

**Corollary 13 (Corollary 2 restated).** Let $\Phi$ be a monotone graph property and let

$$ \mathcal{K} = \{k \in \mathbb{N} \mid \hat{\chi}(\Delta(\Phi_k)) \neq 0\}. $$

If $\mathcal{K}$ is infinite, then $\#\mathrm{IndSub}(\Phi)$ is $\#\mathrm{W}[1]$-hard. If additionally $\mathcal{K}$ is dense, $\#\mathrm{IndSub}(\Phi)$ can not be solved in time $f(k) \cdot \#V(G)^{o(k)}$ for any computable function $f$, unless ETH fails.

**Proof.** Follows immediately from Lemma 12 and Corollary 11.

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

The above criterion yields hardness of $\#\mathrm{IndSub}(\Phi)$ for every monotone graph property $\Phi$ whose graph complex is well-understood with respect to the (reduced) Euler characteristic. The thesis of Jonsson (see Chapt. 10.5 in [17]) provides a large list of graph complexes including e.g. disconnectivity, colorability and coverability, only to name a few, whose reduced Euler characteristics are non-zero infinitely often and to which Corollary 13 is hence applicable. We would also like to point out the work of Chakrabarti, Khot and Shi [4] who proved the reduced Euler characteristic of a large family of graph complexes to be odd. Their result will be used to prove the fourth condition of Theorem 4 and reads as follows — we state it in terms of homomorphisms.

**Lemma 14 ([4]).** Let $F$ be a graph and let $\Phi^{[F]}$ be the graph property that holds true on a graph $G$ if and only if $\mathrm{Hom}(F, G) = \emptyset$, i.e., there is no homomorphism from $F$ to $G$. Furthermore let $T_F := \min\{2^{2^t} - 1 \mid 2^{2^t} \ge \#V(F)\}$ and let $k \in \mathbb{N}$ such that $k \equiv 1 \mod T_F$. Then it holds that $\chi(\Phi_k^{[F]}) \equiv 0 \mod 2$ and hence $\hat{\chi}(\Phi_k^{[F]}) \equiv 1 \mod 2$.

<footnote n="9">⁹ This is required to exclude properties like $\Phi(G) = 0 \Leftrightarrow \#V(G) \equiv 1 \mod 2$ which indeed is monotone as it is closed under the removal of edges.</footnote>