## 4 SFVS on Graphs of Bounded Independent Set

Here we show that despite the complexity dichotomy result for the WEIGHTED SUBSET FEEDBACK VERTEX SET, whenever the weights of the vertices are equal SUBSET FEEDBACK VERTEX SET can be solved in polynomial time on graphs of bounded independent set number.

**Theorem 8.** SUBSET FEEDBACK VERTEX SET on graphs of independent set of size at most *d* can be solved in time $n^{O(d)}$.

*Proof.* Let $G = (V, E)$ be a graph with $\alpha(G) \le d$ and let $S \subseteq V$. Denote by $X \subseteq V$ a minimum subset feedback vertex set of $G$. Let $F = G - X$ be a maximum $S$-forest of $G$. By Observation 1 (2), the vertices of $S$ that belong to $F$ are at most $2d$. Thus for every optimum solution $X$, the set $S \setminus X$ has at most $2d$ vertices.

Now we claim that it is enough to try guessing all subsets $X'$ of $X$ for which $|X'| \le 2d$. To see this, observe that if $X \setminus S$ has order more than $2d$, then $G - S$ has more vertices than $G - X$, leading to a contradiction to the optimality of $X$. Hence, $X \setminus S$ has at most $2d$ vertices. In order to find an optimal solution, it suffices to consider all such candidates $S'$ for $S \setminus X$ and $X'$ for $X \setminus S$. To check whether an induced subgraph of $G$ consists an $S$-forest takes $O(n+m)$ time. Since the number of such sets $S'$ is at most $n^{2d}$ and the number of the considered sets $X'$ is at most $n^{2d}$, the total running time is bounded by $n^{O(d)}$. Therefore in time $n^{O(d)}$ we compute a minimum subset feedback vertex set showing the claimed result. ◀

Regarding the dependence of the exponent in the running time of the algorithm given in Theorem 8, note that we can hardly avoid this fact, since FEEDBACK VERTEX SET is W[1]-hard parameterized by the independent set number as explicitly given in [24]. At the same time such an observation follows from the W[1]-hardness result from the construction given in [22] with respect to the maximum induced matching width. In the full version of this extended abstract [32], we provide a different and simpler reduction from the MULTICOLORED INDEPENDENT SET problem [14, 33] which shows an interesting connection with graphs of bounded independent set size.

## 5 Extending to other Terminal Set Problems

Let us now consider further terminal set problems that are related to SUBSET FEEDBACK VERTEX SET. In these type of problems we are given a graph $G = (V, E)$, a terminal set $T \subseteq V$, and a nonnegative integer $k$ and the goal is to find a set $X \subseteq V$ with $|X| \le k$ which intersects all “structures” (such as cycles or paths) passing through the vertices in $T$ [6]. In this setting, SUBSET FEEDBACK VERTEX SET is a particular terminal set problem when the objective structure is a cycle. We show that the ideas that we developed for SUBSET FEEDBACK VERTEX SET on graphs of bounded independent set size, can be extended to further terminal set problems when the objective structure is a path instead of a cycle.

The (unweighted) NODE MULTIWAY CUT problem is concerned with finding a set $X \subseteq V \setminus T$ of size at most $k$ such that any path between two different terminals intersects $X$. Notice that in this problem we are not allowed to remove any terminal. For graphs having bounded independent set size, we completely characterize the complexity of NODE MULTIWAY CUT. In particular, for $\alpha(G) = 3$ we can adopt the reduction given in Theorem 7.

**Theorem 9.** Let $G$ be a graph of independent set of size at most $d$. If $d \le 2$ then NODE MULTIWAY CUT can be solved on time $n^{O(1)}$. Otherwise, NODE MULTIWAY CUT is NP-complete on graphs of independent set of size at most 3.
## 4 SFVS on Graphs of Bounded Independent Set

Here we show that despite the complexity dichotomy result for the WEIGHTED SUBSET FEEDBACK VERTEX SET, whenever the weights of the vertices are equal SUBSET FEEDBACK VERTEX SET can be solved in polynomial time on graphs of bounded independent set number.

**Theorem 8.** SUBSET FEEDBACK VERTEX SET on graphs of independent set of size at most *d* can be solved in time $n^{O(d)}$.

*Proof.* Let $G = (V, E)$ be a graph with $\alpha(G) \le d$ and let $S \subseteq V$. Denote by $X \subseteq V$ a minimum subset feedback vertex set of $G$. Let $F = G - X$ be a maximum $S$-forest of $G$. By Observation 1 (2), the vertices of $S$ that belong to $F$ are at most $2d$. Thus for every optimum solution $X$, the set $S \setminus X$ has at most $2d$ vertices.

Now we claim that it is enough to try guessing all subsets $X'$ of $X$ for which $|X'| \le 2d$. To see this, observe that if $X \setminus S$ has order more than $2d$, then $G-S$ has more vertices than $G-X$, leading to a contradiction to the optimality of $X$. Hence, $X \setminus S$ has at most $2d$ vertices. In order to find an optimal solution, it suffices to consider all such candidates $S'$ for $S \setminus X$ and $X'$ for $X \setminus S$. To check whether an induced subgraph of $G$ consists an $S$-forest takes $O(n+m)$ time. Since the number of such sets $S'$ is at most $n^{2d}$ and the number of the considered sets $X'$ is at most $n^{2d}$, the total running time is bounded by $n^{O(d)}$. Therefore in time $n^{O(d)}$ we compute a minimum subset feedback vertex set showing the claimed result. ◀

Regarding the dependence of the exponent in the running time of the algorithm given in Theorem 8, note that we can hardly avoid this fact, since FEEDBACK VERTEX SET is W[1]-hard parameterized by the independent set number as explicitly given in [24]. At the same time such an observation follows from the W[1]-hardness result from the construction given in [22] with respect to the maximum induced matching width. In the full version of this extended abstract [32], we provide a different and simpler reduction from the MULTICOLORED INDEPENDENT SET problem [14, 33] which shows an interesting connection with graphs of bounded independent set size.

## 5 Extending to other Terminal Set Problems

Let us now consider further terminal set problems that are related to SUBSET FEEDBACK VERTEX SET. In these type of problems we are given a graph $G = (V, E)$, a terminal set $T \subseteq V$, and a nonnegative integer $k$ and the goal is to find a set $X \subseteq V$ with $|X| \le k$ which intersects all “structures” (such as cycles or paths) passing through the vertices in $T$ [6]. In this setting, SUBSET FEEDBACK VERTEX SET is a particular terminal set problem when the objective structure is a cycle. We show that the ideas that we developed for SUBSET FEEDBACK VERTEX SET on graphs of bounded independent set size, can be extended to further terminal set problems when the objective structure is a path instead of a cycle.

The (unweighted) NODE MULTIWAY CUT problem is concerned with finding a set $X \subseteq V \setminus T$ of size at most $k$ such that any path between two different terminals intersects $X$. Notice that in this problem we are not allowed to remove any terminal. For graphs having bounded independent set size, we completely characterize the complexity of NODE MULTIWAY CUT. In particular, for $\alpha(G) = 3$ we can adopt the reduction given in Theorem 7.

**Theorem 9.** Let $G$ be a graph of independent set of size at most $d$. If $d \le 2$ then NODE MULTIWAY CUT can be solved on time $n^{O(1)}$. Otherwise, NODE MULTIWAY CUT is NP-complete on graphs of independent set of size at most 3.
Due to the difficulty of NODE MULTIWAY CUT even for the unweighted version and with small independent set number, we consider a relaxed variation in which we are allowed to remove terminal vertices. The NODE MULTIWAY CUT WITH DELETABLE TERMINALS problem seeks for a solution X with $X \subseteq V$ (instead of $X \subseteq V \setminus T$). Next we show that the (unweighted) NODE MULTIWAY CUT WITH DELETABLE TERMINALS problem can be solved in polynomial time on graphs of bounded independent set number, using an idea similar to the one given in Theorem 8.

**Theorem 10.** *NODE MULTIWAY CUT WITH DELETABLE TERMINALS on graphs of independent set of size at most *d* can be solved in time $n^{O(d)}$.*

**Proof.** Let $(G, T, k)$ be an instance of NODE MULTIWAY CUT WITH DELETABLE TERMINALS where $G$ is a graph having independent set size at most $d$. Observe that every solution $X$ has size at most $|T|$. Assume first that $|T| \le d$. Then we can enumerate all subsets having at most $|T|$ vertices in time $n^{O(|T|)}$ and pick the smallest subset that separates all terminals. Thus in time $n^{O(d)}$ we output a valid solution $X$, if it exists.

Next assume that $d < |T|$. We consider the graph $G[T]$. As an induced subgraph of $G$, $G[T]$ has independent set size at most $d$. Thus, $G[T]$ contains at least one edge. If both endpoints of an edge in $G[T]$ do not belong to solution $X$, then there is a path between terminal vertices. This means that there is a vertex cover $U$ of $G[T]$ such that $U \subseteq X$. To compute such a set $U$, we enumerate all independent sets $T' \subseteq T$ of size at most $d$ in time $|T|^{O(d)}$ and construct $U = T \setminus T'$. For each constructed $U$, we consider the graph $G' = G - U$ with terminals $T'$. Since $T'$ is an independent set in $G'$, we know that $|T'| \le d$. Thus in time $n^{O(|T'|)}$ we can compute a set $X'$ of minimum size such that all terminals of $G' - X'$ are separated. Therefore, the total running time is bounded by $|T|^{O(d)} \cdot n^{O(|T'|)}$ which is bounded by $n^{O(d)}$, because $|T| \le n$ and $|T'| \le d$. ◀

Let us also stress that we can hardly avoid the dependence of the exponent in the running time given in Theorem 10. This comes from the fact that NODE MULTIWAY CUT WITH DELETABLE TERMINALS with $T = V(G)$ is equivalent to asking whether the graph contains an independent set of size at least $k$. That is, we have to solve the INDEPENDENT SET which is known to be $W[1]$-hard parameterized by the size of the independent set [12].

Regarding the node-weighted variant of NODE MULTIWAY CUT WITH DELETABLE TERMINALS, we provide a dichotomy result with respect to $\alpha(G)$. In fact, for $\alpha(G) \le 2$ we can invoke the algorithm for the WEIGHTED SUBSET FEEDBACK VERTEX SET given in Theorem 6, by adding a new vertex with a large weight that is adjacent to all terminals. Moreover, due to its close connection to the NODE MULTIWAY CUT, for $\alpha(G) > 2$ we can assign appropriate weights to the terminals in a way that they become undeletable.

**Theorem 11.** *Let $G$ be a graph of independent set of size at most $d$. If $d \le 2$ then WEIGHTED NODE MULTIWAY CUT WITH DELETABLE TERMINALS can be solved in time $n^{O(1)}$. Otherwise, WEIGHTED NODE MULTIWAY CUT WITH DELETABLE TERMINALS is NP-complete on graphs of independent set of size at most 3.*

# 6 Concluding Remarks

Despite the fact that the WEIGHTED SUBSET FEEDBACK VERTEX SET is NP-complete on graphs with bounded independent set number, it is still interesting to settle the complexity of SUBSET FEEDBACK VERTEX SET on graphs of maximum induced matching width by extending the approach given in [23]. Moreover, FEEDBACK VERTEX SET is known to be
Due to the difficulty of NODE MULTIWAY CUT even for the unweighted version and with small independent set number, we consider a relaxed variation in which we are allowed to remove terminal vertices. The NODE MULTIWAY CUT WITH DELETABLE TERMINALS problem seeks for a solution $X$ with $X \subseteq V$ (instead of $X \subseteq V \setminus T$). Next we show that the (unweighted) NODE MULTIWAY CUT WITH DELETABLE TERMINALS problem can be solved in polynomial time on graphs of bounded independent set number, using an idea similar to the one given in Theorem 8.

**Theorem 10.** *NODE MULTIWAY CUT WITH DELETABLE TERMINALS on graphs of independent set of size at most *d* can be solved in time $n^{O(d)}$.*

**Proof.** Let $(G, T, k)$ be an instance of NODE MULTIWAY CUT WITH DELETABLE TERMINALS where $G$ is a graph having independent set size at most $d$. Observe that every solution $X$ has size at most $|T|$. Assume first that $|T| \le d$. Then we can enumerate all subsets having at most $|T|$ vertices in time $n^{O(|T|)}$ and pick the smallest subset that separates all terminals. Thus in time $n^{O(d)}$ we output a valid solution $X$, if it exists.

Next assume that $d < |T|$. We consider the graph $G[T]$. As an induced subgraph of $G$, $G[T]$ has independent set size at most $d$. Thus, $G[T]$ contains at least one edge. If both endpoints of an edge in $G[T]$ do not belong to solution $X$, then there is a path between terminal vertices. This means that there is a vertex cover $U$ of $G[T]$ such that $U \subseteq X$. To compute such a set $U$, we enumerate all independent sets $T' \subseteq T$ of size at most $d$ in time $|T|^{O(d)}$ and construct $U = T \setminus T'$. For each constructed $U$, we consider the graph $G' = G - U$ with terminals $T'$. Since $T'$ is an independent set in $G'$, we know that $|T'| \le d$. Thus in time $n^{O(|T'|)}$ we can compute a set $X'$ of minimum size such that all terminals of $G' - X'$ are separated. Therefore, the total running time is bounded by $|T|^{O(d)} \cdot n^{O(|T'|)}$ which is bounded by $n^{O(d)}$, because $|T| \le n$ and $|T'| \le d$. ◀

Let us also stress that we can hardly avoid the dependence of the exponent in the running time given in Theorem 10. This comes from the fact that NODE MULTIWAY CUT WITH DELETABLE TERMINALS with $T = V(G)$ is equivalent to asking whether the graph contains an independent set of size at least $k$. That is, we have to solve the INDEPENDENT SET which is known to be $W[1]$-hard parameterized by the size of the independent set [12].

Regarding the node-weighted variant of NODE MULTIWAY CUT WITH DELETABLE TERMINALS, we provide a dichotomy result with respect to $\alpha(G)$. In fact, for $\alpha(G) \le 2$ we can invoke the algorithm for the WEIGHTED SUBSET FEEDBACK VERTEX SET given in Theorem 6, by adding a new vertex with a large weight that is adjacent to all terminals. Moreover, due to its close connection to the NODE MULTIWAY CUT, for $\alpha(G) > 2$ we can assign appropriate weights to the terminals in a way that they become undeletable.

**Theorem 11.** *Let $G$ be a graph of independent set of size at most $d$. If $d \le 2$ then WEIGHTED NODE MULTIWAY CUT WITH DELETABLE TERMINALS can be solved in time $n^{O(1)}$. Otherwise, WEIGHTED NODE MULTIWAY CUT WITH DELETABLE TERMINALS is NP-complete on graphs of independent set of size at most 3.*

# 6 Concluding Remarks

Despite the fact that the WEIGHTED SUBSET FEEDBACK VERTEX SET is NP-complete on graphs with bounded independent set number, it is still interesting to settle the complexity of SUBSET FEEDBACK VERTEX SET on graphs of maximum induced matching width by extending the approach given in [23]. Moreover, FEEDBACK VERTEX SET is known to be
polynomially-time solvable on cocomparability graphs [28], and, more generally, on AT-free
graphs [26]. To our knowledge, SUBSET FEEDBACK VERTEX SET has not been studied on
such graphs, besides the existence of a fast exponential-time algorithm for the unweighted
variant of the problem [6]. Furthermore, Theorem 9 shows that NODE MULTIWAY CUT
remains NP-complete on graphs having maximum induced matching three. However, on
graphs of bounded maximum induced matching the complexity of NODE MULTIWAY CUT
WITH DELETABLE TERMINALS is still unknown.

References

1 A. Brandstädt, V. B. Le, and J. Spinrad. *Graph Classes: A Survey*. Society for Industrial and Applied Mathematics, 1999.

2 B.-M. Bui-Xuan, O. Suchý, J. A. Telle, and M. Vatshelle. Feedback vertex set on graphs of low clique-width. *Eur. Journal of Combinatorics*, 34(3):666–679, 2013.

3 G. Calinescu. Multiway Cut. In *Encyclopedia of Algorithms*. Springer, 2008.

4 J. Chen, Y. Liu, and S. Lu. An improved parameterized algorithm for the minimum node multiway cut problem. *Algorithmica*, 55:1–13, 2009.

5 R. H. Chitnis, F. V. Fomin, D. Lokshtanov, P. Misra, M. S. Ramanujan, and S. Saurabh. Faster exact algorithms for some terminal set problems. In *Proceedings of IPEC 2013*, pages 150–162, 2013.

6 R. H. Chitnis, F. V. Fomin, D. Lokshtanov, P. Misra, M. S. Ramanujan, and S. Saurabh. Faster exact algorithms for some terminal set problems. *Journal of Computer and System Sciences*, 88:195–207, 2017.

7 D. G. Corneil and J. Fonlupt. The complexity of generalized clique covering. *Discrete Applied Mathematics*, 22(2):109–118, 1988.

8 M. Cygan, J. Nederlof, M. Pilipczuk, M. Pilipczuk, J. M. M. van Rooij, and J. O. Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In *Proceedings of FOCS 2011*, pages 150–159, 2011.

9 M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk. On multiway cut parameterized above lower bounds. *ACM Trans. Comput. Theory*, 5(1):3:1–3:11, 2013.

10 M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk. Subset feedback vertex set is fixed-parameter tractable. *SIAM J. Discrete Math.*, 27(1):290–309, 2013.

11 R. Diestel. *Graph Theory, 4th Edition*, volume 173 of *Graduate Texts in Mathematics*. Springer, 2012.

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

13 G. Even, J. Naor, and L. Zosin. An 8-approximation algorithm for the subset feedback vertex set problem. *SIAM J. Comput.*, 30(4):1231–1252, 2000.

14 M. R. 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.

15 F. V. Fomin, S. Gaspers, D. Lokshtanov, and S. Saurabh. Exact algorithms via monotone local search. In *Proceedings of STOC 2016*, pages 764–775, 2016.

16 F. V. Fomin, P. Heggernes, D. Kratsch, C. Papadopoulos, and Y. Villanger. Enumerating minimal subset feedback vertex sets. *Algorithmica*, 69(1):216–231, 2014.

17 M. R. Garey and D. S. Johnson. *Computers and Intractability*. W. H. Freeman and Co., 1978.

18 N. Garg, V. V. Vazirani, and M. Yannakakis. Multiway cuts in node weighted graphs. *J. Algorithms*, 50(1):49–61, 2004.

19 P. A. Golovach, P. Heggernes, D. Kratsch, and R. Saei. Subset feedback vertex sets in chordal graphs. *J. Discrete Algorithms*, 26:7–15, 2014.
polynomially-time solvable on cocomparability graphs [28], and, more generally, on AT-free
graphs [26]. To our knowledge, SUBSET FEEDBACK VERTEX SET has not been studied on
such graphs, besides the existence of a fast exponential-time algorithm for the unweighted
variant of the problem [6]. Furthermore, Theorem 9 shows that NODE MULTIWAY CUT
remains NP-complete on graphs having maximum induced matching three. However, on
graphs of bounded maximum induced matching the complexity of NODE MULTIWAY CUT
WITH DELETABLE TERMINALS is still unknown.

References

1 A. Brandstädt, V. B. Le, and J. Spinrad. *Graph Classes: A Survey*. Society for Industrial and Applied Mathematics, 1999.

2 B.-M. Bui-Xuan, O. Suchý, J. A. Telle, and M. Vatshelle. Feedback vertex set on graphs of low clique-width. *Eur. Journal of Combinatorics*, 34(3):666–679, 2013.

3 G. Calinescu. Multiway Cut. In *Encyclopedia of Algorithms*. Springer, 2008.

4 J. Chen, Y. Liu, and S. Lu. An improved parameterized algorithm for the minimum node multiway cut problem. *Algorithmica*, 55:1–13, 2009.

5 R. H. Chitnis, F. V. Fomin, D. Lokshtanov, P. Misra, M. S. Ramanujan, and S. Saurabh. Faster exact algorithms for some terminal set problems. In *Proceedings of IPEC 2013*, pages 150–162, 2013.

6 R. H. Chitnis, F. V. Fomin, D. Lokshtanov, P. Misra, M. S. Ramanujan, and S. Saurabh. Faster exact algorithms for some terminal set problems. *Journal of Computer and System Sciences*, 88:195–207, 2017.

7 D. G. Corneil and J. Fonlupt. The complexity of generalized clique covering. *Discrete Applied Mathematics*, 22(2):109–118, 1988.

8 M. Cygan, J. Nederlof, M. Pilipczuk, M. Pilipczuk, J. M. M. van Rooij, and J. O. Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In *Proceedings of FOCS 2011*, pages 150–159, 2011.

9 M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk. On multiway cut parameterized above lower bounds. *ACM Trans. Comput. Theory*, 5(1):3:1–3:11, 2013.

10 M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk. Subset feedback vertex set is fixed-parameter tractable. *SIAM J. Discrete Math.*, 27(1):290–309, 2013.

11 R. Diestel. *Graph Theory*, 4th Edition, volume 173 of *Graduate Texts in Mathematics*. Springer, 2012.

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

13 G. Even, J. Naor, and L. Zosin. An 8-approximation algorithm for the subset feedback vertex set problem. *SIAM J. Comput.*, 30(4):1231–1252, 2000.

14 M. R. 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.

15 F. V. Fomin, S. Gaspers, D. Lokshtanov, and S. Saurabh. Exact algorithms via monotone local search. In *Proceedings of STOC 2016*, pages 764–775, 2016.

16 F. V. Fomin, P. Heggernes, D. Kratsch, C. Papadopoulos, and Y. Villanger. Enumerating minimal subset feedback vertex sets. *Algorithmica*, 69(1):216–231, 2014.

17 M. R. Garey and D. S. Johnson. *Computers and Intractability*. W. H. Freeman and Co., 1978.

18 N. Garg, V. V. Vazirani, and M. Yannakakis. Multiway cuts in node weighted graphs. *J. Algorithms*, 50(1):49–61, 2004.

19 P. A. Golovach, P. Heggernes, D. Kratsch, and R. Saei. Subset feedback vertex sets in chordal graphs. *J. Discrete Algorithms*, 26:7–15, 2014.
20 M. C. Golumbic. *Algorithmic Graph Theory and Perfect Graphs*. Annals of Discrete Mathematics 57, Elsevier, 2004.

21 E. C. Hols and S. Kratsch. A randomized polynomial kernel for subset feedback vertex set. *Theory Comput. Syst.*, 62:54–65, 2018.

22 L. Jaffke, O. Kwon, and J. A. Telle. A note on the complexity of feedback vertex set parameterized by mim-width. *CoRR*, abs/1711.05157, 2017.

23 L. Jaffke, O. Kwon, and J. A. Telle. A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width. In *Proceedings of STACS 2018*, pages 42:1–42:14, 2018.

24 B. Jansen, V. Raman, and M. Vatshelle. Parameter ecology for feedback vertex set. *Tsinghua Sci. and Technol.*, 19(4):387–409, 2014.

25 K. Kawarabayashi and Y. Kobayashi. Fixed-parameter tractability for the subset feedback set problem and the S-cycle packing problem. *J. Comb. Theory, Ser. B*, 102(4):1020–1034, 2012.

26 D. Kratsch, H. Müller, and I. Todinca. Feedback vertex set on AT-free graphs. *Discrete Applied Mathematics*, 156(10):1936–1947, 2008.

27 S. Kratsch and M. Wahlstrom. Representative sets and irrelevant vertices: new tools for kernelization. In *Proceedings of FOCS 2012*, pages 450–459, 2012.

28 Y. D. Liang and M.-S. Chang. Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs. *Acta Informatica*, 34(5):337–346, 1997.

29 D. Marx. Parameterized graph separation problems. *Theor. Comput. Sci.*, 351:399–406, 2006.

30 J. B. Orlin. Max flows in O(nm) time, or better. In *Proceedings of STOC 2013*, pages 765–774, 2013.

31 C. Papadopoulos and S. Tzimas. Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs. In *Proceedings of FCT 2017*, pages 381–394, 2017.

32 C. Papadopoulos and S. Tzimas. Subset feedback vertex set on graphs of bounded independent set size. *CoRR*, abs/1805.07141, 2018. arXiv:1805.07141.

33 K. Pietrzak. On the parameterized complexity of the fixed alphabet shortest common super-sequence and longest common subsequence problems. *J. Comput. Syst. Sci.*, 67(4):757–771, 2003.

34 J. P. Spinrad. *Efficient Graph Representations*. American Mathematical Society, Fields Institute Monograph Series 19, 2003.

35 M. Vatshelle. *New Width Parameters of Graphs*. PhD thesis, University of Bergen, Norway, 2012.

36 M. Yannakakis. Node-deletion problems on bipartite graphs. *SIAM J. Comput.*, 10(2):310–327, 1981.
20 M. C. Golumbic. *Algorithmic Graph Theory and Perfect Graphs*. Annals of Discrete Mathematics 57, Elsevier, 2004.

21 E. C. Hols and S. Kratsch. A randomized polynomial kernel for subset feedback vertex set. *Theory Comput. Syst.*, 62:54–65, 2018.

22 L. Jaffke, O. Kwon, and J. A. Telle. A note on the complexity of feedback vertex set parameterized by mim-width. *CoRR*, abs/1711.05157, 2017.

23 L. Jaffke, O. Kwon, and J. A. Telle. A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width. In *Proceedings of STACS 2018*, pages 42:1–42:14, 2018.

24 B. Jansen, V. Raman, and M. Vatshelle. Parameter ecology for feedback vertex set. *Tsinghua Sci. and Technol.*, 19(4):387–409, 2014.

25 K. Kawarabayashi and Y. Kobayashi. Fixed-parameter tractability for the subset feedback set problem and the S-cycle packing problem. *J. Comb. Theory, Ser. B*, 102(4):1020–1034, 2012.

26 D. Kratsch, H. Müller, and I. Todinca. Feedback vertex set on AT-free graphs. *Discrete Applied Mathematics*, 156(10):1936–1947, 2008.

27 S. Kratsch and M. Wahlstrom. Representative sets and irrelevant vertices: new tools for kernelization. In *Proceedings of FOCS 2012*, pages 450–459, 2012.

28 Y. D. Liang and M.-S. Chang. Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs. *Acta Informatica*, 34(5):337–346, 1997.

29 D. Marx. Parameterized graph separation problems. *Theor. Comput. Sci.*, 351:399–406, 2006.

30 J. B. Orlin. Max flows in O(nm) time, or better. In *Proceedings of STOC 2013*, pages 765–774, 2013.

31 C. Papadopoulos and S. Tzimas. Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs. In *Proceedings of FCT 2017*, pages 381–394, 2017.

32 C. Papadopoulos and S. Tzimas. Subset feedback vertex set on graphs of bounded independent set size. *CoRR*, abs/1805.07141, 2018. arXiv:1805.07141.

33 K. Pietrzak. On the parameterized complexity of the fixed alphabet shortest common super-sequence and longest common subsequence problems. *J. Comput. Syst. Sci.*, 67(4):757–771, 2003.

34 J. P. Spinrad. *Efficient Graph Representations*. American Mathematical Society, Fields Institute Monograph Series 19, 2003.

35 M. Vatshelle. *New Width Parameters of Graphs*. PhD thesis, University of Bergen, Norway, 2012.

36 M. Yannakakis. Node-deletion problems on bipartite graphs. *SIAM J. Comput.*, 10(2):310–327, 1981.
# Integer Programming in Parameterized Complexity: Three Miniatures

## Tomáš Gavenčiak

Department of Applied Mathematics, Charles University, Prague, Czech Republic
gavento@kam.mff.cuni.cz

## Dušan Knop<fnref n="1" />

Department of Informatics, University of Bergen, Bergen, Norway and

Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic
dusan.knop@uib.no

## Martin Koutecký<fnref n="2" />

Technion - Israel Institute of Technology, Haifa, Israel and

Computer Science Institute, Charles University, Prague, Czech Republic
koutecky@technion.ac.il

## Abstract

Powerful results from the theory of integer programming have recently led to substantial advances in parameterized complexity. However, our perception is that, except for Lenstra's algorithm for solving integer linear programming in fixed dimension, there is still little understanding in the parameterized complexity community of the strengths and limitations of the available tools. This is understandable: it is often difficult to infer exact runtimes or even the distinction between FPT and XP algorithms, and some knowledge is simply unwritten folklore in a different community. We wish to make a step in remedying this situation.

To that end, we first provide an easy to navigate quick reference guide of integer programming algorithms from the perspective of parameterized complexity. Then, we show their applications in three case studies, obtaining FPT algorithms with runtime $f(k)$ poly($n$). We focus on:

- Modeling: since the algorithmic results follow by applying existing algorithms to new models, we shift the focus from the complexity result to the modeling result, highlighting common patterns and tricks which are used.

- Optimality program: after giving an FPT algorithm, we are interested in reducing the dependence on the parameter; we show which algorithms and tricks are often useful for speed-ups.

- Minding the poly($n$): reducing $f(k)$ often has the unintended consequence of increasing poly($n$); so we highlight the common trade-offs and show how to get the best of both worlds.

Specifically, we consider graphs of bounded neighborhood diversity which are in a sense the simplest of dense graphs, and we show several FPT algorithms for CAPACITATED DOMINATING SET, SUM COLORING, and MAX-$q$-CUT by modeling them as convex programs in fixed dimension, $n$-fold integer programs, bounded dual treewidth programs, and indefinite quadratic programs in fixed dimension.

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

**Keywords and phrases** graph coloring, parameterized complexity, integer linear programming, integer convex programming

Digital Object Identifier 10.4230/LIPICs.IPEC.2018.21

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

<footnote n="1">¹ Author supported by the project NFR MULTIVAL.</footnote>

<footnote n="2">² Author supported by Technion postdoctoral fellowship.</footnote>
# Integer Programming in Parameterized Complexity: Three Miniatures

## Tomáš Gavenčiak

Department of Applied Mathematics, Charles University, Prague, Czech Republic
gavento@kam.mff.cuni.cz

## Dušan Knop<fnref n="1" />

Department of Informatics, University of Bergen, Bergen, Norway and

Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic
dusan.knop@uib.no

## Martin Koutecký<fnref n="2" />

Technion - Israel Institute of Technology, Haifa, Israel and

Computer Science Institute, Charles University, Prague, Czech Republic
koutecky@technion.ac.il

## Abstract

Powerful results from the theory of integer programming have recently led to substantial advances in parameterized complexity. However, our perception is that, except for Lenstra's algorithm for solving integer linear programming in fixed dimension, there is still little understanding in the parameterized complexity community of the strengths and limitations of the available tools. This is understandable: it is often difficult to infer exact runtimes or even the distinction between FPT and XP algorithms, and some knowledge is simply unwritten folklore in a different community. We wish to make a step in remedying this situation.

To that end, we first provide an easy to navigate quick reference guide of integer programming algorithms from the perspective of parameterized complexity. Then, we show their applications in three case studies, obtaining FPT algorithms with runtime $f(k)$ poly($n$). We focus on:

- **Modeling**: since the algorithmic results follow by applying existing algorithms to new models, we shift the focus from the complexity result to the modeling result, highlighting common patterns and tricks which are used.

- **Optimality program**: after giving an FPT algorithm, we are interested in reducing the dependence on the parameter; we show which algorithms and tricks are often useful for speed-ups.

- **Minding the poly($n$)**: reducing $f(k)$ often has the unintended consequence of increasing poly($n$); so we highlight the common trade-offs and show how to get the best of both worlds.

Specifically, we consider graphs of bounded neighborhood diversity which are in a sense the simplest of dense graphs, and we show several FPT algorithms for CAPACITATED DOMINATING SET, SUM COLORING, and MAX-$q$-CUT by modeling them as convex programs in fixed dimension, $n$-fold integer programs, bounded dual treewidth programs, and indefinite quadratic programs in fixed dimension.

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

**Keywords and phrases** graph coloring, parameterized complexity, integer linear programming, integer convex programming

Digital Object Identifier 10.4230/LIPICs.IPEC.2018.21

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

<footnote n="1">¹ Author supported by the project NFR MULTIVAL.</footnote>

<footnote n="2">² Author supported by Technion postdoctoral fellowship.</footnote>
**Related Version** A full version of the paper is available at https://arxiv.org/abs/1711.02032.

# 1 Introduction

Our focus is on modeling various problems as INTEGER PROGRAMMING (IP), and then obtaining FPT algorithms by applying known algorithms for IP. IP is the problem

$$ \min\{f(\mathbf{x}) \mid \mathbf{x} \in S \cap \mathbb{Z}^n, S \subseteq \mathbb{R}^n \text{ is convex}\}. \qquad (\text{IP}) $$

We give special attention to two restrictions of IP. First, when $S$ is a polyhedron, we get

$$ \min\{f(\mathbf{x}) \mid A\mathbf{x} \le \mathbf{b}, \mathbf{x} \in \mathbb{Z}^n\}, \qquad (\text{LinIP}) $$

where $A \in \mathbb{Z}^{m \times n}$ and $\mathbf{b} \in \mathbb{Z}^m$; we call this problem linearly-constrained IP, or LinIP. Further restricting $f$ to be a linear function gives INTEGER LINEAR PROGRAMMING (ILP):

$$ \min\{\mathbf{w}\mathbf{x} \mid A\mathbf{x} \le \mathbf{b}, \mathbf{x} \in \mathbb{Z}^n\}, \qquad (\text{ILP}) $$

where $\mathbf{w} \in \mathbb{Z}^n$. The function $f: \mathbb{Z}^n \to \mathbb{Z}$ is called the objective function, $S$ is the feasible set (defined by constraints or various oracles), and $\mathbf{x}$ is a vector of (decision) variables. By $\langle \cdot, \cdot \rangle$ we denote the binary encoding length of numbers, vectors and matrices.

In 1983 Lenstra showed that ILP is polynomial in fixed dimension and solvable in time $n^{O(n)} \langle A, \mathbf{b}, \mathbf{w} \rangle$ (including later improvements [22, 36, 45]). Two decades later this algorithm's potential for applications in parameterized complexity was recognized, e.g. by Niedermeier [52]:

> [...] It remains to investigate further examples besides CLOSEST STRING where the described ILP approach turns out to be applicable. More generally, it would be interesting to discover more connections between fixed-parameter algorithms and (integer) linear programming.

This call has been answered in the following years, for example in the context of graph algorithms [19, 20, 24, 44], scheduling [30, 35, 38, 51] or computational social choice [8].

In the meantime, many other powerful algorithms for IP have been devised; however it seemed unclear exactly how could these tools be used, as Lokshtanov states in his PhD thesis [46], referring to FPT algorithms for convex IP in fixed dimension:

> It would be interesting to see if these even more general results can be useful for showing problems fixed parameter tractable.

Similarly, Downey and Fellows [14] highlight the FPT algorithm for so called n-fold IP:

> Conceivably, [MINIMUM LINEAR ARRANGEMENT] might also be approached by the recent (and deep) FPT results of Hemmecke, Onn and Romanchuk [28] concerning nonlinear optimization.

Interestingly, MINIMUM LINEAR ARRANGEMENT was shown to be FPT by yet another new algorithm for IP due to Lokshtanov [47].

In the last 3 years we have seen a surge of interest in, and an increased understanding of, these IP techniques beyond Lenstra's algorithm, allowing significant advances in fields such as parameterized scheduling [9, 30, 33, 38, 51], computational social choice [39, 40, 42], multichoice optimization [23], and stringology [39]. This has increased our understanding of the strengths and limitations of each tool as well as the modeling patterns and tricks which are typically applicable and used.
**Related Version** A full version of the paper is available at https://arxiv.org/abs/1711.02032.

# 1 Introduction

Our focus is on modeling various problems as INTEGER PROGRAMMING (IP), and then obtaining FPT algorithms by applying known algorithms for IP. IP is the problem

$$ \min\{f(\mathbf{x}) \mid \mathbf{x} \in S \cap \mathbb{Z}^n, S \subseteq \mathbb{R}^n \text{ is convex}\}. \qquad (\text{IP}) $$

We give special attention to two restrictions of IP. First, when S is a polyhedron, we get

$$ \min\{f(\mathbf{x}) \mid A\mathbf{x} \le \mathbf{b}, \mathbf{x} \in \mathbb{Z}^n\}, \qquad (\text{LinIP}) $$

where $A \in \mathbb{Z}^{m \times n}$ and $\mathbf{b} \in \mathbb{Z}^m$; we call this problem linearly-constrained IP, or LinIP. Further restricting f to be a linear function gives INTEGER LINEAR PROGRAMMING (ILP):

$$ \min\{\mathbf{w}\mathbf{x} \mid A\mathbf{x} \le \mathbf{b}, \mathbf{x} \in \mathbb{Z}^n\}, \qquad (\text{ILP}) $$

where $\mathbf{w} \in \mathbb{Z}^n$. The function $f: \mathbb{Z}^n \to \mathbb{Z}$ is called the objective function, S is the feasible set (defined by constraints or various oracles), and $\mathbf{x}$ is a vector of (decision) variables. By $\langle \cdot, \cdot \rangle$ we denote the binary encoding length of numbers, vectors and matrices.

In 1983 Lenstra showed that ILP is polynomial in fixed dimension and solvable in time $n^{O(n)} \langle A, \mathbf{b}, \mathbf{w} \rangle$ (including later improvements [22, 36, 45]). Two decades later this algorithm's potential for applications in parameterized complexity was recognized, e.g. by Niedermeier [52]:

> [...] It remains to investigate further examples besides CLOSEST STRING where the described ILP approach turns out to be applicable. More generally, it would be interesting to discover more connections between fixed-parameter algorithms and (integer) linear programming.

This call has been answered in the following years, for example in the context of graph algorithms [19, 20, 24, 44], scheduling [30, 35, 38, 51] or computational social choice [8].

In the meantime, many other powerful algorithms for IP have been devised; however it seemed unclear exactly how could these tools be used, as Lokshtanov states in his PhD thesis [46], referring to FPT algorithms for convex IP in fixed dimension:

> It would be interesting to see if these even more general results can be useful for showing problems fixed parameter tractable.

Similarly, Downey and Fellows [14] highlight the FPT algorithm for so called n-fold IP:

> Conceivably, [MINIMUM LINEAR ARRANGEMENT] might also be approached by the recent (and deep) FPT results of Hemmecke, Onn and Romanchuk [28] concerning nonlinear optimization.

Interestingly, MINIMUM LINEAR ARRANGEMENT was shown to be FPT by yet another new algorithm for IP due to Lokshtanov [47].

In the last 3 years we have seen a surge of interest in, and an increased understanding of, these IP techniques beyond Lenstra's algorithm, allowing significant advances in fields such as parameterized scheduling [9, 30, 33, 38, 51], computational social choice [39, 40, 42], multichoice optimization [23], and stringology [39]. This has increased our understanding of the strengths and limitations of each tool as well as the modeling patterns and tricks which are typically applicable and used.
## 1.1 Our Results

We start by giving a quick overview of existing techniques in Section 2, which we hope to be an accessible reference guide for parameterized complexity researchers. Then, we resolve the parameterized complexity of three problems when parameterized by the neighborhood diversity of a graph (we defer the definitions to the relevant sections). However, since our complexity results follow by applying an appropriate algorithm for IP, we also highlight our modeling results. Moreover, in the spirit of the optimality program (introduced by Marx [49]), we are not content with obtaining some FPT algorithm, but we attempt to decrease the dependence on the parameter $k$ as much as possible. This sometimes has the unintended consequence of increasing the polynomial dependence on the graph size $|G|$. We note this and, by combining several ideas, get the “best of both worlds”. Driving down the poly($|G|$) factor is in the spirit of “minding the poly($n$)” of Lokshtanov et al. [48].

We denote by $|G|$ the number of vertices of the graph $G$ and by $k$ its neighborhood diversity; graphs of neighborhood diversity $k$ have a succinct representation (constructible in linear time) with $O(k^2 \log |G|)$ bits and we assume to have such a representation on input.

### ► Theorem 1. CAPACITATED DOMINATING SET

(a) Has a convex IP model in $O(k^2)$ variables and can be solved in time and space $k^{O(k^2)} \log |G|$.

(b) Has an ILP model in $O(k^2)$ variables and $O(|G|)$ constraints, and can be solved in time $k^{O(k^2)} \text{poly}(|G|)$ and space $\text{poly}(k, |G|)$.

(c) Can be solved in time $k^{O(k)} \text{poly}(|G|)$ using model a and a proximity argument.

(d) Has a polynomial $\text{OPT} + k^2$ approximation algorithm by rounding a relaxation of a.

### ► Theorem 2. SUM COLORING

(a) Has an $n$-fold IP model in $O(k|G|)$ variables and $O(k^2|G|)$ constraints, and can be solved in time $k^{O(k^3)} |G|^2 \log^2 |G|$.

(b) Has a LINIP model in $O(2^k)$ variables and $k$ constraints with a non-separable convex objective, and can be solved in time $2^{2^k \log^2 |G|}$.

(c) Has a LINIP model in $O(2^k)$ variables and $O(2^k)$ constraints whose constraint matrix has dual treewidth $k+2$ and whose objective is separable convex, and can be solved in time $k^{O(k^2)} \log |G|$.

► **Theorem 3.** $\text{MAX-q-CUT}$ has a LINIP model with an indefinite quadratic objective and can be solved in time $g(q, k) \log |G|$ for some computable function $g$.

## 1.2 Related Work

Graphs of neighborhood diversity constitute an important stepping stone in the design of algorithms for dense graphs, because they are in a sense the simplest of dense graphs [2, 3, 6, 20, 24, 25, 50]. Studying the complexity of CAPACITATED DOMINATING SET on graphs of bounded neighborhood diversity is especially interesting because it was shown to be W[1]-hard parameterized by treewidth by Dom et al. [13]. SUM COLORING was shown to be FPT parameterized by treewidth [32]; its complexity parameterized by clique-width is open as far as we know. $\text{MAX-q-CUT}$ is FPT parameterized by $q$ and treewidth (by reduction to CSP), but W[1]-hard parameterized by clique-width [21].
## 1.1 Our Results

We start by giving a quick overview of existing techniques in Section 2, which we hope to be an accessible reference guide for parameterized complexity researchers. Then, we resolve the parameterized complexity of three problems when parameterized by the neighborhood diversity of a graph (we defer the definitions to the relevant sections). However, since our complexity results follow by applying an appropriate algorithm for IP, we also highlight our modeling results. Moreover, in the spirit of the optimality program (introduced by Marx [49]), we are not content with obtaining some FPT algorithm, but we attempt to decrease the dependence on the parameter $k$ as much as possible. This sometimes has the unintended consequence of increasing the polynomial dependence on the graph size $|G|$. We note this and, by combining several ideas, get the “best of both worlds”. Driving down the poly($|G|$) factor is in the spirit of “minding the poly($n$)” of Lokshtanov et al. [48].

We denote by $|G|$ the number of vertices of the graph $G$ and by $k$ its neighborhood diversity; graphs of neighborhood diversity $k$ have a succinct representation (constructible in linear time) with $O(k^2 \log |G|)$ bits and we assume to have such a representation on input.

### ► Theorem 1. CAPACITATED DOMINATING SET

(a) Has a convex IP model in $O(k^2)$ variables and can be solved in time and space $k^{O(k^2)} \log |G|$.

(b) Has an ILP model in $O(k^2)$ variables and $O(|G|)$ constraints, and can be solved in time $k^{O(k^2)} \text{poly}(|G|)$ and space $\text{poly}(k, |G|)$.

(c) Can be solved in time $k^{O(k)} \text{poly}(|G|)$ using model a and a proximity argument.

(d) Has a polynomial $OPT + k^2$ approximation algorithm by rounding a relaxation of a.

### ► Theorem 2. SUM COLORING

(a) Has an $n$-fold IP model in $O(k|G|)$ variables and $O(k^2|G|)$ constraints, and can be solved in time $k^{O(k^3)} |G|^2 \log^2 |G|$.

(b) Has a LINIP model in $O(2^k)$ variables and $k$ constraints with a non-separable convex objective, and can be solved in time $2^{2^k \log^2 |G|}$.

(c) Has a LINIP model in $O(2^k)$ variables and $O(2^k)$ constraints whose constraint matrix has dual treewidth $k+2$ and whose objective is separable convex, and can be solved in time $k^{O(k^2)} \log |G|$.

► **Theorem 3.** MAX-$q$-CUT has a LINIP model with an indefinite quadratic objective and can be solved in time $g(q, k) \log |G|$ for some computable function $g$.

## 1.2 Related Work

Graphs of neighborhood diversity constitute an important stepping stone in the design of algorithms for dense graphs, because they are in a sense the simplest of dense graphs [2, 3, 6, 20, 24, 25, 50]. Studying the complexity of CAPACITATED DOMINATING SET on graphs of bounded neighborhood diversity is especially interesting because it was shown to be W[1]-hard parameterized by treewidth by Dom et al. [13]. SUM COLORING was shown to be FPT parameterized by treewidth [32]; its complexity parameterized by clique-width is open as far as we know. MAX-$q$-CUT is FPT parameterized by $q$ and treewidth (by reduction to CSP), but W[1]-hard parameterized by clique-width [21].
1.3 Preliminaries

For positive integers $m, n$ with $m \le n$ we set $[m, n] = \{m, \dots, n\}$ and $[n] = [1, n]$. We write vectors in boldface (e.g., $\mathbf{x}, \mathbf{y}$) and their entries in normal font (e.g., the $i$-th entry of $\mathbf{x}$ is $x_i$). For a graph $G$ we denote by $V(G)$ its set of vertices, by $E(G)$ the set of its edges, and by $N_G(v) = \{u \in V(G) \mid uv \in E(G)\}$ the (open) neighborhood of a vertex $v \in V(G)$. For a matrix $A$ we define

- the primal graph $G_P(A)$, which has a vertex for each column and two vertices are connected if there exists a row such that both columns are non-zero, and,

- the dual graph $G_D(A) = G_P(A^\top)$, which is the above with rows and columns swapped. We call the treedepth and treewidth of $G_P(A)$ the primal treedepth $\text{td}_P(A)$ and primal treewidth $\text{tw}_P(A)$, and analogously for the dual treedepth $\text{td}_D(A)$ and dual treewidth $\text{tw}_D(A)$.

We define a partial order $\sqsubseteq$ on $\mathbb{R}^n$ as follows: for $\mathbf{x}, \mathbf{y} \in \mathbb{R}^n$ we write $\mathbf{x} \sqsubseteq \mathbf{y}$ and say that $\mathbf{x}$ is conformal to $\mathbf{y}$ if $x_i y_i \ge 0$ (that is, $\mathbf{x}$ and $\mathbf{y}$ lie in the same orthant) and $|x_i| \le |y_i|$ for all $i \in [n]$. It is well known that every subset of $\mathbb{Z}^n$ has finitely many $\sqsubseteq$-minimal elements.

**Definition 4 (Graver basis).** The Graver basis of $A \in \mathbb{Z}^{m \times n}$ is the finite set $\mathcal{G}(A) \subset \mathbb{Z}^n$ of $\sqsubseteq$-minimal elements in $\{\mathbf{x} \in \mathbb{Z}^n \mid A\mathbf{x} = 0, \mathbf{x} \neq \mathbf{0}\}$.

**Neighborhood Diversity.** Two vertices $u, v$ are called twins if $N(u) \setminus \{v\} = N(v) \setminus \{u\}$. The twin equivalence is the relation on vertices of a graph where two vertices are equivalent if and only if they are twins.

**Definition 5 (Lampis [44]).** The neighborhood diversity of a graph $G$, denoted by $\text{nd}(G)$, is the minimum number $k$ of classes (called types) of the twin equivalence of $G$.

We denote by $V_i$ the classes of twin equivalence on $G$ for $i \in [k]$. A graph $G$ with $\text{nd}(G) = k$ can be described in a compressed way using only $\mathcal{O}(\log |G| \cdot k^2)$ space by its type graph, which is computable in linear time [44]:

**Definition 6.** The type graph $T(G)$ of a graph $G$ is a graph on $k = \text{nd}(G)$ vertices $[k]$, where each $i$ is assigned weight $|V_i|$, and where $i, j$ is an edge or a loop in $T(G)$ if and only if two distinct vertices of $V_i$ and $V_j$ are adjacent.

**Modeling.** Loosely speaking, by modeling an optimization problem $\Pi$ as a different problem $\Lambda$ we mean encoding the features of $\Pi$ by the features of $\Lambda$, such that the optima of $\Lambda$ encode at least some optima of $\Pi$. Modeling differs from reduction by highlighting which features of $\Pi$ are captured by which features of $\Lambda$.

In particular, when modeling $\Pi$ as an integer program, the same feature of $\Pi$ can often be encoded in several ways by the variables, constraints or the objective. For example, an objective of $\Pi$ may be encoded as a convex objective of the IP, or as a linear objective which is lower bounded by a convex constraint; similarly a constraint of $\Pi$ may be modeled as a linear constraint of IP or as minimizing a penalty objective function expressing how much is the constraint violated. Such choices greatly influence which algorithms are applicable to solve the resulting model. Specifically, in our models we focus on the parameters $\#\text{variables}$ (dimension), $\#\text{constraints}$, the largest coefficient in the constraints $\|A\|_\infty$ (abusing the notation slightly when the constraints are not linear), the largest right hand side $\|\mathbf{b}\|_\infty$, the largest domain $\|\mathbf{u} - \mathbf{l}\|_\infty$, and the largest coefficient of the objective function $\|\mathbf{w}\|_\infty$ (linear objectives), $\|Q\|_\infty$ (quadratic objectives) or $f_{\max} = \max_{\mathbf{x}:1 \le \mathbf{x} \le \mathbf{u}} |f(\mathbf{x})|$ (in general), and noting other relevant features.
1.3 Preliminaries

For positive integers $m, n$ with $m \le n$ we set $[m, n] = \{m, \dots, n\}$ and $[n] = [1, n]$. We write vectors in boldface (e.g., $\mathbf{x}, \mathbf{y}$) and their entries in normal font (e.g., the $i$-th entry of $\mathbf{x}$ is $x_i$). For a graph $G$ we denote by $V(G)$ its set of vertices, by $E(G)$ the set of its edges, and by $N_G(v) = \{u \in V(G) \mid uv \in E(G)\}$ the (open) neighborhood of a vertex $v \in V(G)$. For a matrix $A$ we define

- the primal graph $G_P(A)$, which has a vertex for each column and two vertices are connected if there exists a row such that both columns are non-zero, and,

- the dual graph $G_D(A) = G_P(A^\top)$, which is the above with rows and columns swapped. We call the treedepth and treewidth of $G_P(A)$ the primal treedepth $\text{td}_P(A)$ and primal treewidth $\text{tw}_P(A)$, and analogously for the dual treedepth $\text{td}_D(A)$ and dual treewidth $\text{tw}_D(A)$.

We define a partial order $\sqsubseteq$ on $\mathbb{R}^n$ as follows: for $\mathbf{x}, \mathbf{y} \in \mathbb{R}^n$ we write $\mathbf{x} \sqsubseteq \mathbf{y}$ and say that $\mathbf{x}$ is conformal to $\mathbf{y}$ if $x_i y_i \ge 0$ (that is, $\mathbf{x}$ and $\mathbf{y}$ lie in the same orthant) and $|x_i| \le |y_i|$ for all $i \in [n]$. It is well known that every subset of $\mathbb{Z}^n$ has finitely many $\sqsubseteq$-minimal elements.

**Definition 4 (Graver basis).** The Graver basis of $A \in \mathbb{Z}^{m \times n}$ is the finite set $\mathcal{G}(A) \subset \mathbb{Z}^n$ of $\sqsubseteq$-minimal elements in $\{\mathbf{x} \in \mathbb{Z}^n \mid A\mathbf{x} = 0, \mathbf{x} \neq \mathbf{0}\}$.

**Neighborhood Diversity.** Two vertices $u, v$ are called twins if $N(u) \setminus \{v\} = N(v) \setminus \{u\}$. The twin equivalence is the relation on vertices of a graph where two vertices are equivalent if and only if they are twins.

**Definition 5 (Lampis [44]).** The neighborhood diversity of a graph $G$, denoted by $\text{nd}(G)$, is the minimum number $k$ of classes (called types) of the twin equivalence of $G$.

We denote by $V_i$ the classes of twin equivalence on $G$ for $i \in [k]$. A graph $G$ with $\text{nd}(G) = k$ can be described in a compressed way using only $\mathcal{O}(\log |G| \cdot k^2)$ space by its type graph, which is computable in linear time [44]:

**Definition 6.** The type graph $T(G)$ of a graph $G$ is a graph on $k = \text{nd}(G)$ vertices $[k]$, where each $i$ is assigned weight $|V_i|$, and where $i, j$ is an edge or a loop in $T(G)$ if and only if two distinct vertices of $V_i$ and $V_j$ are adjacent.

**Modeling.** Loosely speaking, by modeling an optimization problem $\Pi$ as a different problem $\Lambda$ we mean encoding the features of $\Pi$ by the features of $\Lambda$, such that the optima of $\Lambda$ encode at least some optima of $\Pi$. Modeling differs from reduction by highlighting which features of $\Pi$ are captured by which features of $\Lambda$.

In particular, when modeling $\Pi$ as an integer program, the same feature of $\Pi$ can often be encoded in several ways by the variables, constraints or the objective. For example, an objective of $\Pi$ may be encoded as a convex objective of the IP, or as a linear objective which is lower bounded by a convex constraint; similarly a constraint of $\Pi$ may be modeled as a linear constraint of IP or as minimizing a penalty objective function expressing how much is the constraint violated. Such choices greatly influence which algorithms are applicable to solve the resulting model. Specifically, in our models we focus on the parameters $\#\text{variables}$ (dimension), $\#\text{constraints}$, the largest coefficient in the constraints $\|A\|_\infty$ (abusing the notation slightly when the constraints are not linear), the largest right hand side $\|\mathbf{b}\|_\infty$, the largest domain $\|\mathbf{u} - \mathbf{l}\|_\infty$, and the largest coefficient of the objective function $\|\mathbf{w}\|_\infty$ (linear objectives), $\|Q\|_\infty$ (quadratic objectives) or $f_{\max} = \max_{\mathbf{x}:1 \le \mathbf{x} \le \mathbf{u}} |f(\mathbf{x})|$ (in general), and noting other relevant features.
**Solution structure.** We concur with Downey and Fellows that FPT and structure are essentially one [14]. Here, it typically means restricting our attention to certain structured solutions and showing that nevertheless such structured solutions contain optima of the problem at hand. We always discuss these structural properties before formulating a model.

## 2 Integer Programming Toolbox

We give a list of the most relevant algorithms solving IP, highlighting their fastest known
runtimes (marked $\top$), typical use cases and strengths (+), limitations (-), and a list
of references to the algorithms (♡) and their most illustrative applications (▷), both in
chronological order.

### 2.1 Small Dimension

The following tools generally rely on results from discrete geometry.

**ILP in small dimension.** Problem (ILP) with small $n$.

$$ \top n^{2.5n} \langle A, b, w \rangle \text{ [36, 22]} $$

+ Can use large coefficients, which allows encoding logical connectives using Big-$M$ coefficients [5]. Runs in polynomial space. Most people familiar with ILP.

- Small dimension can be an obstacle in modeling polynomially many “types” of objects [7, Challenge #2]. Models often use exponentially many variables in the parameter, leading to double-exponential runtimes (applies to all small dimension techniques below). Encoding a convex objective or constraint requires many constraints (cf. Model 9). Big-$M$ coefficients are impractical.

$$ \heartsuit \text{ [45, 36, 22]} $$

$$ \triangleright \text{ [52, 19, 35, 20, 18]} $$

**Convex IP in small dimension.** Problem (IP) with $f$ a convex function; $S$ can be represented by polynomial inequalities, a first-order oracle, a separation oracle, or as a semialgebraic set.

$$ \top n^{\frac{4}{3}n} \langle B \rangle, \text{ where } S \text{ is contained in a ball of radius } B \text{ [12].} $$

+ Strictly stronger than ILP. Representing constraints implicitly by an oracle allows better dependence on instance size (cf. Model 8).

- Exponential space. Algorithms usually impractical. Proving convexity can be difficult.

$$ \heartsuit \text{ [26, Theorem 6.7.10] (weak separation oracle), [37] (semialgebraic sets), [27, 31] (polynomials), [11] randomized / [12] deterministic (strong separation oracle), [53] reduction to Mixed ILP subproblems (first-order oracle).} $$

$$ \triangleright \text{ [30, 8, 51, 38, 41], Model 8} $$

**Indefinite quadratic IP in small dimension.** Problem (LinIP) with $f(x) = x^\top Q x$ indefinite (non-convex) quadratic.

$$ \top g(n, \|A\|_{\infty}, \|Q\|_{\infty}) \langle b \rangle \text{ [55]} $$

+ Currently the only tractable indefinite objective.

- Limiting parameterization.

$$ \heartsuit \text{ [47, 55]} $$

$$ \triangleright \text{ [47], Model 10} $$
**Solution structure.** We concur with Downey and Fellows that FPT and structure are essentially one [14]. Here, it typically means restricting our attention to certain structured solutions and showing that nevertheless such structured solutions contain optima of the problem at hand. We always discuss these structural properties before formulating a model.

## 2 Integer Programming Toolbox

We give a list of the most relevant algorithms solving IP, highlighting their fastest known
runtimes (marked $\top$), typical use cases and strengths (+), limitations (-), and a list
of references to the algorithms (♡) and their most illustrative applications (▷), both in
chronological order.

### 2.1 Small Dimension

The following tools generally rely on results from discrete geometry.

**ILP in small dimension.** Problem (ILP) with small $n$.

$$ \top n^{2.5n} \langle A, b, w \rangle \text{ [36, 22]} $$

+ Can use large coefficients, which allows encoding logical connectives using Big-$M$ coefficients [5]. Runs in polynomial space. Most people familiar with ILP.

- Small dimension can be an obstacle in modeling polynomially many “types” of objects [7, Challenge #2]. Models often use exponentially many variables in the parameter, leading to double-exponential runtimes (applies to all small dimension techniques below). Encoding a convex objective or constraint requires many constraints (cf. Model 9). Big-$M$ coefficients are impractical.

$$ \heartsuit \text{ [45, 36, 22]} $$

$$ \triangleright \text{ [52, 19, 35, 20, 18]} $$

**Convex IP in small dimension.** Problem (IP) with $f$ a convex function; $S$ can be represented by polynomial inequalities, a first-order oracle, a separation oracle, or as a semialgebraic set.

$$ \top n^{\frac{4}{3}n} \langle B \rangle, \text{ where } S \text{ is contained in a ball of radius } B \text{ [12].} $$

+ Strictly stronger than ILP. Representing constraints implicitly by an oracle allows better dependence on instance size (cf. Model 8).

- Exponential space. Algorithms usually impractical. Proving convexity can be difficult.

$$ \heartsuit \text{ [26, Theorem 6.7.10] (weak separation oracle), [37] (semialgebraic sets), [27, 31] (polynomials), [11] randomized / [12] deterministic (strong separation oracle), [53] reduction to Mixed ILP subproblems (first-order oracle).} $$

$$ \triangleright \text{ [30, 8, 51, 38, 41], Model 8} $$

**Indefinite quadratic IP in small dimension.** Problem (LinIP) with $f(x) = x^\top Q x$ indefinite (non-convex) quadratic.

$$ \top g(n, \|A\|_{\infty}, \|Q\|_{\infty}) \langle b \rangle \text{ [55]} $$

+ Currently the only tractable indefinite objective.

- Limiting parameterization.

$$ \heartsuit \text{ [47, 55]} $$

$$ \triangleright \text{ [47], Model 10} $$
21:6 Integer Programming in Parameterized Complexity: Three Miniatures

**Parametric ILP in small dimension.** Given a $Q = \{\mathbf{b} \in \mathbb{R}^m \mid B\mathbf{b} \le \mathbf{d}\}$, decide

$$ \forall \mathbf{b} \in Q \cap \mathbb{Z}^m \exists \mathbf{x} \in \mathbb{Z}^n : A\mathbf{x} \le \mathbf{b}. $$

$$ \supset g(n, m) \text{poly}(\|A, B, \mathbf{d}\|_{\infty}) \text{ [16]} $$

+ Models one quantifier alternation. Useful in expressing game-like constraints (e.g., “forall moves ∃ a counter-move”). Allows unary big-$M$ coefficients to model logic [42, Theorem 4.5].

- Input has to be given in unary (vs. e.g. Lenstra's algorithm).

- [16, Theorem 4.2], [10, Corollary 1]

- [10, 42]

## 2.2 Variable Dimension

In this section it will be more natural to consider the following standard form of (LinIP)

$$ \min\{f(\mathbf{x}) \mid A\mathbf{x} = \mathbf{b}, \mathbf{l} \le \mathbf{x} \le \mathbf{u}, \mathbf{x} \in \mathbb{Z}^n\}, \qquad (\text{SLinIP}) $$

where $\mathbf{b} \in \mathbb{Z}^m$ and $\mathbf{l}, \mathbf{u} \in \mathbb{Z}^n$. Let $L = \langle f_{\max}, \mathbf{b}, \mathbf{l}, \mathbf{u} \rangle$. In contrast with the previous section, the following algorithms typically rely on algebraic arguments and dynamic programming.

**ILP with few rows.** Problem (SLinIP) with small $m$ and a linear objective $w\mathbf{x}$ for $w \in \mathbb{Z}^n$.

$$ \supset \mathcal{O}((m\|A\|_{\infty})^{2m})\langle \mathbf{b} \rangle \text{ if } \mathbf{l} = \mathbf{0} \text{ and } \mathbf{u} = +\infty, \text{ and } n \cdot (m\|A\|_{\infty})^{O(m^2)}\langle \mathbf{b}, \mathbf{l}, \mathbf{u} \rangle \text{ in general [34]} $$

+ Useful for configuration IPs with small coefficients, leading to exponential speed-ups. Best runtime in the case without upper bounds. Linear dependence on $n$.

- Limited modeling power. Requires small coefficients.

- [54, 17, 34]

- [34]

$$ A_{\text{nfold}} = \begin{pmatrix} A_1 & A_1 & \cdots & A_1 \\ A_2 & 0 & \cdots & 0 \\ 0 & A_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & A_2 \end{pmatrix} $$

$$ A_{\text{stoch}} = \begin{pmatrix} B_1 & B_2 & 0 & \cdots & 0 \\ B_1 & 0 & B_2 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ B_1 & 0 & 0 & \cdots & B_2 \end{pmatrix} $$

**n-fold IP, tree-fold IP, and dual treedepth.** n-fold IP is problem (SLinIP) in dimension $nt$, with $A = A_{\text{nfold}}$ for some two blocks $A_1 \in \mathbb{Z}^{r \times t}$ and $A_2 \in \mathbb{Z}^{s \times t}$, $\mathbf{l}, \mathbf{u} \in \mathbb{Z}^{nt}$, $\mathbf{b} \in \mathbb{Z}^{r+ns}$, and with $f$ a separable convex function, i.e., $f(\mathbf{x}) = \sum_{i=1}^{n} \sum_{j=1}^{t} f_j^i(x_j^i)$ with each $f_j^i: \mathbb{Z} \to \mathbb{Z}$ convex. Tree-fold IP is a generalization of n-fold IP where the block $A_2$ is itself replaced by an n-fold matrix, and so on, recursively, $\tau$ times. Tree-fold IP has bounded $\text{td}_D(A)$.

$$ \supset (\|A\|_{\infty}rs)^{O(r^2s+rs^2)}(nt)^2 \log(nt)\langle L \rangle \text{ n-fold IP [1, 15]; } (\|A\|_{\infty} + 1)^{2^{td_D(A)}}(nt)^2 \log(nt)\langle L \rangle \text{ for (SLinIP) [43].} $$

+ Variable dimension useful in modeling many “types” of objects [40, 42]. Useful for obtaining exponential speed-ups (not only configuration IPs). Seemingly rigid format is in fact not problematic (blocks can be different provided coefficients and dimensions are small).

- Requires small coefficients.

- [28, 39, 9, 15, 1, 43]

- [38, 40, 39, 9, 33], Model 11
21:6 Integer Programming in Parameterized Complexity: Three Miniatures

**Parametric ILP in small dimension.** Given a $Q = \{\mathbf{b} \in \mathbb{R}^m \mid B\mathbf{b} \le \mathbf{d}\}$, decide

$$ \forall \mathbf{b} \in Q \cap \mathbb{Z}^m \exists \mathbf{x} \in \mathbb{Z}^n : A\mathbf{x} \le \mathbf{b}. $$

$$ \supset g(n, m) \text{poly}(\|A, B, \mathbf{d}\|_{\infty}) [16] $$

+ Models one quantifier alternation. Useful in expressing game-like constraints (e.g., “forall moves ∃ a counter-move”). Allows unary big-$M$ coefficients to model logic [42, Theorem 4.5].

- Input has to be given in unary (vs. e.g. Lenstra's algorithm).

[16, Theorem 4.2], [10, Corollary 1]

▷ [10, 42]

2.2 Variable Dimension

In this section it will be more natural to consider the following standard form of (LinIP)

$$ \min\{f(\mathbf{x}) \mid A\mathbf{x} = \mathbf{b}, \mathbf{l} \le \mathbf{x} \le \mathbf{u}, \mathbf{x} \in \mathbb{Z}^n\}, \qquad (\text{SLinIP}) $$

where $\mathbf{b} \in \mathbb{Z}^m$ and $\mathbf{l}, \mathbf{u} \in \mathbb{Z}^n$. Let $L = \langle f_{\max}, \mathbf{b}, \mathbf{l}, \mathbf{u} \rangle$. In contrast with the previous section, the following algorithms typically rely on algebraic arguments and dynamic programming.

**ILP with few rows.** Problem (SLinIP) with small $m$ and a linear objective $w\mathbf{x}$ for $w \in \mathbb{Z}^n$.

$$ \supset \mathcal{O}((m\|A\|_{\infty})^{2m})\langle \mathbf{b} \rangle \text{ if } \mathbf{l} = \mathbf{0} \text{ and } \mathbf{u} = +\infty, \text{ and } n \cdot (m\|A\|_{\infty})^{O(m^2)}\langle \mathbf{b}, \mathbf{l}, \mathbf{u} \rangle \text{ in general [34]} $$

+ Useful for configuration IPs with small coefficients, leading to exponential speed-ups. Best runtime in the case without upper bounds. Linear dependence on $n$.

- Limited modeling power. Requires small coefficients.

♡ [54, 17, 34]

▷ [34]

$$ A_{\text{nfold}} = \begin{pmatrix} A_1 & A_1 & \cdots & A_1 \\ A_2 & 0 & \cdots & 0 \\ 0 & A_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & A_2 \end{pmatrix} $$

$$ A_{\text{stoch}} = \begin{pmatrix} B_1 & B_2 & 0 & \cdots & 0 \\ B_1 & 0 & B_2 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ B_1 & 0 & 0 & \cdots & B_2 \end{pmatrix} $$

**n-fold IP, tree-fold IP, and dual treedepth.** n-fold IP is problem (SLinIP) in dimension $nt$, with $A = A_{\text{nfold}}$ for some two blocks $A_1 \in \mathbb{Z}^{r \times t}$ and $A_2 \in \mathbb{Z}^{s \times t}$, $\mathbf{l}, \mathbf{u} \in \mathbb{Z}^{nt}$, $\mathbf{b} \in \mathbb{Z}^{r+ns}$, and with $f$ a separable convex function, i.e., $f(\mathbf{x}) = \sum_{i=1}^{n} \sum_{j=1}^{t} f_j^i(x_j^i)$ with each $f_j^i: \mathbb{Z} \to \mathbb{Z}$ convex. Tree-fold IP is a generalization of n-fold IP where the block $A_2$ is itself replaced by an n-fold matrix, and so on, recursively, $\tau$ times. Tree-fold IP has bounded $\text{td}_D(A)$.

$$ \supset (\|A\|_{\infty}rs)^{O(r^2s+rs^2)}(nt)^2 \log(nt)\langle L \rangle \text{ n-fold IP [1, 15]; } (\|A\|_{\infty} + 1)^{2^{td_D(A)}}(nt)^2 \log(nt)\langle L \rangle \text{ for (SLinIP) [43].} $$

+ Variable dimension useful in modeling many “types” of objects [40, 42]. Useful for obtaining exponential speed-ups (not only configuration IPs). Seemingly rigid format is in fact not problematic (blocks can be different provided coefficients and dimensions are small).

- Requires small coefficients.

♡ [28, 39, 9, 15, 1, 43]

▷ [38, 40, 39, 9, 33], Model 11
**2-stage and multi-stage stochastic IP, and primal treedepth.** 2-stage stochastic IP is problem (SLinIP) with $A = A_{\text{stoch}}$ and $f$ a separable convex function; multi-stage stochastic IP is problem (SLinIP) with a multi-stage stochastic matrix, which is the transpose of a tree-fold matrix; multi-stage stochastic IP is in turn generalized by IP with small primal treedepth $\text{td}_P(A)$.

$$ \top g(\text{td}_P(A), \|A\|_{\infty})n^2 \log n \langle L \rangle, g \text{ computable [43]} $$

+ Similar to Parametric ILP in fixed dimension, but quantification $\forall \mathbf{b} \in Q \cap \mathbb{Z}^n$ is now over a polynomial sized but possibly non-convex set of explicitly given right hand sides.

- Not clear which problems are captured. Requires small coefficients. Parameter dependence $g$ is possibly non-elementary; no upper bounds on $g$ are known, only computability.

♡ [29, 4, 43]

▷ N/A

**Small treewidth and Graver norms.** Let $g_{\infty}(A) = \max_{g \in \mathcal{G}(A)} \|g\|_{\infty}$ and $g_1(A) = \max_{g \in \mathcal{G}(A)} \|g\|_1$ be maximum norms of elements of $\mathcal{G}(A)$.

$$ \top \min\{g_{\infty}(A)^{\mathcal{O}(\text{tw}_P(A))}, g_1(A)^{\mathcal{O}(\text{tw}_D(A))}\} n^2 \log n \langle L \rangle \text{ [43]} $$

+ Captures IPs beyond the classes defined above (cf. Section 5.3).

- Bounding $g_1(A)$ and $g_{\infty}(A)$ is often hard or impossible.

♡ [43]

▷ Model 14

# 3 Convex Constraints: Capacitated Dominating Set

## CAPACITATED DOMINATING SET

**Input:** A graph $G = (V, E)$ and a capacity function $c: V \to \mathbb{N}$.

**Task:** Find a smallest possible set $D \subseteq V$ and a mapping $\delta: V \setminus D \to D$ such that for each $v \in D$, $|\delta^{-1}(v)| \le c(v)$.

**Solution Structure.** Let $<_c$ be a linear extension of ordering of $V$ by vertex capacities, i.e., $u <_c v$ if $c(u) \le c(v)$. For $i \in T(G)$ and $\ell \in [|V_i|]$ let $V_i[1:\ell]$ be the set of the first $\ell$ vertices of $V_i$ in the ordering $<_c$ and let $f_i(\ell) = \sum_{v \in V_i[2:\ell]} c(v)$; for $\ell > |V_i|$ let $f_i(\ell) = f_i(|V_i|)$. Let $D$ be a solution and $D_i = D \cap V_i$. We call the functions $f_i$ the *domination capacity functions*. Intuitively, $f_i(\ell)$ is the maximum number of vertices dominated by $V_i[1: \ell]$. Observe that since $f_i(\ell)$ is a partial sum of a non-increasing sequence of numbers, it is a piece-wise linear concave function. We say that $D$ is *capacity-ordered* if, for each $i \in T(G)$, $D_i = V_i[1:|D_i|]$. The following observation allows us to restrict our attention to such solutions; the proof goes by a simple exchange argument.

**► Lemma 7 (★).** *There is a capacity-ordered optimal solution.*

Observe that a capacity-ordered solution is fully determined by the sizes $|D_i|$ and $<_c$ rather than the actual sets $D_i$, which allows modeling CDS in small dimension.

**► Model 8 (CAPACITATED DOMINATING SET as convex IP in fixed dimension).**

**Variables & notation:**

- $x_i = |D_i|$

- $y_{ij} = |\delta^{-1}(D_i) \cap D_j|$

- $f_i(x_i)$ = maximum #vertices dominated by $D_i$ if $|D_i| = x_i$
**2-stage and multi-stage stochastic IP, and primal treedepth.** 2-stage stochastic IP is problem (SLinIP) with $A = A_{\text{stoch}}$ and $f$ a separable convex function; multi-stage stochastic IP is problem (SLinIP) with a multi-stage stochastic matrix, which is the transpose of a tree-fold matrix; multi-stage stochastic IP is in turn generalized by IP with small primal treedepth $\text{td}_P(A)$.

$$ \top g(\text{td}_P(A), \|A\|_{\infty})n^2 \log n \langle L \rangle, g \text{ computable [43]} $$

+ Similar to Parametric ILP in fixed dimension, but quantification $\forall \mathbf{b} \in Q \cap \mathbb{Z}^n$ is now over a polynomial sized but possibly non-convex set of explicitly given right hand sides.

- Not clear which problems are captured. Requires small coefficients. Parameter dependence $g$ is possibly non-elementary; no upper bounds on $g$ are known, only computability.

♡ [29, 4, 43]

▷ N/A

**Small treewidth and Graver norms.** Let $g_{\infty}(A) = \max_{g \in \mathcal{G}(A)} \|g\|_{\infty}$ and $g_1(A) = \max_{g \in \mathcal{G}(A)} \|g\|_1$ be maximum norms of elements of $\mathcal{G}(A)$.

$$ \top \min\{g_{\infty}(A)^{\mathcal{O}(\text{tw}_P(A))}, g_1(A)^{\mathcal{O}(\text{tw}_D(A))}\}n^2 \log n \langle L \rangle \text{ [43]} $$

+ Captures IPs beyond the classes defined above (cf. Section 5.3).

- Bounding $g_1(A)$ and $g_{\infty}(A)$ is often hard or impossible.

♡ [43]

▷ Model 14

# 3 Convex Constraints: Capacitated Dominating Set

## CAPACITATED DOMINATING SET

**Input:** A graph $G = (V, E)$ and a capacity function $c: V \to \mathbb{N}$.

**Task:** Find a smallest possible set $D \subseteq V$ and a mapping $\delta: V \setminus D \to D$ such that for each $v \in D$, $|\delta^{-1}(v)| \le c(v)$.

**Solution Structure.** Let $<_c$ be a linear extension of ordering of $V$ by vertex capacities, i.e., $u <_c v$ if $c(u) \le c(v)$. For $i \in T(G)$ and $\ell \in [|V_i|]$ let $V_i[1:\ell]$ be the set of the first $\ell$ vertices of $V_i$ in the ordering $<_c$ and let $f_i(\ell) = \sum_{v \in V_i[2:\ell]} c(v)$; for $\ell > |V_i|$ let $f_i(\ell) = f_i(|V_i|)$. Let $D$ be a solution and $D_i = D \cap V_i$. We call the functions $f_i$ the *domination capacity functions*. Intuitively, $f_i(\ell)$ is the maximum number of vertices dominated by $V_i[1: \ell]$. Observe that since $f_i(\ell)$ is a partial sum of a non-increasing sequence of numbers, it is a piece-wise linear concave function. We say that $D$ is *capacity-ordered* if, for each $i \in T(G)$, $D_i = V_i[1:|D_i|]$. The following observation allows us to restrict our attention to such solutions; the proof goes by a simple exchange argument.

**► Lemma 7 (★).** *There is a capacity-ordered optimal solution.*

Observe that a capacity-ordered solution is fully determined by the sizes $|D_i|$ and $<_c$ rather than the actual sets $D_i$, which allows modeling CDS in small dimension.

**► Model 8 (CAPACITATED DOMINATING SET as convex IP in fixed dimension).**

**Variables & notation:**

- $x_i = |D_i|$

- $y_{ij} = |\delta^{-1}(D_i) \cap D_j|$

- $f_i(x_i)$ = maximum #vertices dominated by $D_i$ if $|D_i| = x_i$
**[Speed trade-offs] Proof of Theorem 1c.** Notice that on our way to proving Theorem 1d we have shown that Model 8 has integrality gap at most $k^2$, i.e., the value of the continuous optimum is at most $k^2$ less than the value of the integer optimum. This implies that an integer optimum $(\mathbf{x}^*, \mathbf{y}^*)$ satisfies, for each $i \in [k]$, $\max\{0, \lfloor x_i - k^2 \rfloor\} \le x_i^* \le \min\{|V_i|, x_i + \lfloor k^2 \rfloor\}$.

We can exploit this to improve Theorem 1a in terms of the parameter dependence at the cost of the dependence on $|G|$. Let us assume that we have a way to test, for a given integer vector $\hat{\mathbf{x}}$, whether it models a capacity-ordered solution, that is, whether there exists a capacitated dominating set with $D_i = V_i[1: \hat{x}_i]$ for each $i$. Then we can simply go over all possible $(2k^2 + 2)^k$ choices of $\hat{\mathbf{x}}$ and choose the best. So we are left with the task of, given a vector $\hat{\mathbf{x}}$, deciding if it models a capacity-ordered solution.

But this is easy. Let $<_c$ be the assumed order and define $D$ as above. Now, we construct an auxiliary bipartite matching problem, where we put $c(v)$ copies of each vertex from $D$ on one side of the graph, and all vertices of $V \setminus D$ on the other side, and connect a copy of $v \in D$ to $u \in V \setminus D$ if $uv \in E(G)$. Then, $D$ is a capacitated dominating set if and only if all vertices in $V \setminus D$ can be matched. The algorithm is then simply to compute the continuous optimum $\mathbf{x}$, and go over all integer vectors $\hat{\mathbf{x}}$ with $\|\mathbf{x} - \hat{\mathbf{x}}\|_1 \le k^2$, verifying whether they model a solution and choosing the smallest (best) one. ◀

## 4 Indefinite Quadratics: Max q-Cut

### MAX-q-CUT

**Input:** A graph $G = (V, E)$.

**Task:** A partition $W_1 \cup \cdots \cup W_q = V$ maximizing the number of edges between distinct $W_\alpha$ and $W_\beta$, i.e., $|\{uv \in E(G) \mid u \in W_\alpha, v \in W_\beta, \alpha \neq \beta\}|$.

**Solution structure.** As before, it is enough to describe how many vertices from type $i \in T(G)$ belong to $W_\alpha$ for $\alpha \in [q]$, and their specific choice does not matter; this gives us a small dimensional encoding of the solutions.

### ► Model 10 (MAX-q-CUT as LINIP with indefinite quadratic objective).

**Variables & Notation:**

- $x_{i\alpha} = |V_i \cap W_\alpha|$

- $x_{i\alpha} \cdot x_{j\beta} = \#\text{edges between } V_i \cap W_\alpha \text{ and } V_j \cap W_\beta \text{ if } ij \in E(T(G))$.

**Objective & Constraints:**

$$ \min \sum_{\substack{\alpha, \beta \in [q] \\ \alpha \neq \beta}} \sum_{ij \in E(T(G))} x_{i\alpha} \cdot x_{j\beta} \qquad \text{min \#edges across partites} \quad \text{(mc:obj)} $$

$$ \sum_{\alpha \in [q]} x_{i\alpha} = |V_i| \qquad \forall i \in T(G) \quad (V_i \cap W_\alpha)_{\alpha \in [q]} \text{ partitions } V_i \quad \text{(mc:part)} $$

**Parameters & Notes:**

- \#vars $\qquad$ \#constraints $\qquad$ $\|A\|_\infty$ $\qquad$ $\|\mathbf{b}\|_\infty$ $\qquad$ $\|\mathbf{l}, \mathbf{u}\|_\infty$ $\qquad$ $\|Q\|_\infty$

- objective (mc:obj) is indefinite quadratic.

Applying Lokshtanov's [47] or Zemmer's [55] algorithm to Model 10 yields Theorem 3. Note that since we do not know anything about the objective except that it is quadratic, we have to make sure that $\|Q\|_\infty$ and $\|A\|_\infty$ are small.
[Speed trade-offs] Proof of Theorem 1c. Notice that on our way to proving Theorem 1d we have shown that Model 8 has integrality gap at most $k^2$, i.e., the value of the continuous optimum is at most $k^2$ less than the value of the integer optimum. This implies that an integer optimum $(\mathbf{x}^*, \mathbf{y}^*)$ satisfies, for each $i \in [k]$, $\max\{0, \lfloor x_i - k^2 \rfloor\} \le x_i^* \le \min\{|V_i|, x_i + \lfloor k^2 \rfloor\}$.

We can exploit this to improve Theorem 1a in terms of the parameter dependence at the cost of the dependence on $|G|$. Let us assume that we have a way to test, for a given integer vector $\hat{\mathbf{x}}$, whether it models a capacity-ordered solution, that is, whether there exists a capacitated dominating set with $D_i = V_i[1: \hat{x}_i]$ for each $i$. Then we can simply go over all possible $(2k^2 + 2)^k$ choices of $\hat{\mathbf{x}}$ and choose the best. So we are left with the task of, given a vector $\hat{\mathbf{x}}$, deciding if it models a capacity-ordered solution.

But this is easy. Let $<_c$ be the assumed order and define $D$ as above. Now, we construct an auxiliary bipartite matching problem, where we put $c(v)$ copies of each vertex from $D$ on one side of the graph, and all vertices of $V \setminus D$ on the other side, and connect a copy of $v \in D$ to $u \in V \setminus D$ if $uv \in E(G)$. Then, $D$ is a capacitated dominating set if and only if all vertices in $V \setminus D$ can be matched. The algorithm is then simply to compute the continuous optimum $\mathbf{x}$, and go over all integer vectors $\hat{\mathbf{x}}$ with $\|\mathbf{x} - \hat{\mathbf{x}}\|_1 \le k^2$, verifying whether they model a solution and choosing the smallest (best) one. ◀

## 4 Indefinite Quadratics: Max q-Cut

### MAX-q-CUT

**Input:** A graph $G = (V, E)$.

**Task:** A partition $W_1 \cup \dots \cup W_q = V$ maximizing the number of edges between distinct $W_\alpha$ and $W_\beta$, i.e., $|\{uv \in E(G) \mid u \in W_\alpha, v \in W_\beta, \alpha \neq \beta\}|$.

**Solution structure.** As before, it is enough to describe how many vertices from type $i \in T(G)$ belong to $W_\alpha$ for $\alpha \in [q]$, and their specific choice does not matter; this gives us a small dimensional encoding of the solutions.

### ► Model 10 (MAX-q-CUT as LINIP with indefinite quadratic objective).

**Variables & Notation:**

- $x_{i\alpha} = |V_i \cap W_\alpha|$

- $x_{i\alpha} \cdot x_{j\beta} = \#\text{edges between } V_i \cap W_\alpha \text{ and } V_j \cap W_\beta \text{ if } ij \in E(T(G))$.

**Objective & Constraints:**

$$ \min \sum_{\substack{\alpha,\beta \in [q]: \\ \alpha \neq \beta}} \sum_{ij \in E(T(G))} x_{i\alpha} \cdot x_{j\beta} \qquad \text{min \#edges across partites} \quad \text{(mc:obj)} $$

$$ \sum_{\alpha \in [q]} x_{i\alpha} = |V_i| \qquad \forall i \in T(G) \quad (V_i \cap W_\alpha)_{\alpha \in [q]} \text{ partitions } V_i \quad \text{(mc:part)} $$

**Parameters & Notes:**

- \#vars $\qquad$ \#constraints $\qquad$ $\|A\|_\infty$ $\qquad$ $\|\mathbf{b}\|_\infty$ $\qquad$ $\|\mathbf{l}, \mathbf{u}\|_\infty$ $\qquad$ $\|Q\|_\infty$

- objective (mc:obj) is indefinite quadratic.

Applying Lokshtanov's [47] or Zemmer's [55] algorithm to Model 10 yields Theorem 3. Note that since we do not know anything about the objective except that it is quadratic, we have to make sure that $\|Q\|_\infty$ and $\|A\|_\infty$ are small.
## 5 Convex Objective: Sum Coloring

### SUM COLORING

**Input:** A graph $G = (V, E)$.

**Task:** A proper coloring $c: V \to \mathbb{N}$ minimizing $\sum_{v \in V} c(v)$.

In the following we first give a single-exponential algorithm for SUM COLORING with a polynomial dependence on $|G|$, then a double-exponential algorithm with a logarithmic dependence on $|G|$, and finally show how to combine the two ideas together to obtain a single-exponential algorithm with a logarithmic dependence on $|G|$.

### 5.1 Sum Coloring via n-fold IP

**Structure of Solution.** The following observation was made by Lampis [44] for the COLORING problem, and it holds also for the SUM COLORING problem: every color $C \subseteq V(G)$ intersects each clique type in at most one vertex, and each independent type in either none or all of its vertices. The first follows simply by the fact that it is a clique; the second by the fact that if both colors $\alpha, \beta$ with $\alpha < \beta$ are used for an independent type, then recoloring all vertices of color $\beta$ to be of color $\alpha$ remains a valid coloring and decreases its cost. We call a coloring with this structure an essential coloring.

#### ► Model 11 (SUM COLORING as n-fold IP).

**Variables & Notation:**

- $x_i^\alpha = 1$ if color $\alpha$ intersects $V_i$

- $\alpha \cdot x_i^\alpha$ = cost of color $\alpha$ at a clique type $i$

- $\alpha|V_i| \cdot x_i^\alpha$ = cost of color $\alpha$ at an independent type $V_i$

- $S_{\text{nfold}}(\mathbf{x}) = \sum_{\alpha=1}^{|G|} \left( (\sum_{\text{clique } i \in T(G)} \alpha x_i^\alpha) + (\sum_{\text{indep. } i \in T(G)} \alpha |V_i| x_i^\alpha) \right) = \text{total cost of } \mathbf{x}$

**Objective & Constraints:**

$$ \min S_{\text{nfold}}(\mathbf{x}) \qquad (\text{sc:nf:obj}) $$

$$ \sum_{\alpha=1}^{|G|} x_i^\alpha = |V_i| \quad \forall i \in T(G), V_i \text{ is clique} \quad V_i \text{ is colored} \quad (\text{sc:nf:cliques}) $$

$$ \sum_{\alpha=1}^{|G|} x_i^\alpha = 1 \quad \forall i \in T(G), V_i \text{ is independent} \quad V_i \text{ is colored} \quad (\text{sc:nf:indeps}) $$

$$ x_i^\alpha + x_j^\alpha \le 1 \quad \forall \alpha \in [[G]] \quad \forall ij \in E(T(G)) \quad x^\alpha \text{ is independent set} \quad (\text{sc:nf:xi-indep}) $$

**Parameters & Notes:**

$$ \begin{array}{llllllllllll} \#\text{vars} & \#\text{constraints} & \|A\|_{\infty} & \|\mathbf{b}\|_{\infty} & \|\mathbf{l}, \mathbf{u}\|_{\infty} & \|\mathbf{w}\|_{\infty} & r & s & t \\ k|G| & k + k^2|G| & 1 & |G| & 1 & |G| & k & k^2 & k \end{array} $$

- Constraints have an n-fold format: (sc:nf:cliques) and (sc:nf:indeps) form the $(A_1 \cdots A_1)$ block and (sc:nf:xi-indep) form the $A_2$ blocks; see parameters $r, s, t$ above.

Applying the algorithm of Altmanová et al. [1] to Model 11 yields Theorem 2a. Model 11 is a typical use case of n-fold IP: we have a vector of multiplicities $\mathbf{b}$ (modeling $(|V_1|, \dots, |V_k|)$) and we optimize over its decompositions into independent sets of $T(G)$. A clever objective function models the objective of SUM COLORING.
# 5 Convex Objective: Sum Coloring

SUM COLORING

**Input:** A graph $G = (V, E)$.

**Task:** A proper coloring $c: V \to \mathbb{N}$ minimizing $\sum_{v \in V} c(v)$.

In the following we first give a single-exponential algorithm for SUM COLORING with a polynomial dependence on $|G|$, then a double-exponential algorithm with a logarithmic dependence on $|G|$, and finally show how to combine the two ideas together to obtain a single-exponential algorithm with a logarithmic dependence on $|G|$.

## 5.1 Sum Coloring via n-fold IP

**Structure of Solution.** The following observation was made by Lampis [44] for the COLORING problem, and it holds also for the SUM COLORING problem: every color $C \subseteq V(G)$ intersects each clique type in at most one vertex, and each independent type in either none or all of its vertices. The first follows simply by the fact that it is a clique; the second by the fact that if both colors $\alpha, \beta$ with $\alpha < \beta$ are used for an independent type, then recoloring all vertices of color $\beta$ to be of color $\alpha$ remains a valid coloring and decreases its cost. We call a coloring with this structure an *essential coloring*.

**► Model 11 (SUM COLORING as n-fold IP).**

**Variables & Notation:**

- $x_i^\alpha = 1$ if color $\alpha$ intersects $V_i$

- $\alpha \cdot x_i^\alpha$ = cost of color $\alpha$ at a clique type $i$

- $\alpha|V_i| \cdot x_i^\alpha$ = cost of color $\alpha$ at an independent type $V_i$

- $S_{\text{nfold}}(\mathbf{x}) = \sum_{\alpha=1}^{|G|} \left( (\sum_{\text{clique } i \in T(G)} \alpha x_i^\alpha) + (\sum_{\text{indep. } i \in T(G)} \alpha |V_i| x_i^\alpha) \right) = \text{total cost of } \mathbf{x}$

**Objective & Constraints:**

$$ \min S_{\text{nfold}}(\mathbf{x}) \qquad (\text{sc:nf:obj}) $$

$$ \sum_{\alpha=1}^{|G|} x_i^\alpha = |V_i| \quad \forall i \in T(G), V_i \text{ is clique} \quad V_i \text{ is colored} \quad (\text{sc:nf:cliques}) $$

$$ \sum_{\alpha=1}^{|G|} x_i^\alpha = 1 \quad \forall i \in T(G), V_i \text{ is independent} \quad V_i \text{ is colored} \quad (\text{sc:nf:indeps}) $$

$$ x_i^\alpha + x_j^\alpha \le 1 \quad \forall \alpha \in [[G]] \quad \forall ij \in E(T(G)) \quad x^\alpha \text{ is independent set} \quad (\text{sc:nf:xi-indep}) $$

**Parameters & Notes:**

$$ \begin{array}{llllllllll} \#\text{vars} & \#\text{constraints} & \|A\|_{\infty} & \|\mathbf{b}\|_{\infty} & \|\mathbf{l}, \mathbf{u}\|_{\infty} & \|\mathbf{w}\|_{\infty} & r & s & t \\ k|G| & k + k^2|G| & 1 & |G| & 1 & |G| & k & k^2 & k \end{array} $$

- Constraints have an n-fold format: (sc:nf:cliques) and (sc:nf:indeps) form the $(A_1 \cdots A_1)$ block and (sc:nf:xi-indep) form the $A_2$ blocks; see parameters $r, s, t$ above.

Applying the algorithm of Altmanová et al. [1] to Model 11 yields Theorem 2a. Model 11 is a typical use case of n-fold IP: we have a vector of multiplicities $\mathbf{b}$ (modeling $(|V_1|, \dots, |V_k|)$) and we optimize over its decompositions into independent sets of $T(G)$. A clever objective function models the objective of SUM COLORING.
<figure><img src="image_110.png" /><figcaption>■ **Figure 1** An illustration of the cost decomposition to the individual classes. Note that *i*-th row (color *i*) has cost *i* per vertex.</figcaption></figure>

## 5.2 Sum Coloring via Convex Minimization in Fixed Dimension

**Structure of Solution.** The previous observations also allow us to encode a solution in a different way. Let $\mathcal{I} = \{I_1, \dots, I_K\}$ be the set of all independent sets of $T(G)$; note that $K < 2^k$. Then we can encode an essential coloring of $G$ by a vector of multiplicities $\mathbf{x} = (x_{I_1}, \dots, x_{I_K})$ of elements of $\mathcal{I}$ such that there are $x_{I_j}$ colors which color exactly the types contained in $I_j$. The difficulty with SUM COLORING lies in the formulation of its objective function. Observe that given an $I \in \mathcal{I}$, the number of vertices every color class of this type will contain is independent of the actual multiplicity $x_I$. Define the size of a color class $\sigma: \mathcal{I} \to \mathbb{N}$ as $\sigma(I) = \sum_{\text{clique } i \in I} 1 + \sum_{\text{indep. } i \in I} |V_i|$.

► **Lemma 12** (⋆). Let $G = (V, E)$ be a graph and let $c: V \to \mathbb{N}$ be a proper coloring of $G$ minimizing $\sum_{v \in V} c(v)$. Let $\mu(p)$ denote the quantity $|\{v \in V \mid c(v) = p\}|$. Then $\mu(p) \ge \mu(q)$ for every $p \le q$.

Our goal now is to show that the objective function can be expressed as a convex function in terms of the variables $\mathbf{x}$. We will get help from auxiliary variables $y_1, \dots, y_{|G|}$ which are a linear projection of variables $\mathbf{x}$; note that we do not actually introduce these variables into the model and only use them for the sake of proving convexity. Namely, $y_j$ indicates how many color classes contain at least $j$ vertices: $y_j = \sum_{\sigma(I) \ge j} x_I$. Then, the objective function can be expressed as $S_{\text{convex}}(\mathbf{x}) = \sum_{i=1}^p |i\sigma(I_i)| = \sum_{j=1}^{|G|} \binom{y_j}{2}$, where $i = 1, \dots, p$ is the order of the color classes given by Lemma 12, every class of type $I$ is present $x_I$ times, where we enumerate only those $I$ with $x_I \ge 1$. The equivalence of the two is straightforward to check.

Finally, $S_{\text{convex}}$ is convex with respect to $\mathbf{x}$ because,

1) all $x_I$ are linear (thus affine) functions,

2) $y_i = \sum_{I: \sigma(I) \ge i} x_I$ is a sum of affine functions, thus affine,

3) $y_i(y_i - 1)/2$ is convex: it is a basic fact that $h(x) = g(f(x))$ is convex if $f$ is affine and $g$ is convex. Here $f = y_i$ is affine by the previous point and $g = f(f - 1)/2$ is convex.

4) $S_{\text{convex}}$ is the sum of $y_i(y_i - 1)/2$, which are convex by the previous point.
<figure><img src="image_112.png" /><figcaption>■ **Figure 1** An illustration of the cost decomposition to the individual classes. Note that *i*-th row (color *i*) has cost *i* per vertex.</figcaption></figure>

## 5.2 Sum Coloring via Convex Minimization in Fixed Dimension

**Structure of Solution.** The previous observations also allow us to encode a solution in a different way. Let $\mathcal{I} = \{I_1, \dots, I_K\}$ be the set of all independent sets of $T(G)$; note that $K < 2^k$. Then we can encode an essential coloring of $G$ by a vector of multiplicities $\mathbf{x} = (x_{I_1}, \dots, x_{I_K})$ of elements of $\mathcal{I}$ such that there are $x_{I_j}$ colors which color exactly the types contained in $I_j$. The difficulty with SUM COLORING lies in the formulation of its objective function. Observe that given an $I \in \mathcal{I}$, the number of vertices every color class of this type will contain is independent of the actual multiplicity $x_I$. Define the size of a color class $\sigma: \mathcal{I} \to \mathbb{N}$ as $\sigma(I) = \sum_{\text{clique } i \in I} 1 + \sum_{\text{indep. } i \in I} |V_i|$.

► **Lemma 12** (⋆). Let $G = (V, E)$ be a graph and let $c: V \to \mathbb{N}$ be a proper coloring of $G$ minimizing $\sum_{v \in V} c(v)$. Let $\mu(p)$ denote the quantity $|\{v \in V \mid c(v) = p\}|$. Then $\mu(p) \ge \mu(q)$ for every $p \le q$.

Our goal now is to show that the objective function can be expressed as a convex function in terms of the variables $\mathbf{x}$. We will get help from auxiliary variables $y_1, \dots, y_{|G|}$ which are a linear projection of variables $\mathbf{x}$; note that we do not actually introduce these variables into the model and only use them for the sake of proving convexity. Namely, $y_j$ indicates how many color classes contain at least $j$ vertices: $y_j = \sum_{\sigma(I) \ge j} x_I$. Then, the objective function can be expressed as $S_{\text{convex}}(\mathbf{x}) = \sum_{i=1}^p |i\sigma(I_i)| = \sum_{j=1}^{|G|} \binom{y_j}{2}$, where $i = 1, \dots, p$ is the order of the color classes given by Lemma 12, every class of type $I$ is present $x_I$ times, where we enumerate only those $I$ with $x_I \ge 1$. The equivalence of the two is straightforward to check.

Finally, $S_{\text{convex}}$ is convex with respect to $\mathbf{x}$ because,

1) all $x_I$ are linear (thus affine) functions,

2) $y_i = \sum_{I: \sigma(I) \ge i} x_I$ is a sum of affine functions, thus affine,

3) $y_i(y_i - 1)/2$ is convex: it is a basic fact that $h(x) = g(f(x))$ is convex if $f$ is affine and $g$ is convex. Here $f = y_i$ is affine by the previous point and $g = f(f - 1)/2$ is convex.

4) $S_{\text{convex}}$ is the sum of $y_i(y_i - 1)/2$, which are convex by the previous point.
► Model 13 (SUM COLORING as LINIP in fixed dimension with convex objective).

Variables & Notation:

■ $x_I$ = #of color class I

■ $y_i$ = #of color classes I with $\sigma(I) \le i$

■ $\binom{y_i}{2}$ cost of column $y_i$ (Figure 1)

■ $S_{\text{convex}} = \sum_{i=1}^{|G|} \binom{y_i}{2}$ = cost of all columns

Objective & Constraints:

$$ \min S_{\text{convex}}(\mathbf{x}) \qquad (\text{sc:convex:obj}) $$

$$ \sum_{I_j: i \in I_j} x_{I_j} = |V_i| \quad \forall \text{clique } i \in T(G) \quad \text{clique } V_i \text{ gets } |V_i| \text{ colors} \quad (\text{sc:convex:cliques}) $$

$$ \sum_{I_j: i \in I_j} x_{I_j} = 1 \quad \forall \text{indep. } i \in T(G) \quad \text{indep. } V_i \text{ gets 1 color} \quad (\text{sc:convex:indeps}) $$

Parameters & Notes:

$$ \begin{array}{llllll} \#\text{vars} & \#\text{constraints} & \|A\|_{\infty} & \|\mathbf{b}\|_{\infty} & \|\mathbf{l}, \mathbf{u}\|_{\infty} & f_{\max} \\ 2^k & k & 1 & |G| & |G| & |G|^2 \end{array} $$

■ Objective $S_{\text{convex}}$ is non-separable convex, and can be computed in time $2^k \log |G|$ by noticing that there are at most $2^k$ different $y_i$'s (see below).

Applying the algorithm of Dadush [11] to Model 13 yields Theorem 2b. Notice that we could not apply Lokshtanov's algorithm because the objective has large coefficients. Also notice that we do not need separability of $S_{\text{convex}}$ or any structure of $A$.

5.3 Sum Coloring and Graver Bases

Consider Model 13. The fact that the number of rows and the largest coefficient $\|A\|_{\infty}$ is small, and that we can formulate $S_{\text{convex}}$ as a separable convex objective in terms of the $y_i$ variables gives us some hope that Graver basis techniques would be applicable.

Since $|\mathcal{I}| \le 2^k$, we can replace the $y_i$'s by a smaller set of variables $z_i$ for a set of “critical sizes” $\Gamma = \{i \in [|G|] \mid \exists I \in \mathcal{I} : \sigma(I) = i\}$. For each $i \in \Gamma$ let $\text{succ}(i) = \min\{j \in \Gamma \mid j > i\}$ (and let $\text{succ}(\max \Gamma) = \max \Gamma$), define $z_i = \sum_{I \in \mathcal{I}: \sigma(I) \ge i} x_I$, and let $\zeta_i = (\text{succ}(i) - i)$ be the size difference between a color class of size $i$ and the smallest larger color class. Then,

$$ S_{\text{convex}}(\mathbf{x}) = \sum_{i=1}^{|G|} \binom{y_i}{2} = \sum_{i \in \Gamma} \zeta_i \binom{z_i}{2} = S_{\text{sepconvex}}(\mathbf{z}) . $$

Now we want to construct a system of inequalities of bounded dual treewidth $\text{tw}_D(A)$; however, adding the $z_i$ variables as we have defined them amounts to adding many inequalities containing the $z_1$ variable, thus increasing the dual treewidth to $k + 2^k$. To avoid this, let us define $z_i$ equivalently as $z_i = z_{\text{succ}(i)} + \sum_{\text{succ}(i)>\sigma(I)\ge i} x_I = z_{\text{succ}(i)} + \sum_{\sigma(I)=i} x_I$.

► Model 14 (SUM COLORING as LINIP with small $\text{tw}_D(A)$ and small $g_1(A)$).

Variables & Notation:

■ $x_I$ = #of color class I

■ $z_i$ = #of color classes I with $\sigma(I) \ge i$

■ $\zeta_i$ = size difference between $I \in \mathcal{I}$ with $\sigma(I) = i$ and closest larger $J \in \mathcal{I}$

■ $\zeta_i(\binom{z_i}{2})$ cost of all columns between $y_i$ and $y_{\text{succ}(i)}$ (Figure 1)
► Model 13 (SUM COLORING as LINIP in fixed dimension with convex objective).

**Variables & Notation:**

- $x_I$ = #of color class I

- $y_i$ = #of color classes I with $\sigma(I) \le i$

- $\binom{y_i}{2}$ cost of column $y_i$ (Figure 1)

- $S_{\text{convex}} = \sum_{i=1}^{|G|} \binom{y_i}{2}$ = cost of all columns

**Objective & Constraints:**

$$ \min S_{\text{convex}}(\mathbf{x}) \qquad (\text{sc:convex:obj}) $$

$$ \sum_{I_j: i \in I_j} x_{I_j} = |V_i| \quad \forall \text{clique } i \in T(G) \quad \text{clique } V_i \text{ gets } |V_i| \text{ colors} \quad (\text{sc:convex:cliques}) $$

$$ \sum_{I_j: i \in I_j} x_{I_j} = 1 \quad \forall \text{indep. } i \in T(G) \quad \text{indep. } V_i \text{ gets 1 color} \quad (\text{sc:convex:indeps}) $$

**Parameters & Notes:**

$$ \begin{array}{llllll} \#\text{vars} & \#\text{constraints} & \|A\|_{\infty} & \|\mathbf{b}\|_{\infty} & \|\mathbf{l}, \mathbf{u}\|_{\infty} & f_{\max} \\ 2^k & k & 1 & |G| & |G| & |G|^2 \end{array} $$

- Objective $S_{\text{convex}}$ is non-separable convex, and can be computed in time $2^k \log |G|$ by noticing that there are at most $2^k$ different $y_i$'s (see below).

Applying the algorithm of Dadush [11] to Model 13 yields Theorem 2b. Notice that we could not apply Lokshtanov's algorithm because the objective has large coefficients. Also notice that we do not need separability of $S_{\text{convex}}$ or any structure of A.

## 5.3 Sum Coloring and Graver Bases

Consider Model 13. The fact that the number of rows and the largest coefficient $\|A\|_{\infty}$ is small, and that we can formulate $S_{\text{convex}}$ as a separable convex objective in terms of the $y_i$ variables gives us some hope that Graver basis techniques would be applicable.

Since $|\mathcal{I}| \le 2^k$, we can replace the $y_i$'s by a smaller set of variables $z_i$ for a set of “critical sizes” $\Gamma = \{i \in [|G|] \mid \exists I \in \mathcal{I}: \sigma(I) = i\}$. For each $i \in \Gamma$ let $\text{succ}(i) = \min\{j \in \Gamma \mid j > i\}$ (and let $\text{succ}(\max \Gamma) = \max \Gamma$), define $z_i = \sum_{I \in \mathcal{I}: \sigma(I) \ge i} x_I$, and let $\zeta_i = (\text{succ}(i) - i)$ be the size difference between a color class of size $i$ and the smallest larger color class. Then,

$$ S_{\text{convex}}(\mathbf{x}) = \sum_{i=1}^{|G|} \binom{y_i}{2} = \sum_{i \in \Gamma} \zeta_i \binom{z_i}{2} = S_{\text{sepconvex}}(\mathbf{z}) . $$

Now we want to construct a system of inequalities of bounded dual treewidth $\text{tw}_D(A)$; however, adding the $z_i$ variables as we have defined them amounts to adding many inequalities containing the $z_1$ variable, thus increasing the dual treewidth to $k + 2^k$. To avoid this, let us define $z_i$ equivalently as $z_i = z_{\text{succ}(i)} + \sum_{\text{succ}(i) > \sigma(I) \ge i} x_I = z_{\text{succ}(i)} + \sum_{\sigma(I)=i} x_I$.

► Model 14 (SUM COLORING as LINIP with small $\text{tw}_D(A)$ and small $g_1(A)$).

**Variables & Notation:**

- $x_I$ = #of color class I

- $z_i$ = #of color classes I with $\sigma(I) \ge i$

- $\zeta_i$ = size difference between $I \in \mathcal{I}$ with $\sigma(I) = i$ and closest larger $J \in \mathcal{I}$

- $\zeta_i(\binom{z_i}{2})$ cost of all columns between $y_i$ and $y_{\text{succ}(i)}$ (Figure 1)
■ $\Gamma$ = set of critical sizes

■ $S_{\text{sepconvex}}(\mathbf{z}) = \sum_{i \in \Gamma} \zeta_i(z_i/2)$ = total cost

**Objective & Constraints:** constraints (sc:convex:cliques) and (sc:convex:indeps), and:

$$ \min S_{\text{sepconvex}}(\mathbf{z}) \qquad (\text{sc:graver:obj}) $$

$$ z_i = z_{\text{succ}(i)} + \sum_{I \in \mathcal{I}: \sigma(I)=i} x_I \quad \forall i \in \Gamma \qquad (\text{sc:graver:sep}) $$

**Parameters & Notes:**

$$ \begin{array}{llllllll} \#\text{vars} & \#\text{constraints} & \|A\|_{\infty} & \|\mathbf{b}\|_{\infty} & \|\mathbf{l}, \mathbf{u}\|_{\infty} & f_{\max} & g_1(A) & \text{tw}_D(A) \\ \mathcal{O}(2^k) & \mathcal{O}(2^k) & 1 & |G| & |G| & |G|^2 & \mathcal{O}(k^k) & k+2 \end{array} $$

■ Bounds on $g_1(A)$ and $\text{tw}_D(A)$ by Lemmas 16 and 15, respectively.

■ Objective $S_{\text{sepconvex}}$ is separable convex.

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

Applying the algorithm of Koutecký et al. [43] to Model 14 yields Theorem 2c.

Let us denote the matrix encoding the constraints (sc:convex:cliques) and (sc:convex:indeps) as $F \in \mathbb{Z}^{k \times 2 \cdot 2^k}$ (notice that we also add the empty columns for the $z_i$ variables), and the matrix encoding the constraints (sc:graver:sep) by $L \in \mathbb{Z}^{2^k \times 2^k}$; thus $A = (F/L)$.

► Lemma 15 (⋆). In Model 14 it holds that $\text{tw}_D(A) \le k+1$.

**Proof Idea.** $G_D(F)$ is a $k$-clique $K_k$, and $G_D(L)$ is a $2^k$-path $P_{2^k}$. Thus, $G_D(A)$ are these two graphs connected by all possible edges, and we construct a path decomposition, whose consecutive nodes contain $G_D(F)$ and consecutive vertices of $G_D(L)$. ◀

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

► Lemma 16 (⋆). In Model 14 it holds that $g_1(A) \le k^{O(k)}$.

**Proof Idea.** We first simplify the structure of $L$ by deleting duplicitous columns, and then explicitely construct a decomposition of any $\mathbf{h}$ s.t. $L\mathbf{h} = \mathbf{0}$ into conformal vectors $\mathbf{g}$ of small $\ell_1$-norm. Combining with known bounds on matrices with few rows ($F$) and stacked matrices ($A$) yields the bound. ◀

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

**References**

1. Kateřina Altmanová, Dušan Knop, and Martin Koutecký. Evaluating and Tuning n-fold Integer Programming. In Gianlorenzo D'Angelo, editor, *17th International Symposium on Experimental Algorithms, SEA 2018, June 27-29, 2018, L'Aquila, Italy*, volume 103 of LIPIcs, pages 10:1-10:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. doi:10.4230/LIPIcs.SEA.2018.10.

2. Sancrey Rodrigues Alves, Konrad Kazimierz Dabrowski, Luérbio Faria, Sulamita Klein, Ignasi Sau, and Uéverton dos Santos Souza. On the (Parameterized) Complexity of Recognizing Well-Covered (r, l)-graphs. In *10th International Conference on Combinatorial Optimization and Applications (COCOA'16)*, volume 10043 of Lecture Notes in Computer Science, pages 423-437, 2016. doi:10.1007/978-3-319-48749-6.

3. NR Aravind, Subrahmanyam Kalyanasundaram, Anjeneya Swami Kare, and Juho Lauri. Algorithms and hardness results for happy coloring problems. *arXiv preprint arXiv:1705.08282*, 2017.

4. Matthias Aschenbrenner and Raymond Hemmecke. Finiteness theorems in stochastic integer programming. *Foundations of Computational Mathematics*, 7(2):183-227, 2007.

5. Johannes Bisschop. *AIMMS Optimization Modeling*. Paragon Decision Technology BV, 2006.
■ $\Gamma$ = set of critical sizes

■ $S_{\text{sepconvex}}(\mathbf{z}) = \sum_{i \in \Gamma} \zeta_i(z_i/2)$ = total cost

**Objective & Constraints:** constraints (sc:convex:cliques) and (sc:convex:indeps), and:

$$ \min S_{\text{sepconvex}}(\mathbf{z}) \qquad (\text{sc:graver:obj}) $$

$$ z_i = z_{\text{succ}(i)} + \sum_{I \in \mathcal{I}: \sigma(I)=i} x_I \quad \forall i \in \Gamma \qquad (\text{sc:graver:sep}) $$

**Parameters & Notes:**

$$ \begin{array}{llllllll} \#\text{vars} & \#\text{constraints} & \|A\|_{\infty} & \|b\|_{\infty} & \|l, u\|_{\infty} & f_{\max} & g_1(A) & \text{tw}_D(A) \\ \mathcal{O}(2^k) & \mathcal{O}(2^k) & 1 & |G| & |G| & |G|^2 & \mathcal{O}(k^k) & k+2 \end{array} $$

■ Bounds on $g_1(A)$ and $\text{tw}_D(A)$ by Lemmas 16 and 15, respectively.

■ Objective $S_{\text{sepconvex}}$ is separable convex.

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

Applying the algorithm of Koutecký et al. [43] to Model 14 yields Theorem 2c.

Let us denote the matrix encoding the constraints (sc:convex:cliques) and (sc:convex:indeps) as $F \in \mathbb{Z}^{k \times 2 \cdot 2^k}$ (notice that we also add the empty columns for the $z_i$ variables), and the matrix encoding the constraints (sc:graver:sep) by $L \in \mathbb{Z}^{2^k \times 2^k}$; thus $A = (F/L)$.

► Lemma 15 (⋆). In Model 14 it holds that $\text{tw}_D(A) \le k+1$.

**Proof Idea.** $G_D(F)$ is a $k$-clique $K_k$, and $G_D(L)$ is a $2^k$-path $P_{2^k}$. Thus, $G_D(A)$ are these two graphs connected by all possible edges, and we construct a path decomposition, whose consecutive nodes contain $G_D(F)$ and consecutive vertices of $G_D(L)$. ◀

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

► Lemma 16 (⋆). In Model 14 it holds that $g_1(A) \le k^{O(k)}$.

**Proof Idea.** We first simplify the structure of $L$ by deleting duplicitous columns, and then explicitely construct a decomposition of any $\mathbf{h}$ s.t. $L\mathbf{h} = \mathbf{0}$ into conformal vectors $\mathbf{g}$ of small $l_1$-norm. Combining with known bounds on matrices with few rows ($F$) and stacked matrices ($A$) yields the bound. ◀

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

References

1. Kateřina Altmanová, Dušan Knop, and Martin Koutecký. Evaluating and Tuning n-fold Integer Programming. In Gianlorenzo D'Angelo, editor, 17th International Symposium on Experimental Algorithms, SEA 2018, June 27-29, 2018, L'Aquila, Italy, volume 103 of LIPIcs, pages 10:1-10:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. doi:10.4230/LIPIcs.SEA.2018.10.

2. Sancrey Rodrigues Alves, Konrad Kazimierz Dabrowski, Luérbio Faria, Sulamita Klein, Ignasi Sau, and Uéverton dos Santos Souza. On the (Parameterized) Complexity of Recognizing Well-Covered (r, l)-graphs. In 10th International Conference on Combinatorial Optimization and Applications (COCOA'16), volume 10043 of Lecture Notes in Computer Science, pages 423-437, 2016. doi:10.1007/978-3-319-48749-6.

3. NR Aravind, Subrahmanyam Kalyanasundaram, Anjeneya Swami Kare, and Juho Lauri. Algorithms and hardness results for happy coloring problems. arXiv preprint arXiv:1705.08282, 2017.

4. Matthias Aschenbrenner and Raymond Hemmecke. Finiteness theorems in stochastic integer programming. Foundations of Computational Mathematics, 7(2):183-227, 2007.

5. Johannes Bisschop. AIMMS Optimization Modeling. Paragon Decision Technology BV, 2006.
21:14 Integer Programming in Parameterized Complexity: Three Miniatures

6 Édouard Bonnet and Florian Sikora. The Graph Motif problem parameterized by the structure of the input graph. *Discrete Applied Mathematics*, 2016.

7 Robert Bredereck, Jiehua Chen, Piotr Faliszewski, Jiong Guo, Rolf Niedermeier, and Gerhard J Woeginger. Parameterized algorithmics for computational social choice: Nine research challenges. *Tsinghua Science and Technology*, 19(4):358–373, 2014.

8 Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, Piotr Skowron, and Nimrod Talmon. Elections with Few Candidates: Prices, Weights, and Covering Problems. In *Proc. ADT 2015*, volume 9346 of *Lecture Notes Comput. Sci.*, pages 414–431, 2015.

9 Lin Chen and Daniel Marx. Covering a tree with rooted subtrees–parameterized and approximation algorithms. In *Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018*, pages 2801–2820. SIAM, 2018.

10 Jason Crampton, Gregory Gutin, Martin Koutecký, and Rémi Watrigant. Parameterized resiliency problems via integer linear programming. In *Proc. CIAC 2017*, volume 10236 of *Lecture Notes Comput. Sci.*, pages 164–176, 2017.

11 Daniel Dadush, Chris Peikert, and Santosh Vempala. Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings. In Rafail Ostrovsky, editor, *FOCS*, page 580–589. IEEE, 2011. doi:10.1109/FOCS.2011.31.

12 Daniel Dadush and Santosh S Vempala. Near-optimal deterministic algorithms for volume computation via M-ellipsoids. *Proceedings of the National Academy of Sciences*, 110(48):19237–19245, 2013.

13 Michael Dom, Daniel Lokshtanov, Saket Saurabh, and Yngve Villanger. Capacitated domination and covering: A parameterized perspective. In *International Workshop on Parameterized and Exact Computation*, pages 78–90. Springer, 2008.

14 Rodney G. Downey and Michael R. Fellows. *Fundamentals of Parameterized Complexity*. Texts in Computer Science. Springer, 2013. doi:10.1007/978-1-4471-5559-1.

15 Friedrich Eisenbrand, Christoph Hunkenschröder, and Kim-Manuel Klein. Faster Algorithms for Integer Programs with Block Structure. In Ioannis Chatziogiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, *45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic*, volume 107 of *LIPIcs*, pages 49:1–49:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. doi:10.4230/LIPIcs.ICALP.2018.49.

16 Friedrich Eisenbrand and Gennady Shmonin. Parametric integer programming in fixed dimension. *Math. Oper. Res.*, 33(4), 2008.

17 Friedrich Eisenbrand and Robert Weismantel. Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma. In *Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms*, pages 808–816. SIAM, 2018.

18 Piotr Faliszewski, Rica Gonen, Martin Koutecký, and Nimrod Talmon. Opinion diffusion and campaigning on society graphs. In *Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18*, pages 219–225. International Joint Conferences on Artificial Intelligence Organization, 7 2018. doi:10.24963/ijcai.2018/30.

19 Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Frances A. Rosamond, and Saket Saurabh. Graph Layout Problems Parameterized by Vertex Cover. In Seok-Hee Hong, Hiroshi Nagamochi, and Takuro Fukunaga, editors, *ISAAC*, volume 5369 of *Lecture Notes in Computer Science*, page 294–305. Springer, 2008. doi:10.1007/978-3-540-92182-0.

20 Jiří Fiala, Tomáš Gavenčiak, Dušan Knop, Martin Koutecký, and Jan Kratochvíl. Parameterized complexity of distance labeling and uniform channel assignment problems. *Discrete Applied Mathematics*, 2017.

21 Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width. *SIAM J. Comput.*, 43(5):1541–1563, 2014. doi:10.1137/130910932.
6 Édouard Bonnet and Florian Sikora. The Graph Motif problem parameterized by the structure of the input graph. *Discrete Applied Mathematics*, 2016.

7 Robert Bredereck, Jiehua Chen, Piotr Faliszewski, Jiong Guo, Rolf Niedermeier, and Gerhard J Woeginger. Parameterized algorithmics for computational social choice: Nine research challenges. *Tsinghua Science and Technology*, 19(4):358–373, 2014.

8 Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, Piotr Skowron, and Nimrod Talmon. Elections with Few Candidates: Prices, Weights, and Covering Problems. In *Proc. ADT 2015*, volume 9346 of *Lecture Notes Comput. Sci.*, pages 414–431, 2015.

9 Lin Chen and Daniel Marx. Covering a tree with rooted subtrees–parameterized and approximation algorithms. In *Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018*, pages 2801–2820. SIAM, 2018.

10 Jason Crampton, Gregory Gutin, Martin Koutecký, and Rémi Watrigant. Parameterized resiliency problems via integer linear programming. In *Proc. CIAC 2017*, volume 10236 of *Lecture Notes Comput. Sci.*, pages 164–176, 2017.

11 Daniel Dadush, Chris Peikert, and Santosh Vempala. Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings. In Rafail Ostrovsky, editor, *FOCS*, page 580–589. IEEE, 2011. doi:10.1109/FOCS.2011.31.

12 Daniel Dadush and Santosh S Vempala. Near-optimal deterministic algorithms for volume computation via M-ellipsoids. *Proceedings of the National Academy of Sciences*, 110(48):19237–19245, 2013.

13 Michael Dom, Daniel Lokshtanov, Saket Saurabh, and Yngve Villanger. Capacitated domination and covering: A parameterized perspective. In *International Workshop on Parameterized and Exact Computation*, pages 78–90. Springer, 2008.

14 Rodney G. Downey and Michael R. Fellows. *Fundamentals of Parameterized Complexity*. Texts in Computer Science. Springer, 2013. doi:10.1007/978-1-4471-5559-1.

15 Friedrich Eisenbrand, Christoph Hunkenschröder, and Kim-Manuel Klein. Faster Algorithms for Integer Programs with Block Structure. In Ioannis Chatziogiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, *45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic*, volume 107 of *LIPIcs*, pages 49:1–49:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. doi:10.4230/LIPIcs.ICALP.2018.49.

16 Friedrich Eisenbrand and Gennady Shmonin. Parametric integer programming in fixed dimension. *Math. Oper. Res.*, 33(4), 2008.

17 Friedrich Eisenbrand and Robert Weismantel. Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma. In *Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms*, pages 808–816. SIAM, 2018.

18 Piotr Faliszewski, Rica Gonen, Martin Koutecký, and Nimrod Talmon. Opinion diffusion and campaigning on society graphs. In *Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18*, pages 219–225. International Joint Conferences on Artificial Intelligence Organization, 7 2018. doi:10.24963/ijcai.2018/30.

19 Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Frances A. Rosamond, and Saket Saurabh. Graph Layout Problems Parameterized by Vertex Cover. In Seok-Hee Hong, Hiroshi Nagamochi, and Takuro Fukunaga, editors, *ISAAC*, volume 5369 of *Lecture Notes in Computer Science*, page 294–305. Springer, 2008. doi:10.1007/978-3-540-92182-0.

20 Jiří Fiala, Tomáš Gavenčiak, Dušan Knop, Martin Koutecký, and Jan Kratochvíl. Parameterized complexity of distance labeling and uniform channel assignment problems. *Discrete Applied Mathematics*, 2017.

21 Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width. *SIAM J. Comput.*, 43(5):1541–1563, 2014. doi:10.1137/130910932.
22 András Frank and Eva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. *Combinatorica*, 7(1):49–65, 1987. doi:10.1007/BF02579200.

23 Jakub Gajarský, Petr Hliněný, Martin Koutecký, and Shmuel Onn. Parameterized shifted combinatorial optimization. In *International Computing and Combinatorics Conference*, pages 224–236. Springer, 2017.

24 Robert Ganian. Using neighborhood diversity to solve hard problems. *arXiv preprint arXiv:1201.3091*, 2012.

25 Luisa Gargano and Adele A. Rescigno. Complexity of conflict-free colorings of graphs. *Theoretical Computer Science*, 566(??):39–49, February 2015. URL: http://www.sciencedirect.com/science/article/pii/S0304397514009463.

26 Martin Grötschel, László Lovász, and Alexander Schrijver. *Geometric algorithms and combinatorial optimization*, volume 2. Springer Science & Business Media, 2012.

27 Sebastian Heinz. Complexity of integer quasiconvex polynomial optimization. *J. Complexity*, 21(4):543–556, 2005. doi:10.1016/j.jco.2005.04.004.

28 Raymond Hemmecke, Shmuel Onn, and Lyubov Romanchuk. n-Fold integer programming in cubic time. *Math. Program*, 137(1-2):325–341, 2013. doi:10.1007/s10107-011-0490-y.

29 Raymond Hemmecke and Rüdiger Schultz. Decomposition methods for two-stage stochastic integer programs. In *Online optimization of large scale systems*, pages 601–622. Springer, 2001.

30 Danny Hermelin, Judith-Madeleine Kubitza, Dvir Shabtay, Nimrod Talmon, and Gerhard Woeginger. Scheduling two competing agents when one agent has significantly fewer jobs. In *LIPIcs-Leibniz International Proceedings in Informatics*, volume 43. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015.

31 Robert Hildebrand and Matthias Köppe. A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity $2^{O(nlogn)}$. *Discrete Optimization*, 10(1):69–84, 2013. doi:10.1016/j.disopt.2012.11.003.

32 Klaus Jansen. Complexity results for the optimum cost chromatic partition problem. *Manuscript*, 1997.

33 Klaus Jansen, Kim-Manuel Klein, Marten Maack, and Malin Rau. Empowering the Configuration-IP – New PTAS Results for Scheduling with Setups Times. *arXiv preprint arXiv:1801.06460*, 2018.

34 Klaus Jansen and Lars Rohwedder. On Integer Programming and Convolution. *arXiv preprint arXiv:1803.04744*, 2018.

35 Klaus Jansen and Roberto Solis-Oba. An OPT+1 Algorithm for the Cutting Stock Problem with Constant Number of Object Lengths. In *IPCO*, pages 438–449. Springer, 2010.

36 Ravi Kannan. Minkowski's convex body theorem and integer programming. *Math. Oper. Res.*, 12(3):415–440, August 1987.

37 Leonid Khachiyan and Lorant Porkolab. Integer Optimization on Convex Semialgebraic Sets. *Discrete & Computational Geometry*, 23(2):207–224, 2000. doi:10.1007/PL00009496.

38 Dušan Knop and Martin Koutecký. Scheduling meets n-fold Integer Programming. *Journal of Scheduling*, November 2017. doi:10.1007/s10951-017-0550-0.

39 Dušan Knop, Martin Koutecký, and Matthias Mnich. Combinatorial n-fold Integer Programming and Applications. In Kirk Pruhs and Christian Sohler, editors, *25th Annual European Symposium on Algorithms (ESA 2017)*, volume 87 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 54:1–54:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.esa.2017.54.

40 Dušan Knop, Martin Koutecký, and Matthias Mnich. Voting and Bribing in Single-Exponential Time. In Heribert Vollmer and Brigitte Vallée, editors, *34th Symposium on*
22 András Frank and Eva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. *Combinatorica*, 7(1):49–65, 1987. doi:10.1007/BF02579200.

23 Jakub Gajarský, Petr Hliněný, Martin Koutecký, and Shmuel Onn. Parameterized shifted combinatorial optimization. In *International Computing and Combinatorics Conference*, pages 224–236. Springer, 2017.

24 Robert Ganian. Using neighborhood diversity to solve hard problems. *arXiv preprint arXiv:1201.3091*, 2012.

25 Luisa Gargano and Adele A. Rescigno. Complexity of conflict-free colorings of graphs. *Theoretical Computer Science*, 566(??):39–49, February 2015. URL: http://www.sciencedirect.com/science/article/pii/S0304397514009463.

26 Martin Grötschel, László Lovász, and Alexander Schrijver. *Geometric algorithms and combinatorial optimization*, volume 2. Springer Science & Business Media, 2012.

27 Sebastian Heinz. Complexity of integer quasiconvex polynomial optimization. *J. Complexity*, 21(4):543–556, 2005. doi:10.1016/j.jco.2005.04.004.

28 Raymond Hemmecke, Shmuel Onn, and Lyubov Romanchuk. n-Fold integer programming in cubic time. *Math. Program*, 137(1-2):325–341, 2013. doi:10.1007/s10107-011-0490-y.

29 Raymond Hemmecke and Rüdiger Schultz. Decomposition methods for two-stage stochastic integer programs. In *Online optimization of large scale systems*, pages 601–622. Springer, 2001.

30 Danny Hermelin, Judith-Madeleine Kubitza, Dvir Shabtay, Nimrod Talmon, and Gerhard Woeginger. Scheduling two competing agents when one agent has significantly fewer jobs. In *LIPIcs-Leibniz International Proceedings in Informatics*, volume 43. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015.

31 Robert Hildebrand and Matthias Köppe. A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity $2^{O(nlogn)}$. *Discrete Optimization*, 10(1):69–84, 2013. doi:10.1016/j.disopt.2012.11.003.

32 Klaus Jansen. Complexity results for the optimum cost chromatic partition problem. Manuscript, 1997.

33 Klaus Jansen, Kim-Manuel Klein, Marten Maack, and Malin Rau. Empowering the Configuration-IP – New PTAS Results for Scheduling with Setups Times. *arXiv preprint arXiv:1801.06460*, 2018.

34 Klaus Jansen and Lars Rohwedder. On Integer Programming and Convolution. *arXiv preprint arXiv:1803.04744*, 2018.

35 Klaus Jansen and Roberto Solis-Oba. An OPT+1 Algorithm for the Cutting Stock Problem with Constant Number of Object Lengths. In *IPCO*, pages 438–449. Springer, 2010.

36 Ravi Kannan. Minkowski's convex body theorem and integer programming. *Math. Oper. Res.*, 12(3):415–440, August 1987.

37 Leonid Khachiyan and Lorant Porkolab. Integer Optimization on Convex Semialgebraic Sets. *Discrete & Computational Geometry*, 23(2):207–224, 2000. doi:10.1007/PL00009496.

38 Dušan Knop and Martin Koutecký. Scheduling meets n-fold Integer Programming. *Journal of Scheduling*, November 2017. doi:10.1007/s10951-017-0550-0.

39 Dušan Knop, Martin Koutecký, and Matthias Mnich. Combinatorial n-fold Integer Programming and Applications. In Kirk Pruhs and Christian Sohler, editors, *25th Annual European Symposium on Algorithms (ESA 2017)*, volume 87 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 54:1–54:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.esa.2017.54.

40 Dušan Knop, Martin Koutecký, and Matthias Mnich. Voting and Bribing in Single-Exponential Time. In Heribert Vollmer and Brigitte Vallée, editors, *34th Symposium on IPEC 2018*
*Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany*, volume 66 of *LIPIcs*, pages 46:1–46:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.

41 Dušan Knop, Tomáš Masařík, and Tomáš Toufar. Parameterized Complexity of Fair Vertex Evaluation Problems. *CoRR*, abs/1803.06878, 2018. doi:1803.06878.

42 Dušan Knop, Martin Koutecký, and Matthias Mnich. A Unifying Framework for Manipulation Problems. In *Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018*, pages 256–264, 2018. URL: http://dl.acm.org/citation.cfm?id=3237427.

43 Martin Koutecký, Asaf Levin, and Shmuel Onn. A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, *45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic*, volume 107 of *LIPIcs*, pages 85:1–85:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. doi:10.4230/LIPIcs.ICALP.2018.85.

44 Michael Lampis. Algorithmic Meta-theorems for Restrictions of Treewidth. *Algorithmica*, 64(1):19–37, 2012.

45 Hendrik W. Lenstra, Jr. Integer programming with a fixed number of variables. *Mathematics of Operations Research*, 8(4):538–548, 1983.

46 Daniel Lokshtanov. *New Methods in Parameterized Algorithms and Complexity*. PhD thesis, University of Bergen, 2009.

47 Daniel Lokshtanov. Parameterized integer quadratic programming: Variables and coefficients. *arXiv preprint arXiv:1511.00310*, 2015.

48 Daniel Lokshtanov, MS Ramanujan, and Saket Saurabh. A linear time parameterized algorithm for directed feedback vertex set. *arXiv preprint arXiv:1609.04347*, 2016.

49 Dániel Marx. What’s next? Future directions in parameterized complexity. In *The Multivariate Algorithmic Revolution and Beyond*, pages 469–496. Springer, 2012.

50 Tomáš Masařík and Tomáš Toufar. Parameterized Complexity of Fair Deletion Problems. In *International Conference on Theory and Applications of Models of Computation (TAMC’16)*, pages 628–642, 2017.

51 Matthias Mnich and Andreas Wiese. Scheduling and fixed-parameter tractability. *Math. Program.*, 154(1-2, Ser. B):533–562, 2015.

52 Rolf Niedermeier. Ubiquitous Parameterization - Invitation to Fixed-Parameter Algorithms. In Jirí Fiala, Václav Koubek, and Jan Kratochvíl, editors, *MFCS*, volume 3153 of *Lecture Notes in Computer Science*, page 84–103. Springer, 2004. doi:10.1007/978-3-540-28629-5_4.

53 Timm Oertel, Christian Wagner, and Robert Weismantel. Integer convex minimization by mixed integer linear optimization. *Oper. Res. Lett*, 42(6-7):424–428, 2014. doi:10.1016/j.orl.2014.07.005.

54 Christos H Papadimitriou. On the complexity of integer programming. *Journal of the ACM (JACM)*, 28(4):765–768, 1981.

55 Kevin Zemmer. *Integer Polynomial Optimization in Fixed Dimension*. PhD thesis, ETH Zurich, 2017.
*Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany*, volume 66 of *LIPIcs*, pages 46:1–46:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.

41 Dušan Knop, Tomáš Masařík, and Tomáš Toufar. Parameterized Complexity of Fair Vertex Evaluation Problems. *CoRR*, abs/1803.06878, 2018. doi:1803.06878.

42 Dušan Knop, Martin Koutecký, and Matthias Mnich. A Unifying Framework for Manipulation Problems. In *Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018*, pages 256–264, 2018. URL: http://dl.acm.org/citation.cfm?id=3237427.

43 Martin Koutecký, Asaf Levin, and Shmuel Onn. A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, *45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic*, volume 107 of *LIPIcs*, pages 85:1–85:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. doi:10.4230/LIPIcs.ICALP.2018.85.

44 Michael Lampis. Algorithmic Meta-theorems for Restrictions of Treewidth. *Algorithmica*, 64(1):19–37, 2012.

45 Hendrik W. Lenstra, Jr. Integer programming with a fixed number of variables. *Mathematics of Operations Research*, 8(4):538–548, 1983.

46 Daniel Lokshtanov. *New Methods in Parameterized Algorithms and Complexity*. PhD thesis, University of Bergen, 2009.

47 Daniel Lokshtanov. Parameterized integer quadratic programming: Variables and coefficients. *arXiv preprint arXiv:1511.00310*, 2015.

48 Daniel Lokshtanov, MS Ramanujan, and Saket Saurabh. A linear time parameterized algorithm for directed feedback vertex set. *arXiv preprint arXiv:1609.04347*, 2016.

49 Dániel Marx. What’s next? Future directions in parameterized complexity. In *The Multivariate Algorithmic Revolution and Beyond*, pages 469–496. Springer, 2012.

50 Tomáš Masařík and Tomáš Toufar. Parameterized Complexity of Fair Deletion Problems. In *International Conference on Theory and Applications of Models of Computation (TAMC’16)*, pages 628–642, 2017.

51 Matthias Mnich and Andreas Wiese. Scheduling and fixed-parameter tractability. *Math. Program.*, 154(1-2, Ser. B):533–562, 2015.

52 Rolf Niedermeier. Ubiquitous Parameterization - Invitation to Fixed-Parameter Algorithms. In Jirí Fiala, Václav Koubek, and Jan Kratochvíl, editors, *MFCS*, volume 3153 of *Lecture Notes in Computer Science*, page 84–103. Springer, 2004. doi:10.1007/978-3-540-28629-5_4.

53 Timm Oertel, Christian Wagner, and Robert Weismantel. Integer convex minimization by mixed integer linear optimization. *Oper. Res. Lett*, 42(6-7):424–428, 2014. doi:10.1016/j.orl.2014.07.005.

54 Christos H Papadimitriou. On the complexity of integer programming. *Journal of the ACM (JACM)*, 28(4):765–768, 1981.

55 Kevin Zemmer. *Integer Polynomial Optimization in Fixed Dimension*. PhD thesis, ETH Zurich, 2017.
# Solving Target Set Selection with Bounded Thresholds Faster than $2^n$

## Ivan Bliznets

St. Petersburg Department of Steklov Institute of Mathematics of the Russian Academy of Sciences, St. Petersburg, Russia
iabliznets@gmail.com

https://orcid.org/0000-0003-2291-2556

## Danil Sagunov

St. Petersburg Department of Steklov Institute of Mathematics of the Russian Academy of Sciences, St. Petersburg, Russia
danilka.pro@gmail.com

https://orcid.org/0000-0003-3327-9768

## Abstract

In this paper we consider the TARGET SET SELECTION problem. The problem naturally arises in many fields like economy, sociology, medicine. In the TARGET SET SELECTION problem one is given a graph $G$ with a function thr: $V(G) \to N \cup \{0\}$ and integers $k, \ell$. The goal of the problem is to activate at most $k$ vertices initially so that at the end of the activation process there is at least $\ell$ activated vertices. The activation process occurs in the following way: (i) once activated, a vertex stays activated forever; (ii) vertex $v$ becomes activated if at least thr($v$) of its neighbours are activated. The problem and its different special cases were extensively studied from approximation and parameterized points of view. For example, parameterizations by the following parameters were studied: treewidth, feedback vertex set, diameter, size of target set, vertex cover, cluster editing number and others.

Despite the extensive study of the problem it is still unknown whether the problem can be solved in $O^*((2 - \epsilon)^n)$ time for some $\epsilon > 0$. We partially answer this question by presenting several faster-than-trivial algorithms that work in cases of constant thresholds, constant dual thresholds or when the threshold value of each vertex is bounded by one-third of its degree. Also, we show that the problem parameterized by $\ell$ is W[1]-hard even when all thresholds are constant.

**2012 ACM Subject Classification** Theory of computation → Graph algorithms analysis, Theory of computation → Parameterized complexity and exact algorithms, Theory of computation → Branch-and-bound

**Keywords and phrases** exact exponential algorithms, target set, vertex thresholds, social influence, irreversible conversions of graphs, bootstrap percolation

**Digital Object Identifier** 10.4230/LIPICs.IPEC.2018.22

**Related Version** Full version permanently available at https://arxiv.org/abs/1807.10789.

**Funding** This research was supported by the Russian Science Foundation (project 16-11-10123)

# 1 Introduction

In this paper we consider the TARGET SET SELECTION problem. In the problem one is given a graph $G$ with a function thr: $V(G) \to N \cup \{0\}$ (a threshold function), and two integers $k, \ell$. The question of the problem is to find a vertex subset $S \subseteq V(G)$ (a target set) such that $|S| \le k$ and if we initially activate $S$ then eventually at least $\ell$ vertices of $G$ become activated.

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

© Ivan Bliznets and Danil Sagunov;
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. 22; pp. 22:1–22:14

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

Leibniz International Proceedings in Informatics
LIPICS
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
# Solving Target Set Selection with Bounded Thresholds Faster than $2^n$

## Ivan Bliznets

St. Petersburg Department of Steklov Institute of Mathematics of the Russian Academy of Sciences, St. Petersburg, Russia
iabliznets@gmail.com

https://orcid.org/0000-0003-2291-2556

## Danil Sagunov

St. Petersburg Department of Steklov Institute of Mathematics of the Russian Academy of Sciences, St. Petersburg, Russia
danilka.pro@gmail.com

https://orcid.org/0000-0003-3327-9768

## Abstract

In this paper we consider the TARGET SET SELECTION problem. The problem naturally arises in many fields like economy, sociology, medicine. In the TARGET SET SELECTION problem one is given a graph $G$ with a function thr: $V(G) \to N \cup \{0\}$ and integers $k, \ell$. The goal of the problem is to activate at most $k$ vertices initially so that at the end of the activation process there is at least $\ell$ activated vertices. The activation process occurs in the following way: (i) once activated, a vertex stays activated forever; (ii) vertex $v$ becomes activated if at least thr($v$) of its neighbours are activated. The problem and its different special cases were extensively studied from approximation and parameterized points of view. For example, parameterizations by the following parameters were studied: treewidth, feedback vertex set, diameter, size of target set, vertex cover, cluster editing number and others.

Despite the extensive study of the problem it is still unknown whether the problem can be solved in $O^*((2 - \epsilon)^n)$ time for some $\epsilon > 0$. We partially answer this question by presenting several faster-than-trivial algorithms that work in cases of constant thresholds, constant dual thresholds or when the threshold value of each vertex is bounded by one-third of its degree. Also, we show that the problem parameterized by $\ell$ is W[1]-hard even when all thresholds are constant.

**2012 ACM Subject Classification** Theory of computation → Graph algorithms analysis, Theory of computation → Parameterized complexity and exact algorithms, Theory of computation → Branch-and-bound

**Keywords and phrases** exact exponential algorithms, target set, vertex thresholds, social influence, irreversible conversions of graphs, bootstrap percolation

**Digital Object Identifier** 10.4230/LIPICs.IPEC.2018.22

**Related Version** Full version permanently available at https://arxiv.org/abs/1807.10789.

**Funding** This research was supported by the Russian Science Foundation (project 16-11-10123)

## 1 Introduction

In this paper we consider the TARGET SET SELECTION problem. In the problem one is given a graph $G$ with a function thr: $V(G) \to N \cup \{0\}$ (a threshold function), and two integers $k, \ell$. The question of the problem is to find a vertex subset $S \subseteq V(G)$ (a target set) such that $|S| \le k$ and if we initially activate $S$ then eventually at least $\ell$ vertices of $G$ become activated.

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

© Ivan Bliznets and Danil Sagunov;
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. 22; pp. 22:1–22:14

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

Leibniz International Proceedings in Informatics
LIPICS
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
The activation process is defined by the following two rules: (i) if a vertex becomes activated it stays activated forever; (ii) vertex $v$ becomes activated if either it was activated initially or at some moment there is at least $\text{thr}(v)$ activated vertices in the set of its neighbours $N(v)$. Often in the literature by **TARGET SET SELECTION** people refer to the special case of **TARGET SET SELECTION** where $\ell = |V(G)|$, i.e. where we need to activate all vertices of the graph. We refer to this special case as **PERFECT TARGET SET SELECTION**.

TARGET SET SELECTION problem naturally arises in such areas as economy, sociology, medicine. Let us give an example of a scenario [24, 6] under which TARGET SET SELECTION may arise in the marketing area. Often people start using some product when they find out that some number of their friends are already using it. Keeping this in mind, it is reasonable to start the following advertisement campaign of a product: give out the product for free to some people; these people start using the product, and then some friends of these people start using the product, then some friends of these friends and so on. For a given limited budget for the campaign we would like to give out the product in a way that eventually we get the most users of the product. Or we may be given the desired number of users of the product and we would like to find out what initial budget is sufficient. It is easy to see that this situation is finely modelled by the TARGET SET SELECTION problem.

The fact that TARGET SET SELECTION naturally arises in many different fields leads to a situation that the problem and its different special cases were studied under different names: IRREVERSIBLE $k$-CONVERSION SET [10, 16], $P_3$-HULL NUMBER [3], $r$-NEIGHBOUR BOOTSTRAP PERCOLATION [4], $(k, \ell)$-INFLUENCE [5], monotone dynamic monopolies [27], a generalization of PERFECT TARGET SET SELECTION on the case of oriented graphs is known as CHAIN REACTION CLOSURE and $t$-THRESHOLD STARTING SET [1]. In [10], Centeno et al. showed that PERFECT TARGET SET SELECTION is NP-hard even when all threshold values are equal to two.

There is an extensive list of results on TARGET SET SELECTION from parameterized and approximation point of view. Many different parameterizations were studied in the literature such as size of the target set, treewidth, feedback vertex set, diameter, vertex cover, cluster editing number and others (for more details, see Table 1). Most of these studies consider the PERFECT TARGET SET SELECTION problem, i.e. the case where $\ell = |V(G)|$. However, FPT membership results for parameters treewidth [6] and cliquewidth [23] were given for the general case of TARGET SET SELECTION. From approximation point of view, it is known that the minimization version (minimize the number of vertices in a target set for a fixed $\ell$) of the problem is very hard and cannot be approximated within $O(2^{\log_{1-\epsilon} n})$ factor for any $\epsilon > 0$, unless NP $\subseteq$ DTIME($n^{polylog(n)}$). This inappoximability result holds even for graphs of constant degree with all thresholds being at most two [11]. Also, the maximization version of the problem (maximize the number of activated vertices for a fixed $k$) is NP-hard to approximate within a factor of $n^{1-\epsilon}$ for any $\epsilon > 0$ [24].

Taking into account many intractability results for the problem, it is natural to ask whether we can beat a trivial brute-force algorithm for this problem or its important subcase PERFECT TARGET SET SELECTION. In other words, can we construct an algorithm with running time $O^*((2 - \epsilon)^n)$ for some $\epsilon > 0$. Surprisingly, the answer to this question is still unknown. Note that the questions whether we can beat brute-force naturally arise in computer science and have significant theoretic importance. Probably, the most important such question is SETH hypothesis which informally can be stated as:

**Hypothesis 1 (SETH).** There is no algorithm for SAT with running time $O^*((2 - \epsilon)^n)$ for any $\epsilon > 0$.

Another example of such question is the following hypothesis:
The activation process is defined by the following two rules: (i) if a vertex becomes activated it stays activated forever; (ii) vertex $v$ becomes activated if either it was activated initially or at some moment there is at least $\text{thr}(v)$ activated vertices in the set of its neighbours $N(v)$. Often in the literature by **TARGET SET SELECTION** people refer to the special case of **TARGET SET SELECTION** where $\ell = |V(G)|$, i.e. where we need to activate all vertices of the graph. We refer to this special case as **PERFECT TARGET SET SELECTION**.

TARGET SET SELECTION problem naturally arises in such areas as economy, sociology, medicine. Let us give an example of a scenario [24, 6] under which TARGET SET SELECTION may arise in the marketing area. Often people start using some product when they find out that some number of their friends are already using it. Keeping this in mind, it is reasonable to start the following advertisement campaign of a product: give out the product for free to some people; these people start using the product, and then some friends of these people start using the product, then some friends of these friends and so on. For a given limited budget for the campaign we would like to give out the product in a way that eventually we get the most users of the product. Or we may be given the desired number of users of the product and we would like to find out what initial budget is sufficient. It is easy to see that this situation is finely modelled by the TARGET SET SELECTION problem.

The fact that TARGET SET SELECTION naturally arises in many different fields leads to a situation that the problem and its different special cases were studied under different names: **IRREVERSIBLE k-CONVERSION SET** [10, 16], **P₃-HULL NUMBER** [3], **r-NEIGHBOUR BOOTSTRAP PERCOLATION** [4], **(k, ℓ)-INFLUENCE** [5], monotone dynamic monopolies [27], a generalization of **PERFECT TARGET SET SELECTION** on the case of oriented graphs is known as **CHAIN REACTION CLOSURE** and **t-THRESHOLD STARTING SET** [1]. In [10], Centeno et al. showed that **PERFECT TARGET SET SELECTION** is NP-hard even when all threshold values are equal to two.

There is an extensive list of results on TARGET SET SELECTION from parameterized and approximation point of view. Many different parameterizations were studied in the literature such as size of the target set, treewidth, feedback vertex set, diameter, vertex cover, cluster editing number and others (for more details, see Table 1). Most of these studies consider the **PERFECT TARGET SET SELECTION** problem, i.e. the case where $\ell = |V(G)|$. However, FPT membership results for parameters treewidth [6] and cliquewidth [23] were given for the general case of TARGET SET SELECTION. From approximation point of view, it is known that the minimization version (minimize the number of vertices in a target set for a fixed $\ell$) of the problem is very hard and cannot be approximated within $O(2^{\log^{1-\epsilon}n})$ factor for any $\epsilon > 0$, unless NP $\subseteq$ DTIME($n^{polylog(n)}$). This inappoximability result holds even for graphs of constant degree with all thresholds being at most two [11]. Also, the maximization version of the problem (maximize the number of activated vertices for a fixed $k$) is NP-hard to approximate within a factor of $n^{1-\epsilon}$ for any $\epsilon > 0$ [24].

Taking into account many intractability results for the problem, it is natural to ask whether we can beat a trivial brute-force algorithm for this problem or its important subcase **PERFECT TARGET SET SELECTION**. In other words, can we construct an algorithm with running time $O^*((2 - \epsilon)^n)$ for some $\epsilon > 0$. Surprisingly, the answer to this question is still unknown. Note that the questions whether we can beat brute-force naturally arise in computer science and have significant theoretic importance. Probably, the most important such question is SETH hypothesis which informally can be stated as:

**Hypothesis 1 (SETH).** There is no algorithm for SAT with running time $O^*((2 - \epsilon)^n)$ for any $\epsilon > 0$.

Another example of such question is the following hypothesis:
<table><caption>**Table 1** Some known results on different parameterizations of PERFECT TARGET SET SELECTION. In the Thresholds column we indicate restrictions on the threshold function under which the results were obtained. Here *t* denotes the maximum threshold value.</caption><thead><tr><th>Parameter</th><th>Thresholds</th><th>Result</th><th>Reference</th></tr></thead><tbody><tr><td>Bandwidth <i>b</i></td><td>general</td><td><i>O</i><sup>*</sup>(<i>b</i><sup><i>O</i>(<i>b</i> log <i>b</i>)</sup>)</td><td>Chopin et al. [12]</td></tr><tr><td>Clique Cover Number <i>c</i></td><td>general</td><td>NP-hard for <i>c</i> = 2</td><td>Chopin et al. [12]</td></tr><tr><td>Cliquewidth <i>cw</i></td><td>constant</td><td><i>O</i><sup>*</sup>((<i>cw</i> &middot; <i>t</i>)<sup><i>O</i>(<i>cw</i>&middot;<i>t</i>)</sup>)</td><td>Hartmann [23]</td></tr><tr><td>Cluster Editing Number <i>&zeta;</i></td><td>general</td><td><i>O</i><sup>*</sup>(16<sup><i>&zeta;</i></sup>)</td><td>Nichterlein et al. [26]</td></tr><tr><td>Diameter <i>d</i></td><td>general</td><td>NP-hard for <i>d</i> = 2</td><td>Nichterlein et al. [26]</td></tr><tr><td>Feedback Edge Set Number <i>f</i></td><td>general</td><td><i>O</i><sup>*</sup>(4<sup><i>f</i></sup>)</td><td>Nichterlein et al. [26]</td></tr><tr><td>Feedback Vertex Set Number</td><td>general</td><td>W[1]-hard</td><td>Ben-Zwi et al. [6]</td></tr><tr><td>Neighborhood Diversity <i>nd</i></td><td>majority</td><td><i>O</i><sup>*</sup>(<i>nd</i><sup><i>O</i>(<i>nd</i>)</sup>)</td><td>Dvořák et al. [17]</td></tr><tr><td></td><td>general</td><td>W[1]-hard</td><td>Dvořák et al. [17]</td></tr><tr><td>Target Set Size <i>k</i></td><td>constant</td><td>W[P]-complete</td><td>Abrahamson et al. [1], Bazgan et al. [5]</td></tr><tr><td>Treewidth <i>w</i></td><td>constant</td><td><i>O</i><sup>*</sup>(<i>t</i><sup><i>O</i>(<i>w</i> log <i>w</i>)</sup>)</td><td>Ben-Zwi et al. [6]</td></tr><tr><td></td><td>majority</td><td>W[1]-hard</td><td>Chopin et al. [12]</td></tr><tr><td>Vertex Cover Number <i>&tau;</i></td><td>general</td><td><i>O</i><sup>*</sup>(2<sup>(2<sup><i>&tau;</i></sup>+1) &middot; <i>&tau;</i></sup>)</td><td>Nichterlein et al. [26]</td></tr></tbody></table>

**► Hypothesis 2.** [29] For every hereditary graph class Π that can be recognized in polynomial time, the MAXIMUM INDUCED Π-SUBGRAPH problem can be solved in <i>O</i><sup>*</sup>((2 − ε)<sup>n</sup>) time for some ε > 0.

There is a significant number of papers [9, 28, 19, 18, 14, 30, 22, 13, 15, 7, 20] with the main motivation to present an algorithm faster than the trivial one.

As in the stated hypotheses and mentioned papers, our goal is to come up with an algorithm that works faster than brute-force. We partially answer this question by presenting several <i>O</i><sup>*</sup>((2 − ε)<sup>n</sup>) running time algorithms for TARGET SET SELECTION when thresholds, i.e. the values of thr(v), are bounded by some fixed constant and in case when the values of thr(v) − deg(v), so-called dual thresholds, are bounded by some fixed constant for every v ∈ V(G). We think that this result may be interesting mainly because of the following two reasons. Firstly, the result is established for a well-studied problem with many applications and hence can reveal some important combinatorial or algorithmic structure of the problem. Secondly, maybe by resolving the asked question we could make progress in resolving hypotheses 1, 2.

**Our results.** In this paper, we establish the following algorithmic results.

PERFECT TARGET SET SELECTION can be solved in

- <i>O</i><sup>*</sup>(1.90345<sup>n</sup>) if for every v ∈ V(G) we have thr(v) ≤ 2;

- <i>O</i><sup>*</sup>(1.98577<sup>n</sup>) if for every v ∈ V(G) we have thr(v) ≤ 3;

- <i>O</i><sup>*</sup>((2 − ε<sub>d</sub>)<sup>n</sup>) randomized time if for every v ∈ V(G) we have thr(v) ≥ deg(v) − d.

TARGET SET SELECTION can be solved in

- <i>O</i><sup>*</sup>(1.99001<sup>n</sup>) if for every v ∈ V(G) we have thr(v) ≤ ⌊ deg(v) / 3 ⌋;

- <i>O</i><sup>*</sup>((2 − ε<sub>t</sub>)<sup>n</sup>) if for every v ∈ V(G) we have thr(v) ≤ t.

We also prove the following lower bound.

TARGET SET SELECTION parameterized by ℓ is W[1]-hard even if

- thr(v) = 2 for every v ∈ V(G).
<table><caption>**Table 1** Some known results on different parameterizations of PERFECT TARGET SET SELECTION. In the Thresholds column we indicate restrictions on the threshold function under which the results were obtained. Here *t* denotes the maximum threshold value.</caption><thead><tr><th>Parameter</th><th>Thresholds</th><th>Result</th><th>Reference</th></tr></thead><tbody><tr><td>Bandwidth <i>b</i></td><td>general</td><td><i>O</i><sup>*</sup>(<i>b</i><sup>O(b log <i>b</i>)</sup>)</td><td>Chopin et al. [12]</td></tr><tr><td>Clique Cover Number <i>c</i></td><td>general</td><td>NP-hard for <i>c</i> = 2</td><td>Chopin et al. [12]</td></tr><tr><td>Cliquewidth <i>cw</i></td><td>constant</td><td><i>O</i><sup>*</sup>((<i>cw</i> &middot; <i>t</i>)<sup>O(<i>cw</i>&middot;<i>t</i>)</sup>)</td><td>Hartmann [23]</td></tr><tr><td>Cluster Editing Number <i>&zeta;</i></td><td>general</td><td><i>O</i><sup>*</sup>(16<sup><i>&zeta;</i></sup>)</td><td>Nichterlein et al. [26]</td></tr><tr><td>Diameter <i>d</i></td><td>general</td><td>NP-hard for <i>d</i> = 2</td><td>Nichterlein et al. [26]</td></tr><tr><td>Feedback Edge Set Number <i>f</i></td><td>general</td><td><i>O</i><sup>*</sup>(4<sup><i>f</i></sup>)</td><td>Nichterlein et al. [26]</td></tr><tr><td>Feedback Vertex Set Number</td><td>general</td><td>W[1]-hard</td><td>Ben-Zwi et al. [6]</td></tr><tr><td rowspan="2">Neighborhood Diversity <i>nd</i></td><td>majority</td><td><i>O</i><sup>*</sup>(nd<sup>O(<i>nd</i>)</sup>)</td><td>Dvořák et al. [17]</td></tr><tr><td>general</td><td>W[1]-hard</td><td>Dvořák et al. [17]</td></tr><tr><td>Target Set Size <i>k</i></td><td>constant</td><td>W[P]-complete</td><td>Abrahamson et al. [1], Bazgan et al. [5]</td></tr><tr><td>Treewidth <i>w</i></td><td>constant</td><td><i>O</i><sup>*</sup>(<i>t</i><sup>O(<i>w</i> log <i>w</i>)</sup>)</td><td>Ben-Zwi et al. [6]</td></tr><tr><td rowspan="2">Vertex Cover Number <i>&tau;</i></td><td>majority</td><td>W[1]-hard</td><td>Chopin et al. [12]</td></tr><tr><td>general</td><td><i>O</i><sup>*</sup>(2<sup>(2<sup><i>&tau;</i></sup>+1) &middot; <i>&tau;</i></sup>)</td><td>Nichterlein et al. [26]</td></tr></tbody></table>

**► Hypothesis 2.** [29] For every hereditary graph class Π that can be recognized in polynomial time, the MAXIMUM INDUCED Π-SUBGRAPH problem can be solved in <i>O</i><sup>*</sup>((2 − ε)<sup>n</sup>) time for some ε > 0.

There is a significant number of papers [9, 28, 19, 18, 14, 30, 22, 13, 15, 7, 20] with the main motivation to present an algorithm faster than the trivial one.

As in the stated hypotheses and mentioned papers, our goal is to come up with an algorithm that works faster than brute-force. We partially answer this question by presenting several <i>O</i><sup>*</sup>((2 − ε)<sup>n</sup>) running time algorithms for TARGET SET SELECTION when thresholds, i.e. the values of thr(v), are bounded by some fixed constant and in case when the values of thr(v) − deg(v), so-called dual thresholds, are bounded by some fixed constant for every v ∈ V(G). We think that this result may be interesting mainly because of the following two reasons. Firstly, the result is established for a well-studied problem with many applications and hence can reveal some important combinatorial or algorithmic structure of the problem. Secondly, maybe by resolving the asked question we could make progress in resolving hypotheses 1, 2.

**Our results.** In this paper, we establish the following algorithmic results.

PERFECT TARGET SET SELECTION can be solved in

- <i>O</i><sup>*</sup>(1.90345<sup>n</sup>) if for every v ∈ V(G) we have thr(v) ≤ 2;

- <i>O</i><sup>*</sup>(1.98577<sup>n</sup>) if for every v ∈ V(G) we have thr(v) ≤ 3;

- <i>O</i><sup>*</sup>((2 − ε<sub>d</sub>)<sup>n</sup>) randomized time if for every v ∈ V(G) we have thr(v) ≥ deg(v) − d.

TARGET SET SELECTION can be solved in

- <i>O</i><sup>*</sup>(1.99001<sup>n</sup>) if for every v ∈ V(G) we have thr(v) ≤ ⌊ deg(v) / 3 ⌋;

- <i>O</i><sup>*</sup>((2 − ε<sub>t</sub>)<sup>n</sup>) if for every v ∈ V(G) we have thr(v) ≤ t.

We also prove the following lower bound.

TARGET SET SELECTION parameterized by ℓ is W[1]-hard even if

- thr(v) = 2 for every v ∈ V(G).
# 2 Preliminaries

## 2.1 Notation and problem definition

We use standard graph notation. We consider only simple graphs, i.e. undirected graphs without loops and multiple edges. By $V(G)$ we denote the set of vertices of $G$ and by $E(G)$ we denote the set of its edges. We let $n = |V(G)|$. $N(v)$ denotes the set of neighbours of vertex $v \in V(G)$, and $N[v] = N(v) \cup \{v\}$. $\Delta(G) = \max_{v \in V(G)} \deg(v)$ denotes the maximum degree of $G$. By $G[F]$ we denote the subgraph of $G$ induced by a set $F$ of its vertices. Define by $\deg_F(v)$ the degree of $v$ in the subgraph $G[F]$.

By $X_1 \sqcup X_2 \sqcup \dots \sqcup X_m$ we denote the disjoint union of sets $X_1, X_2, \dots, X_m$, i.e. $X_1 \sqcup X_2 \sqcup \dots \sqcup X_m = X_1 \cup X_2 \cup \dots \cup X_m$ with the additional restriction that $X_i \cap X_j = \emptyset$ for any distinct $i, j$.

For a graph $G$, threshold function $thr$ and $X \subseteq V(G)$ we put $S_0(X) = X$ and for every $i > 0$ we define $S_i(X) = S_{i-1}(X) \cup \{v \in V(G) : |N(v) \cap S_{i-1}(X)| \ge \text{thr}(v)\}$. We say that $v$ becomes activated in the $i^{th}$ round, if $v \in S_i(X) \setminus S_{i-1}(X)$, i.e. $v$ is not activated in the $(i-1)^{th}$ round and is activated in the $i^{th}$ round. By activation process yielded by $X$ we mean the sequence $S_0(X), S_1(X), \dots, S_i(X), \dots, S_n(X)$. Note that $S_n(X) = S_{n+1}(X)$ as $S_i(X) \subseteq S_{i+1}(X)$ and $n$ rounds is always enough for the activation process to converge. By $S(X)$ we denote the set of vertices that eventually become activated, and we say that $X$ activates $S(X)$ in $(G, \text{thr})$. Thus, $S(X) = S_n(X)$.

We recall the definition of TARGET SET SELECTION.

**TARGET SET SELECTION**

**Input:** A graph $G$ with thresholds $thr: V(G) \to \mathbb{N} \cup \{0\}$, integers $k, \ell$.

**Question:** Is there a set $X \subseteq V(G)$ such that $|X| \le k$ and $|S(X)| \ge \ell$?

We call a solution $X$ of TARGET SET SELECTION a *target set of* $(G, \text{thr})$.

By PERFECT TARGET SET SELECTION we understand a special case of TARGET SET SELECTION with $\ell = n$. We call $X$ a *perfect target set of* $(G, \text{thr})$, if it activates all vertices of $G$, i.e. $S(X) = V(G)$.

Most of the algorithms described in this paper are recursive algorithms that use branching technique. Such algorithms are described by *reduction rules*, that are used to simplify a problem instance, and *branching rules*, that are used to solve an instance by recursively solving smaller instances. If a branching rule branches an instance of size $n$ into $r$ instances of size $n - t_1, n - t_2, \dots, n - t_r$, we call $(t_1, t_2, \dots, t_r)$ a *branching vector* of this branching rule. By a *branching factor* of a branching rule we understand a constant $c$ that is a solution of a linear recurrence corresponding to some branching vector of this rule; such constants are used to bound the running time of an algorithm following the rule with $c^n$. Note that a branching rule may have multiple corresponding branching vectors and multiple corresponding branching factors. By the *worst branching factor* of a branching rule (or multiple branching rules, if they are applied within the same algorithm) we understand the largest among its branching factors. We refer to [21] for a more detailed explanation of these aspects.

In our work we also use the following folklore result.

**► Lemma 1.** For any positive integer $n$ and any $\alpha$ such that $0 < \alpha \le \frac{1}{2}$, we have $\sum_{i=0}^{\lfloor \alpha n \rfloor} \binom{n}{i} \le 2^{H(\alpha)n}$, where $H(\alpha) = -\alpha \log_2(\alpha) - (1-\alpha) \log_2(1-\alpha)$.
## 2 Preliminaries

### 2.1 Notation and problem definition

We use standard graph notation. We consider only simple graphs, i.e. undirected graphs without loops and multiple edges. By $V(G)$ we denote the set of vertices of $G$ and by $E(G)$ we denote the set of its edges. We let $n = |V(G)|$. $N(v)$ denotes the set of neighbours of vertex $v \in V(G)$, and $N[v] = N(v) \cup \{v\}$. $\Delta(G) = \max_{v \in V(G)} \deg(v)$ denotes the maximum degree of $G$. By $G[F]$ we denote the subgraph of $G$ induced by a set $F$ of its vertices. Define by $\deg_F(v)$ the degree of $v$ in the subgraph $G[F]$.

By $X_1 \sqcup X_2 \sqcup \dots \sqcup X_m$ we denote the disjoint union of sets $X_1, X_2, \dots, X_m$, i.e. $X_1 \sqcup X_2 \sqcup \dots \sqcup X_m = X_1 \cup X_2 \cup \dots \cup X_m$ with the additional restriction that $X_i \cap X_j = \emptyset$ for any distinct $i, j$.

For a graph $G$, threshold function $thr$ and $X \subseteq V(G)$ we put $S_0(X) = X$ and for every $i > 0$ we define $S_i(X) = S_{i-1}(X) \cup \{v \in V(G) : |N(v) \cap S_{i-1}(X)| \ge \text{thr}(v)\}$. We say that $v$ becomes activated in the $i^{th}$ round, if $v \in S_i(X) \setminus S_{i-1}(X)$, i.e. $v$ is not activated in the $(i-1)^{th}$ round and is activated in the $i^{th}$ round. By activation process yielded by $X$ we mean the sequence $S_0(X), S_1(X), \dots, S_i(X), \dots, S_n(X)$. Note that $S_n(X) = S_{n+1}(X)$ as $S_i(X) \subseteq S_{i+1}(X)$ and $n$ rounds is always enough for the activation process to converge. By $S(X)$ we denote the set of vertices that eventually become activated, and we say that $X$ activates $S(X)$ in $(G, \text{thr})$. Thus, $S(X) = S_n(X)$.

We recall the definition of TARGET SET SELECTION.

**TARGET SET SELECTION**

**Input:** A graph $G$ with thresholds $thr: V(G) \rightarrow \mathbb{N} \cup \{0\}$, integers $k, \ell$.

**Question:** Is there a set $X \subseteq V(G)$ such that $|X| \le k$ and $|S(X)| \ge \ell$?

We call a solution $X$ of TARGET SET SELECTION a *target set of* $(G, \text{thr})$.

By PERFECT TARGET SET SELECTION we understand a special case of TARGET SET SELECTION with $\ell = n$. We call $X$ a *perfect target set of* $(G, \text{thr})$, if it activates all vertices of $G$, i.e. $S(X) = V(G)$.

Most of the algorithms described in this paper are recursive algorithms that use branching technique. Such algorithms are described by *reduction rules*, that are used to simplify a problem instance, and *branching rules*, that are used to solve an instance by recursively solving smaller instances. If a branching rule branches an instance of size $n$ into $r$ instances of size $n - t_1, n - t_2, \dots, n - t_r$, we call $(t_1, t_2, \dots, t_r)$ a *branching vector* of this branching rule. By a *branching factor* of a branching rule we understand a constant $c$ that is a solution of a linear recurrence corresponding to some branching vector of this rule; such constants are used to bound the running time of an algorithm following the rule with $c^n$. Note that a branching rule may have multiple corresponding branching vectors and multiple corresponding branching factors. By the *worst branching factor* of a branching rule (or multiple branching rules, if they are applied within the same algorithm) we understand the largest among its branching factors. We refer to [21] for a more detailed explanation of these aspects.

In our work we also use the following folklore result.

**► Lemma 1.** For any positive integer $n$ and any $\alpha$ such that $0 < \alpha \le \frac{1}{2}$, we have $\sum_{i=0}^{\lfloor \alpha n \rfloor} \binom{n}{i} \le 2^{H(\alpha)n}$, where $H(\alpha) = -\alpha \log_2(\alpha) - (1-\alpha) \log_2(1-\alpha)$.
**Algorithm: minimal_pvcs(G, F, A, Z)**

**Input:** Graph G with $\Delta(G) < t$, vertex subsets $F, A, Z$ such that $F \cup A \cup Z = V(G)$.

**Output:** All minimal partial vertex covers $S$ of $G$ such that $S \cap (A \cup Z) = A$.

if $\exists v : N[v] \subseteq F$ then

**foreach** $R \subseteq N[v]$ **do**
  &nbsp;&nbsp;&nbsp;&nbsp;**minimal_pvcs**($G, F \setminus N[v], A \cup R, Z \cup (N[v] \setminus R)$)

else

**foreach** $R \subseteq F$ **do**
  &nbsp;&nbsp;&nbsp;&nbsp;**if** $A \cup R$ is a minimal partial vertex cover of $G$ **then**
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**output** $A \cup R$

<caption>Figure 1 Algorithm enumerating all minimal partial vertex covers of a graph.</caption>

## 2.2 Minimal partial vertex covers

**Definition 2.** Let $G$ be a graph. We call a subset $S \subseteq V(G)$ of its vertices a $T$-partial vertex cover of $G$ for some $T \subseteq E(G)$, if the set of edges covered by vertices in $S$ is exactly $T$, i.e. $T = \{uv : \{u, v\} \cap S \neq \emptyset, uv \in E(G)\}$.

We call a $T$-partial vertex cover $S$ of $G$ a minimal partial vertex cover of $G$ if there is no $T$-partial vertex cover $S'$ of $G$ with $S' \subseteq S$. Equivalently, there is no vertex $v \in S$ so that $S \setminus \{v\}$ is a $T$-partial vertex cover of $G$.

The following theorem bounds the number of minimal partial vertex covers in graphs of bounded degree. We note that somewhat similar results were proven by Björklund et al. [8].

**Theorem 3.** For any positive integer $t$, there is a constant $\omega_t < 1$ and an algorithm that, given an $n$-vertex graph $G$ with $\Delta(G) < t$ as input, outputs all minimal partial vertex covers of $G$ in $O^*(2^{\omega_t n})$ time.

**Proof.** We present a recursive branching algorithm that lists all minimal partial vertex covers of $G$. Pseudocode of the algorithm is presented in Figure 1. As input, the algorithm takes three sets $F, A, Z$ such that $F \cup A \cup Z = V(G)$. The purpose of the algorithm is to enumerate all minimal partial vertex covers that contain $A$ as a subset and do not intersect with $Z$. So the algorithm outputs all minimal partial vertex covers $S$ of $G$ satisfying $S \cap (A \cup Z) = A$. It is easy to see that then `minimal_pvcs(G, V(G), \emptyset, \emptyset)` enumerates all minimal partial vertex covers of $G$.

The algorithm uses only the following branching rule. If there is a vertex $v \in F$ such that $N(v) \subseteq F$ then consider $2^{|N[v]|} - 1$ branches. In each branch, take some $R \subseteq N[v]$ and run `minimal_pvcs(G, F \ N[v], A \cup R, Z \cup (N[v] \setminus R))`. In other words, we branch on which vertices in $N[v]$ belong to minimal partial vertex cover and which do not. Note that if $S$ is a minimal partial vertex cover then it cannot contain $N[v]$, since otherwise $S \setminus \{v\}$ is its proper subset and covers the same edges. Hence, above branching consider all possible cases. Since $\Delta(G) < t$, the worst branching factor is $(2^t - 1)^{\frac{1}{t}}$.

If the branching rule cannot be applied then we apply brute-force on all possible variants of the intersection of the minimal partial vertex cover $S$ and the set $F$. So we consider all $2^{|F|}$ variants of $S \cap F$, and filter out variants that do not correspond to a minimal partial vertex cover. Minimality of a partial vertex cover can be checked in polynomial time, so filtering out adds only a polynomial factor.
Note that we run brute-force only if every vertex in $F$ has at least one neighbour in $A \cup Z$, in other words, $A \cup Z$ is a dominating set of $G$. Since $\Delta(G) < t$, any dominating set of $G$ consists of at least $\frac{n}{t}$ vertices. Hence, $|F| \le \frac{(t-1)n}{t}$. This leads to the following upper bound on the running time of the algorithm:

$$((2^t - 1)^{\frac{1}{t}})^{\frac{n}{t}} \cdot 2^{\frac{(t-1)n}{t}} \cdot n^{O(1)}$$

Hence, we can put $\omega_t = \frac{1}{t^2} \log (2^t - 1) + \frac{t-1}{t} < 1$.

# 3 Algorithms for bounded thresholds

## 3.1 Algorithm for thresholds bounded by fixed constant

In this subsection we prove the following theorem.

**Theorem 4.** Let $t$ be a fixed constant. For TARGET SET SELECTION with all thresholds bounded by $t$ there is a $O^*((2 - \epsilon_t)^n)$-time algorithm, where $\epsilon_t$ is a positive constant that depends only on $t$.

Our algorithm consists of three main stages. In the first stage we apply some simple reduction and branching rules. If the instance becomes small enough we then apply brute-force and solve the problem. Otherwise, we move to the second stage of the algorithm. In the second stage we perform branching rules that help us describe the activation process. After that we move to the third stage in which we run special dynamic program that finally solves the problem for each branch. Let us start the description of the algorithm.

### 3.1.1 Stage I

In the first stage our algorithm applies some branching rules. In each branch we maintain the following partition of $V(G)$ into three parts $A, Z, F$. These parts have the following meaning: $A$ is the set of vertices that are known to be in our target set, $Z$ — the set of vertices that are known to be not in the target set, $F$ — the set of all other vertices (i.e. vertices about that we do not know any information so far). At the beginning, we have $A = Z = \emptyset$ and $F = V(G)$.

We start the first stage with exhaustive application of reduction rule 1 and branching rule 1.

**Reduction rule 1.** If there is any vertex $v \in S(A)$, but $v \notin A \cup Z$, then assign $v$ to $Z$.

Reduction rule 1 is correct as there is no need to put a vertex in a target set if it will become activated eventually by the influence of its neighbours.

**Branching rule 1.** If there is a vertex $v \in F$ such that $\deg_F(v) \ge \text{thr}(v)$ then arbitrarily choose a subset $T \subseteq N(v) \cap F$ such that $|T| = \text{thr}(v)$ and branch on the following branches:

1. For each subset of vertices $S \subseteq T \cup \{v\}$ of size less than $\text{thr}(v)$ consider a branch in which we put $S$ into $A$ and we put other vertices $T \cup \{v\} \setminus S$ into $Z$;

2. Additionally consider the branch in which we assign all vertices from $T$ to $A$ and $v$ is assigned to $Z$.

It is enough to consider only above-mentioned branches. All other possible branches assign at least $\text{thr}(v)$ vertices from $T \cup \{v\}$ to $A$, and we always can replace such branch with the branch assigning $T$ to $A$, since it leads to the activation of all vertices in $T \cup \{v\}$
Note that we run brute-force only if every vertex in $F$ has at least one neighbour in $A \cup Z$, in other words, $A \cup Z$ is a dominating set of $G$. Since $\Delta(G) < t$, any dominating set of $G$ consists of at least $\frac{n}{t}$ vertices. Hence, $|F| \le \frac{(t-1)n}{t}$. This leads to the following upper bound on the running time of the algorithm:

$$((2^t - 1)^{\frac{1}{t}})^{\frac{n}{t}} \cdot 2^{\frac{(t-1)n}{t}} \cdot n^{O(1)}.$$

Hence, we can put $\omega_t = \frac{1}{t^2} \log (2^t - 1) + \frac{t-1}{t} < 1$.

# 3 Algorithms for bounded thresholds

## 3.1 Algorithm for thresholds bounded by fixed constant

In this subsection we prove the following theorem.

**Theorem 4.** Let $t$ be a fixed constant. For TARGET SET SELECTION with all thresholds bounded by $t$ there is a $O^*((2 - \epsilon_t)^n)$-time algorithm, where $\epsilon_t$ is a positive constant that depends only on $t$.

Our algorithm consists of three main stages. In the first stage we apply some simple reduction and branching rules. If the instance becomes small enough we then apply brute-force and solve the problem. Otherwise, we move to the second stage of the algorithm. In the second stage we perform branching rules that help us describe the activation process. After that we move to the third stage in which we run special dynamic program that finally solves the problem for each branch. Let us start the description of the algorithm.

### 3.1.1 Stage I

In the first stage our algorithm applies some branching rules. In each branch we maintain the following partition of $V(G)$ into three parts $A, Z, F$. These parts have the following meaning: $A$ is the set of vertices that are known to be in our target set, $Z$ — the set of vertices that are known to be not in the target set, $F$ — the set of all other vertices (i.e. vertices about that we do not know any information so far). At the beginning, we have $A = Z = \emptyset$ and $F = V(G)$.

We start the first stage with exhaustive application of reduction rule 1 and branching rule 1.

**Reduction rule 1.** If there is any vertex $v \in S(A)$, but $v \notin A \cup Z$, then assign $v$ to $Z$.

Reduction rule 1 is correct as there is no need to put a vertex in a target set if it will become activated eventually by the influence of its neighbours.

**Branching rule 1.** If there is a vertex $v \in F$ such that $\deg_F(v) \ge \text{thr}(v)$ then arbitrarily choose a subset $T \subseteq N(v) \cap F$ such that $|T| = \text{thr}(v)$ and branch on the following branches:

1. For each subset of vertices $S \subseteq T \cup \{v\}$ of size less than $\text{thr}(v)$ consider a branch in which we put $S$ into $A$ and we put other vertices $T \cup \{v\} \setminus S$ into $Z$;

2. Additionally consider the branch in which we assign all vertices from $T$ to $A$ and $v$ is assigned to $Z$.

It is enough to consider only above-mentioned branches. All other possible branches assign at least $\text{thr}(v)$ vertices from $T \cup \{v\}$ to $A$, and we always can replace such branch with the branch assigning $T$ to $A$, since it leads to the activation of all vertices in $T \cup \{v\}$
and adds at most the same number of vertices into a target set. Branching rule 1 considers $2^{\text{thr}(v)+1} - \text{thr}(v) - 1$ options for $\text{thr}(v) + 1$ vertices, thus it gives the biggest branching factor of $(2^{t+1} - t - 1)^{\frac{(1-\gamma)n}{t+1}}$ (here and below $t = \max_{v \in V(G)} \text{thr}(v)$).

**► Branching rule 2.** If $|F| \le \gamma n$, where $\gamma$ is a constant to be chosen later, then simply apply brute-force on how vertices in $F$ should be assigned to $A$ and $Z$.

If branching rule 2 is applied in all branches then the running time of the whole algorithm is at most $2^{\gamma n}(2^{t+1} - t - 1)^{\frac{(1-\gamma)n}{t+1}}$ and we do not need to use stages II and III, as the problem is already solved in this case.

### 3.1.2 Stage II

After exhaustive application of reduction rule 1 and branching rules 1 and 2, in each branch we either know the answer or we have the following properties:

1. $\Delta(G[F]) < t$;

2. $|F| > \gamma n$;

3. $S(A) \subseteq A \cup Z$.

Now, in order to solve the problem it is left to identify the vertices of a target set that belong to $F$. It is too expensive to consider all $2^{|F|}$ subsets of $F$ as $F$ is too big. Instead of this direct approach (brute-force on all subsets of $F$) we consider several subbranches. In each such branch we almost completely describe the activation process of the graph. For each branch, knowing this information about the activation process, we find an appropriate target set by solving a special dynamic program in stage III.

Let $X$ be an answer (a target set). $X$ can be expressed as $X = A \sqcup B$ where $B \subseteq F$. At the beginning of the activation process only vertices in $S_0(X) = X = A \sqcup B$ are activated, after the first round vertices in $S_1(A \sqcup B)$ are activated, and so on. It is clear that $S(A \sqcup B) = S_n(A \sqcup B)$. Unfortunately, we cannot compute the sequence of $S_i(A \sqcup B)$ as we do not know $B$. Instead we compute the sequence $P_0, P_1, \dots, P_n = P$ such that $P_i \setminus B = S_i(X) \setminus B$ and $P_i \subseteq P_{i+1}$ for any $i$.

First of all, using Theorem 3 we list all minimal partial vertex covers of the graph $G[F]$. For each minimal partial vertex cover $C$ we create a branch that indicates that $C \subseteq B$ and, moreover, $C$ covers exactly the same edges in $G[F]$ as $B$ does. In other words, any edge in $G[F]$ has at least one endpoint in $B$ if and only if it has at least one endpoint in $C$. Note that such $C$ exists for any $B$. One can obtain $C$ by removing vertices from $B$ one by one while it covers the same edges as $B$. When no vertex can be removed, then, by definition, the remaining vertices form a minimal partial vertex cover.

Put $P_0 = A \sqcup C$. It is correct since $S_0(X) \setminus B = A = P_0 \setminus B$. We now show how to find $P_{i+1}$ having $P_i$. Recall that to do such transition from $S_i(X)$ to $S_{i+1}(X)$ it is enough to find vertices with the number of neighbours in $S_i(X)$ being at least the threshold value of that vertex. As for $P_i$ and $P_{i+1}$, it is sufficient to check that the number of activated neighbours has reached the threshold only for vertices that are not in $B$. Thus any transition from $P_i$ to $P_{i+1}$ can be done by using a procedure that, given $P_i$ and any vertex $v \notin P_i$, checks whether $v$ becomes activated in the $(i+1)^{\text{th}}$ round or not, under the assumption that $v \notin B$.

Given $P_i$ it is not always possible to find a unique $P_{i+1}$ as we do not know $B$. That is why in such cases we create several subbranches that indicate potential values of $P_{i+1}$.

Let us now show how to, for each vertex $v \notin P_i$, figure out whether $v$ is in $P_{i+1}$ (see pseudocode in Figure 2). Since we know $P_i$ and $P_i \subseteq P_{i+1}$, we assume that $v \notin P_i$.

If $|N(v) \cap P_i| \ge \text{thr}(v)$ then we simply include $v$ in $P_{i+1}$. We claim that this check is enough for $v \in F$.
and adds at most the same number of vertices into a target set. Branching rule 1 considers $2^{\text{thr}(v)+1} - \text{thr}(v) - 1$ options for $\text{thr}(v) + 1$ vertices, thus it gives the biggest branching factor of $(2^{t+1} - t - 1)^{\frac{(1-\gamma)n}{t+1}}$ (here and below $t = \max_{v \in V(G)} \text{thr}(v)$).

**► Branching rule 2.** If $|F| \le \gamma n$, where $\gamma$ is a constant to be chosen later, then simply apply brute-force on how vertices in $F$ should be assigned to $A$ and $Z$.

If branching rule 2 is applied in all branches then the running time of the whole algorithm is at most $2^{\gamma n}(2^{t+1} - t - 1)^{\frac{(1-\gamma)n}{t+1}}$ and we do not need to use stages II and III, as the problem is already solved in this case.

### 3.1.2 Stage II

After exhaustive application of reduction rule 1 and branching rules 1 and 2, in each branch we either know the answer or we have the following properties:

1. $\Delta(G[F]) < t$;

2. $|F| > \gamma n$;

3. $S(A) \subseteq A \cup Z$.

Now, in order to solve the problem it is left to identify the vertices of a target set that belong to $F$. It is too expensive to consider all $2^{|F|}$ subsets of $F$ as $F$ is too big. Instead of this direct approach (brute-force on all subsets of $F$) we consider several subbranches. In each such branch we almost completely describe the activation process of the graph. For each branch, knowing this information about the activation process, we find an appropriate target set by solving a special dynamic program in stage III.

Let $X$ be an answer (a target set). $X$ can be expressed as $X = A \sqcup B$ where $B \subseteq F$. At the beginning of the activation process only vertices in $S_0(X) = X = A \sqcup B$ are activated, after the first round vertices in $S_1(A \sqcup B)$ are activated, and so on. It is clear that $S(A \sqcup B) = S_n(A \sqcup B)$. Unfortunately, we cannot compute the sequence of $S_i(A \sqcup B)$ as we do not know $B$. Instead we compute the sequence $P_0, P_1, \dots, P_n = P$ such that $P_i \setminus B = S_i(X) \setminus B$ and $P_i \subseteq P_{i+1}$ for any $i$.

First of all, using Theorem 3 we list all minimal partial vertex covers of the graph $G[F]$. For each minimal partial vertex cover $C$ we create a branch that indicates that $C \subseteq B$ and, moreover, $C$ covers exactly the same edges in $G[F]$ as $B$ does. In other words, any edge in $G[F]$ has at least one endpoint in $B$ if and only if it has at least one endpoint in $C$. Note that such $C$ exists for any $B$. One can obtain $C$ by removing vertices from $B$ one by one while it covers the same edges as $B$. When no vertex can be removed, then, by definition, the remaining vertices form a minimal partial vertex cover.

Put $P_0 = A \sqcup C$. It is correct since $S_0(X) \setminus B = A = P_0 \setminus B$. We now show how to find $P_{i+1}$ having $P_i$. Recall that to do such transition from $S_i(X)$ to $S_{i+1}(X)$ it is enough to find vertices with the number of neighbours in $S_i(X)$ being at least the threshold value of that vertex. As for $P_i$ and $P_{i+1}$, it is sufficient to check that the number of activated neighbours has reached the threshold only for vertices that are not in $B$. Thus any transition from $P_i$ to $P_{i+1}$ can be done by using a procedure that, given $P_i$ and any vertex $v \notin P_i$, checks whether $v$ becomes activated in the $(i+1)^{\text{th}}$ round or not, under the assumption that $v \notin B$.

Given $P_i$ it is not always possible to find a unique $P_{i+1}$ as we do not know $B$. That is why in such cases we create several subbranches that indicate potential values of $P_{i+1}$.

Let us now show how to, for each vertex $v \notin P_i$, figure out whether $v$ is in $P_{i+1}$ (see pseudocode in Figure 2). Since we know $P_i$ and $P_i \subseteq P_{i+1}$, we assume that $v \notin P_i$.

If $|N(v) \cap P_i| \ge \text{thr}(v)$ then we simply include $v$ in $P_{i+1}$. We claim that this check is enough for $v \in F$.
**► Claim 1.** If $v \in F \setminus B$, then $v$ becomes activated in the $i^{th}$ round if and only if $|N(v) \cap P_i| \ge \text{thr}(v)$.

**Proof.** We show that by proving that $S_i(X) \cap N(v) = P_i \cap N(v)$ for every $v \in F \setminus B$. Note that $S_i(X) \setminus B = P_i \setminus B$ by definition of $P_i$. So it is enough to prove that $S_i(X) \cap N(v) \cap B = P_i \cap N(v) \cap B$, which is equivalent to $N(v) \cap B = P_i \cap N(v) \cap B$, as $B \subseteq S_i(X)$. Since $v \notin B$, then any $uv \in E(G[F])$ is covered by $B$ if and only if $u \in B$. $C$ covers the same edges in $G[F]$ as $B$ does, and also $v \notin C$, hence $C \cap N(v) = B \cap N(v)$. Thus, since $C \subseteq P_0 \subseteq P_i$, we get $P_i \cap B \cap N(v) = P_i \cap C \cap N(v) = C \cap N(v) = B \cap N(v)$. ◀

If $v \in B$, the decision for $v$ does not matter. Thus if $v \in F$ and $|N(v) \cap P_i| < \text{thr}(v)$, we may simply not include $v$ in $P_{i+1}$.

If $v \in Z$, at this point, we cannot compute the number of activated neighbours of $v$ exactly as we do not know what neighbours of $v$ are in $B$. Note that we do not need the exact number of such neighbours if we know that this value is at least $\text{thr}(v)$. Thus we branch into $\text{thr}(v) + 1$ subbranches corresponding to the value of $\min\{|N(v) \cap B|, \text{thr}(v)\}$, from now on we denote this value as $dg(v)$.

On the other hand, we know all activated neighbours of $v$ that are in $V(G) \setminus F$ since $S_i(X) \cap (V(G) \setminus F) = P_i \cap (V(G) \setminus F)$, as $B \subseteq F$. Let this number be $m = |N(v) \cap (P_i \setminus F)|$. So the number of activated neighbours of $v$ is at least $m + dg(v)$. Also there may be some activated neighbours of $v$ in $N(v) \cap P_i \cap F$. However, we cannot simply add $|N(v) \cap P_i \cap F|$ to $m + dg(v)$ since vertices in $P_i \cap B$ will be computed twice. So we are actually interested in the value of $|(N(v) \cap P_i \cap F) \setminus B|$. That is why for vertices from $N(v) \cap P_i \cap F$ we simply branch whether they are in $B$ or not. After that we compare $m + dg(v) + |(N(v) \cap P_i \cap F) \setminus B|$ with $\text{thr}(v)$ and figure out whether $v$ becomes activated in the current round or not.

Note that once we branch on the value of $\min\{|N(v) \cap B|, \text{thr}(v)\}$, or on whether $v \in B$ or not for some $v$, we will not branch on the same value or make a decision for the same vertex again as it makes no sense. Once fixed, the decision should not change along the whole branch and all of its subbranches, otherwise the information about $B$ would just become inconsistent.

Let us now bound the number of branches created. There are three types of branchings in the second stage:

1. Branching on the value of the minimal partial vertex cover $C$. By Theorem 3, there is at most $O^*(2^{\omega_t|F|})$ such branches.

2. Branching on the value of $dg(v) = \min\{|N(v) \cap B|, \text{thr}(v)\}$ with $v \in Z$. There is at most $(t+1)^{|Z|}$ such possibilities since $t \ge \min\{|N(v) \cap B|, \text{thr}(v)\} \ge 0$.

3. Branching on whether vertex $u$ is in $B$ or not. We perform this branching only for vertices in the set $N(v) \cap P_i \cap F$ with $v \in Z$ only when its size is strictly smaller than $\text{thr}(v) \le t$. Hence we perform a branching of this type on at most $(t-1)|Z|$ vertices.

Hence, the total number of the branches created in stage II is at most

$$2^{\omega_t|F|} \cdot (t+1)^{|Z|} \cdot 2^{(t-1)|Z|} \cdot n^{O(1)}.$$

### 3.1.3 Stage III

Now, for each branch our goal is to find the smallest set $X$ which activates at least $\ell$ vertices and agrees with all information obtained during branching in a particular branch. That is,
- $A \subseteq X, Z \cap X = \emptyset$ (branchings made in stage I);
- $C \subseteq X$ (branching of the first type in stage II);
**Claim 1.** If $v \in F \setminus B$, then $v$ becomes activated in the $i^{th}$ round if and only if $|N(v) \cap P_i| \ge \text{thr}(v)$.

**Proof.** We show that by proving that $S_i(X) \cap N(v) = P_i \cap N(v)$ for every $v \in F \setminus B$. Note that $S_i(X) \setminus B = P_i \setminus B$ by definition of $P_i$. So it is enough to prove that $S_i(X) \cap N(v) \cap B = P_i \cap N(v) \cap B$, which is equivalent to $N(v) \cap B = P_i \cap N(v) \cap B$, as $B \subseteq S_i(X)$. Since $v \notin B$, then any $uv \in E(G[F])$ is covered by $B$ if and only if $u \in B$. $C$ covers the same edges in $G[F]$ as $B$ does, and also $v \notin C$, hence $C \cap N(v) = B \cap N(v)$. Thus, since $C \subseteq P_0 \subseteq P_i$, we get $P_i \cap B \cap N(v) = P_i \cap C \cap N(v) = C \cap N(v) = B \cap N(v)$. ◀

If $v \in B$, the decision for $v$ does not matter. Thus if $v \in F$ and $|N(v) \cap P_i| < \text{thr}(v)$, we may simply not include $v$ in $P_{i+1}$.

If $v \in Z$, at this point, we cannot compute the number of activated neighbours of $v$ exactly as we do not know what neighbours of $v$ are in $B$. Note that we do not need the exact number of such neighbours if we know that this value is at least $\text{thr}(v)$. Thus we branch into $\text{thr}(v) + 1$ subbranches corresponding to the value of $\min\{|N(v) \cap B|, \text{thr}(v)\}$, from now on we denote this value as $dg(v)$.

On the other hand, we know all activated neighbours of $v$ that are in $V(G) \setminus F$ since $S_i(X) \cap (V(G) \setminus F) = P_i \cap (V(G) \setminus F)$, as $B \subseteq F$. Let this number be $m = |N(v) \cap (P_i \setminus F)|$. So the number of activated neighbours of $v$ is at least $m + dg(v)$. Also there may be some activated neighbours of $v$ in $N(v) \cap P_i \cap F$. However, we cannot simply add $|N(v) \cap P_i \cap F|$ to $m + dg(v)$ since vertices in $P_i \cap B$ will be computed twice. So we are actually interested in the value of $|(N(v) \cap P_i \cap F) \setminus B|$. That is why for vertices from $N(v) \cap P_i \cap F$ we simply branch whether they are in $B$ or not. After that we compare $m + dg(v) + |(N(v) \cap P_i \cap F) \setminus B|$ with $\text{thr}(v)$ and figure out whether $v$ becomes activated in the current round or not.

Note that once we branch on the value of $\min\{|N(v) \cap B|, \text{thr}(v)\}$, or on whether $v \in B$ or not for some $v$, we will not branch on the same value or make a decision for the same vertex again as it makes no sense. Once fixed, the decision should not change along the whole branch and all of its subbranches, otherwise the information about $B$ would just become inconsistent.

Let us now bound the number of branches created. There are three types of branchings in the second stage:

1. Branching on the value of the minimal partial vertex cover $C$. By Theorem 3, there is at most $\mathcal{O}^*(2^{\omega_t|F|})$ such branches.

2. Branching on the value of $dg(v) = \min\{|N(v) \cap B|, \text{thr}(v)\}$ with $v \in Z$. There is at most $(t+1)^{|Z|}$ such possibilities since $t \ge \min\{|N(v) \cap B|, \text{thr}(v)\} \ge 0$.

3. Branching on whether vertex $u$ is in $B$ or not. We perform this branching only for vertices in the set $N(v) \cap P_i \cap F$ with $v \in Z$ only when its size is strictly smaller than $\text{thr}(v) \le t$. Hence we perform a branching of this type on at most $(t-1)|Z|$ vertices.

Hence, the total number of the branches created in stage II is at most

$$2^{\omega_t|F|} \cdot (t+1)^{|Z|} \cdot 2^{(t-1)|Z|} \cdot n^{\mathcal{O}(1)}.$$

### 3.1.3 Stage III

Now, for each branch our goal is to find the smallest set $X$ which activates at least $\ell$ vertices and agrees with all information obtained during branching in a particular branch. That is,
- $A \subseteq X, Z \cap X = \emptyset$ (branchings made in stage I);
- $C \subseteq X$ (branching of the first type in stage II);
**Algorithm: is_activated(G, thr, A, Z, F, Pᵢ, v)**

**Input:** G, thr, A, Z, F as usual, Pᵢ such that Pᵢ \ B = Sᵢ(A ⊔ B) \ B for some B, and a vertex v /∈ Pᵢ.

**Output:** True, if v /∈ B and v ∈ Sᵢ₊₁(A ⊔ B);
False, if v /∈ B and v /∈ Sᵢ₊₁(A ⊔ B);
any answer, otherwise.

if |N(v) ∩ Pᵢ| ≥ thr(v) then

| return True

else if v ∈ F then

| return False

m ← |N(v) ∩ (Pᵢ \ F)|

branch on the value of dg(v) = min {|N(v) ∩ B|, thr(v)}

m ← m + dg(v)

foreach u ∈ Pᵢ ∩ N(v) ∩ F do

| branch on whether u ∈ B

if u /∈ B then

| m ← m + 1

return m ≥ thr(v)

<caption>Figure 2 Procedure determining whether a vertex becomes activated in the current round.</caption>

- information about min{|N(v) ∩ B|, thr(v)} (second type branchings in stage II);

- additional information whether certain vertices belong to X or not (third type branchings in stage II).

From now on we assume that we are considering some particular branching leaf. Let A'
be the set of vertices that are known to be in X for a given branch and Z' be the set of
vertices known to be not in X (note that A ⊆ A' and Z ⊆ Z'). Let Z = {v₁, v₂, ..., v_z}
and F' = V(G) \ A' \ Z' = {u₁, u₂, ..., u_{f'}}. So actually it is left to find B' ⊆ F' (in these
new terms, B = (A' \ A) ⊔ B') such that |A' ⊔ B'| ≤ k, |P ∪ A' ∪ B'| ≥ ℓ and for each
i ∈ {1, 2, ..., z} the value min{thr(v_i), |N(v_i) ∩ B|} equals dg(v_i). This is true since the
information obtained during branching completely determines the value of P.

In order to solve the obtained problem we employ dynamic programming. We create
a table TS of size f' × ℓ × (t + 1)². For all B'_1 such that |(B'_1 ∪ P) ∩ {u_1, u_2, ..., u_i}| = p
and min{thr(v_j), |N(v_j) ∩ ((A' \ A) ∪ B'_1)|} = d_j, in the field TS(i, p, d_1, d_2, ..., d_z) we
store any set B'_2 of minimum size such that A' ∪ B'_1 ∪ B'_2 is a potential solution, i.e.
|S(A' ∪ B'_1 ∪ B'_2)| = |(P ∪ B'_1 ∪ B'_2)| = |P ∩ (V(G) \ F')| + p + |B'_2| ≥ ℓ and for every j we
have min{thr(v_j), |N(v_j) ∩ ((A' \ A) ∪ B'_1 ∪ B'_2)|} = min{thr(v_j), |N(v_j) ∩ B'_2| + d_j} = dg(v_j).
Note that the choice of B'_2 depends only on values i, p, d_1, d_2, ..., d_z, but not on the value
of B'_1 directly. In other words, TS(i, p, d_1, d_2, ..., d_z) stores one of optimal ways of how the
remaining f' - i vertices in F' should be chosen into B' if the first i vertices in F' was chosen
correspondingly to the values of p and d_j.

Note that for some fields in the TS table there may be no appropriate value of B'_2 (there
is no appropriate solution). In such cases, we put the corresponding element to be equal to
V(G). It is a legitimate operation since we are solving a minimization problem. Note that
**Algorithm: is_activated(G, thr, A, Z, F, Pᵢ, v)**

**Input:** G, thr, A, Z, F as usual, Pᵢ such that Pᵢ \ B = Sᵢ(A ⊔ B) \ B for some B, and a vertex v /∈ Pᵢ.

**Output:** True, if v /∈ B and v ∈ Sᵢ₊₁(A ⊔ B);
False, if v /∈ B and v /∈ Sᵢ₊₁(A ⊔ B);
any answer, otherwise.

if |N(v) ∩ Pᵢ| ≥ thr(v) then

| return True

else if v ∈ F then

| return False

m ← |N(v) ∩ (Pᵢ \ F)|

branch on the value of dg(v) = min{|N(v) ∩ B|, thr(v)}

m ← m + dg(v)

foreach u ∈ Pᵢ ∩ N(v) ∩ F do

| branch on whether u ∈ B

if u /∈ B then

| m ← m + 1

return m ≥ thr(v)

<caption>Figure 2 Procedure determining whether a vertex becomes activated in the current round.</caption>

- information about min{|N(v) ∩ B|, thr(v)} (second type branchings in stage II);

- additional information whether certain vertices belong to X or not (third type branchings in stage II).

From now on we assume that we are considering some particular branching leaf. Let A'
be the set of vertices that are known to be in X for a given branch and Z' be the set of
vertices known to be not in X (note that A ⊆ A' and Z ⊆ Z'). Let Z = {v₁, v₂, ..., vz}
and F' = V(G) \ A' \ Z' = {u₁, u₂, ..., uf'}. So actually it is left to find B' ⊆ F' (in these
new terms, B = (A' \ A) ⊔ B') such that |A' ⊔ B'| ≤ k, |P ∪ A' ∪ B'| ≥ l and for each
i ∈ {1, 2, ..., z} the value min{thr(vi), |N(vi) ∩ B|} equals dg(vi). This is true since the
information obtained during branching completely determines the value of P.

In order to solve the obtained problem we employ dynamic programming. We create
a table TS of size f' × l × (t + 1)². For all B'_1 such that |(B'_1 ∪ P) ∩ {u_1, u_2, ..., u_i}| = p
and min{thr(v_j), |N(v_j) ∩ ((A' \ A) ∪ B'_1)|} = d_j, in the field TS(i, p, d_1, d_2, ..., d_z) we
store any set B'_2 of minimum size such that A' ∪ B'_1 ∪ B'_2 is a potential solution, i.e.
|S(A' ∪ B'_1 ∪ B'_2)| = |(P ∪ B'_1 ∪ B'_2)| = |P ∩ (V(G) \ F')| + p + |B'_2| ≥ l and for every j we
have min{thr(v_j), |N(v_j) ∩ ((A' \ A) ∪ B'_1 ∪ B'_2)|} = min{thr(v_j), |N(v_j) ∩ B'_2| + d_j} = dg(v_j).
Note that the choice of B'_2 depends only on values i, p, d_1, d_2, ..., d_z, but not on the value
of B'_1 directly. In other words, TS(i, p, d_1, d_2, ..., d_z) stores one of optimal ways of how the
remaining f' - i vertices in F' should be chosen into B' if the first i vertices in F' was chosen
correspondingly to the values of p and d_j.

Note that for some fields in the TS table there may be no appropriate value of B'_2 (there
is no appropriate solution). In such cases, we put the corresponding element to be equal to
V(G). It is a legitimate operation since we are solving a minimization problem. Note that
the desired value of $B'$ will be stored as

$$TS(0, 0, \min\{|N(v_1) \cap (A' \setminus A)|, \mathrm{thr}(v_1)\}, \dots, \min\{|N(v_z) \cap (A' \setminus A)|, \mathrm{thr}(v_z)\}).$$

We assign $TS(f', p, dg(v_1), dg(v_2), \dots, dg(v_z)) = \emptyset$ for every $p$ such that $p + |P \cap (V(G) \setminus F')| \ge \ell$. We do this since values $p, dg(v_1), dg(v_2), \dots, dg(v_z)$ indicate that $A' \sqcup B'_1$ is already a solution. In all other fields of type $TS(f', \dots, \cdot, \dots, \cdot)$ we put the value of $V(G)$. We now show how to evaluate values $TS(i, p, d_1, d_2, \dots, d_z)$ for any $i \ge 0$ smaller than $f'$. We can evaluate any $TS(i, \cdot, \cdot, \dots, \cdot)$ in polynomial time if we have all values $TS(i+1, \cdot, \cdot, \dots, \cdot)$ evaluated. For each $j \in \{1, 2, \dots, z\}$, let $d_j^{i+1} = \min\{\mathrm{thr}(v_j), d_j + |N(v_j) \cap \{u_{i+1}\}|\}$. In order to compute $TS(i, p, d_1, d_2, \dots, d_z)$, we need to decide whether $u_{i+1}$ is in a target set or not. If $u_{i+1}$ is taken into $B'$ then $d_j$ becomes equal to $d_j^{i+1}$ for each $j$, if it is not, none of $d_j$ should change. Hence, $TS(i, p, \langle d_j \rangle) = \min[TS(i+1, p+1, \langle d_j^{i+1} \rangle) \cup \{u_{i+1}\}, TS(i+1, p+|P \cap \{u_{i+1}\}|, \langle d_j \rangle)]$.

Since $0 \le d_j \le dg(v_j)$ for any $j$, the $TS$ table has $O^*((t+1)^{|Z|})$ fields. Each field of the table is evaluated in polynomial time. So the desired $B'$ is found (hence, the solution is found) in $O^*((t+1)^{|Z|})$ time for any branch fixed in stage II. Stages II and III together run in $2^{\omega_t|F|} \cdot (t+1)^{|Z|} \cdot 2^{(t-1)|Z|} \cdot (t+1)^{|Z|} \cdot n^{O(1)}$ time for any fixed subbranch of stage I.

Actually, the $(t+1)^{2|Z|}$ multiplier in the upper bound can be improved. Recall that it corresponds to the number of possible variants of $dg(v_j)$ and the number of possible variants of $d_j$. However, note that $d_j \le dg(v_j)$. So after each of $dg(v_j)$ is fixed in stage II, for $d_j$ there is only $dg(v_j) + 1$ options in stage III. Hence, each of the pairs $(d_j, dg(v_j))$ can be presented only in $\binom{t+2}{2}$ variants. This gives an improvement of the $(t+1)^{2|Z|}$ multiplier to a $\binom{t+2}{2}$ multiplier. So, the upper bound on the running time in stages II and III becomes $O^*\left(2^{\omega_t|F|} \cdot \binom{t+2}{2}^{|Z|} \cdot 2^{(t-1)|Z|}\right)$.

We rewrite this upper bound in terms of $n$ and $|F|$. Since $|Z| \le n - |F|$, the upper bound is

$$2^{\omega_t|F|} \cdot \binom{t+2}{2}^{n-|F|} \cdot 2^{(t-1)(n-|F|)} \cdot n^{O(1)}.$$

Now we are ready to choose $\gamma$. We set the value of $\gamma$ so that computation in each branch created at the end of stage I takes at most $O^*(2^{\gamma n})$ time. Note that the upper bound on the running time required for stages II and III increases while the value of $|F|$ decreases. So we can find $\gamma$ as the solution of equation $2^{\gamma n} = 2^{\omega_t \gamma n} \cdot \binom{t+2}{2}^{(1-\gamma)n} \cdot 2^{(t-1)(1-\gamma)n}$. Hence, $\gamma = \frac{(t-1)+\log_2\binom{t+2}{2}}{(t-\omega_t)+\log_2\binom{t+2}{2}} < 1$, as $\omega_t < 1$. So the overall running time is

$$2^{\gamma n} (2^{t+1} - t - 1)^{\frac{(1-\gamma)n}{t+1}} \cdot n^{O(1)},$$

which is $O^*((2 - \epsilon_t)^n)$ for some $\epsilon_t > 0$ since $\gamma < 1$.

## 3.2 Two algorithms for constant thresholds in the perfect case

Here, we present two algorithms for special cases of PERFECT TARGET SET SELECTION with thresholds being at most two or three. These algorithms use the idea that cannot be used in the general case of TARGET SET SELECTION, so the running times of these algorithms are significantly faster than the running time of the algorithm from the previous subsection. We provide their full descriptions in the full version of our paper.

**Theorem 5.** PERFECT TARGET SET SELECTION with thresholds being at most two can be solved in $O^*(1.90345^n)$ time.
the desired value of $B'$ will be stored as

$$TS(0, 0, \min\{|N(v_1) \cap (A' \setminus A)|, \mathrm{thr}(v_1)\}, \dots, \min\{|N(v_z) \cap (A' \setminus A)|, \mathrm{thr}(v_z)\}).$$

We assign $TS(f', p, dg(v_1), dg(v_2), \dots, dg(v_z)) = \emptyset$ for every $p$ such that $p + |P \cap (V(G) \setminus F')| \ge \ell$. We do this since values $p, dg(v_1), dg(v_2), \dots, dg(v_z)$ indicate that $A' \sqcup B'_1$ is already a solution. In all other fields of type $TS(f', \dots, \dots, \dots)$ we put the value of $V(G)$. We now show how to evaluate values $TS(i, p, d_1, d_2, \dots, d_z)$ for any $i \ge 0$ smaller than $f'$. We can evaluate any $TS(i, \dots, \dots, \dots, \dots)$ in polynomial time if we have all values $TS(i+1, \dots, \dots, \dots)$ evaluated. For each $j \in \{1, 2, \dots, z\}$, let $d_j^{i+1} = \min\{\mathrm{thr}(v_j), d_j + |N(v_j) \cap \{u_{i+1}\}|\}$. In order to compute $TS(i, p, d_1, d_2, \dots, d_z)$, we need to decide whether $u_{i+1}$ is in a target set or not. If $u_{i+1}$ is taken into $B'$ then $d_j$ becomes equal to $d_j^{i+1}$ for each $j$, if it is not, none of $d_j$ should change. Hence, $TS(i, p, \langle d_j \rangle) = \min[TS(i+1, p+1, \langle d_j^{i+1} \rangle) \cup \{u_{i+1}\}, TS(i+1, p+|P \cap \{u_{i+1}\}|, \langle d_j \rangle)]$.

Since $0 \le d_j \le dg(v_j)$ for any $j$, the $TS$ table has $O^*((t+1)^{|Z|})$ fields. Each field of the table is evaluated in polynomial time. So the desired $B'$ is found (hence, the solution is found) in $O^*((t+1)^{|Z|})$ time for any branch fixed in stage II. Stages II and III together run in $2^{\omega_t|F|} \cdot (t+1)^{|Z|} \cdot 2^{(t-1)|Z|} \cdot (t+1)^{|Z|} \cdot n^{O(1)}$ time for any fixed subbranch of stage I.

Actually, the $(t+1)^{2|Z|}$ multiplier in the upper bound can be improved. Recall that it corresponds to the number of possible variants of $dg(v_j)$ and the number of possible variants of $d_j$. However, note that $d_j \le dg(v_j)$. So after each of $dg(v_j)$ is fixed in stage II, for $d_j$ there is only $dg(v_j) + 1$ options in stage III. Hence, each of the pairs $(d_j, dg(v_j))$ can be presented only in $\binom{t+2}{2}$ variants. This gives an improvement of the $(t+1)^{2|Z|}$ multiplier to a $\binom{t+2}{2}^{|Z|}$ multiplier. So, the upper bound on the running time in stages II and III becomes $O^*\left(2^{\omega_t|F|} \cdot \binom{t+2}{2}^{|Z|} \cdot 2^{(t-1)|Z|}\right)$.

We rewrite this upper bound in terms of $n$ and $|F|$. Since $|Z| \le n - |F|$, the upper bound is

$$2^{\omega_t|F|} \cdot \binom{t+2}{2}^{n-|F|} \cdot 2^{(t-1)(n-|F|)} \cdot n^{O(1)}.$$

Now we are ready to choose $\gamma$. We set the value of $\gamma$ so that computation in each branch created at the end of stage I takes at most $O^*(2^{\gamma n})$ time. Note that the upper bound on the running time required for stages II and III increases while the value of $|F|$ decreases. So we can find $\gamma$ as the solution of equation $2^{\gamma n} = 2^{\omega_t \gamma n} \cdot \binom{t+2}{2}^{(1-\gamma)n} \cdot 2^{(t-1)(1-\gamma)n}$. Hence, $\gamma = \frac{(t-1)+\log_2\left(\binom{t+2}{2}\right)}{(t-\omega_t)+\log_2\left(\binom{t+2}{2}\right)} < 1$, as $\omega_t < 1$. So the overall running time is

$$2^{\gamma n} (2^{t+1} - t - 1)^{\frac{(1-\gamma)n}{t+1}} \cdot n^{O(1)},$$

which is $O^*((2 - \epsilon_t)^n)$ for some $\epsilon_t > 0$ since $\gamma < 1$.

## 3.2 Two algorithms for constant thresholds in the perfect case

Here, we present two algorithms for special cases of PERFECT TARGET SET SELECTION with thresholds being at most two or three. These algorithms use the idea that cannot be used in the general case of TARGET SET SELECTION, so the running times of these algorithms are significantly faster than the running time of the algorithm from the previous subsection. We provide their full descriptions in the full version of our paper.

**Theorem 5.** PERFECT TARGET SET SELECTION with thresholds being at most two can be solved in $O^*(1.90345^n)$ time.
**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