8:12 Parameterized Complexity of Multi-Node Hubs

2. If there exists a damaged vertex $v$ such that the connected component $C$ of $H(A, f)$ containing $v$ is huge, then at least one of the following conditions holds.

a. $H(A, f)$ has a huge connected component $C'$ such that $V(C') \cap (U^* \cap A) \neq \emptyset$.

b. $H(A, f)$ has no connected component that contains a damaged vertex and is not huge.

3. For all $\{v, u\} \in P^*$, either $H(A, f)$ has a connected component containing both $v$ and $u$ or each of its connected components containing $v$ or $u$ is huge.

4. $q = |A \setminus U^*| + \sum_{U \in \mathcal{U}} g(U)$.

Each $q$-valid triple is a potential solution for SINGLE BAG. The first three conditions are related to the connectivity demand of a solution to MNH, and the fourth to the size demand. The value of a $q$-valid triple $(A, f, g)$ is

$$W(A, f, g) = |E(A, V(H) \setminus A) \setminus E(U^* \cap A, U^* \setminus A)| + \sum_{U \in \mathcal{U}} \text{cut}(U, A \cap U, f(U), g(U)).$$

Informally, $W(A, f, g)$ is the sum of the number of edges between vertices in $A$ and vertices outside $A$ (excluding edges with both endpoints in $U^*$), to which we add the sum of the values of previously computed solutions.

**Goal.** For each $q \in \{\max\{0, k - \text{size}(U^*) - |U^* \cap T|\}, \dots, \min\{tSize - \text{size}(U^*) - |U^*|, k - |U^* \cap T|\}\}$, we need to compute the maximum value $W_q$ for which there exists a $q$-valid triple $(A, f, g)$ such that $W_q = W(A, f, g)$. In case $W_q$ is not defined, since there does not exist a $q$-valid tuple, we set $W_q = -\infty$.

The following observation bounds the number of damaged sets in $\mathcal{U}$ and the number of damaged vertices corresponding to a $q$-valid triple. The main intuition is that if the current bag has several children then the size of the graph (which is less than $k+p$) forces a solution to select all vertices of all the subgraphs induced by the children, except $p$ of them. This observation is used to allow us to apply the color coding method efficiently. Due to lack of space, the proof is omitted.

**Observation 10.** If $(A, f, g)$ is a $q$-valid triple such that $W_q = W(A, f, g)$, then

- $|V(H) \setminus A| \le p$ and $(A, f, g)$ damages at most $2p^2$ sets in $\mathcal{U}$,

- $(A, f, g)$ damages at most $2p^2 \cdot (2^{cp} + 1)$ vertices, and

- $g(U) \ge \text{size}(U) - p$ for all $U \in \mathcal{U}$.

5 Conclusion

In this paper, we initiated the study of multi-node hubs in general, and of algorithmic aspects of MNH in particular. The concept of multi-node hubs is a natural generalization of the concept of hubs, therefore it might play a central role in the analysis of complex networks. We showed that although MNH is W[1]-hard parameterized by $k$, it is FPT parameterized by $p$. Our algorithm is primarily a classification result and should be viewed as a proof of concept that the problem is FPT. While our approach may lead to an algorithm with running time $O^*(2^{p^{O(1)}})$ (or even $O^*(2^{O(p \log p)})$), developing an algorithm with running time $O^*(2^{O(p)})$ seems challenging. It may also be interesting to consider other natural restrictions on the set $A$ such as properties expressible in monadic second order logic, or to study MNH with respect to parameters other than $k$ and $p$.

To the best of our knowledge, besides our algorithm, only algorithms for BISECTION and a problem called JUDICIOUS PARTITION [32] are based on the decomposition of [15]. Exploring the power of this decomposition more deeply might be fruitful; in this context, it is noteworthy to mention [31]. In our application, we showed how an instance of a maximization problem
8:12 Parameterized Complexity of Multi-Node Hubs

2. If there exists a damaged vertex $v$ such that the connected component $C$ of $H(A, f)$ containing $v$ is huge, then at least one of the following conditions holds.

a. $H(A, f)$ has a huge connected component $C'$ such that $V(C') \cap (U^* \cap A) \neq \emptyset$.

b. $H(A, f)$ has no connected component that contains a damaged vertex and is not huge.

3. For all $\{v, u\} \in P^*$, either $H(A, f)$ has a connected component containing both $v$ and $u$ or each of its connected components containing $v$ or $u$ is huge.

4. $q = |A \setminus U^*| + \sum_{U \in \mathcal{U}} g(U)$.

Each $q$-valid triple is a potential solution for SINGLE BAG. The first three conditions are related to the connectivity demand of a solution to MNH, and the fourth to the size demand. The value of a $q$-valid triple $(A, f, g)$ is

$$W(A, f, g) = |E(A, V(H) \setminus A) \setminus E(U^* \cap A, U^* \setminus A)| + \sum_{U \in \mathcal{U}} \text{cut}(U, A \cap U, f(U), g(U)).$$

Informally, $W(A, f, g)$ is the sum of the number of edges between vertices in $A$ and vertices outside $A$ (excluding edges with both endpoints in $U^*$), to which we add the sum of the values of previously computed solutions.

**Goal.** For each $q \in \{\max\{0, k - \text{size}(U^*) - |U^* \cap T|\}, \dots, \min\{tSize - \text{size}(U^*) - |U^*|, k - |U^* \cap T|\}\}$, we need to compute the maximum value $W_q$ for which there exists a $q$-valid triple $(A, f, g)$ such that $W_q = W(A, f, g)$. In case $W_q$ is not defined, since there does not exist a $q$-valid tuple, we set $W_q = -\infty$.

The following observation bounds the number of damaged sets in $\mathcal{U}$ and the number of damaged vertices corresponding to a $q$-valid triple. The main intuition is that if the current bag has several children then the size of the graph (which is less than $k+p$) forces a solution to select all vertices of all the subgraphs induced by the children, except $p$ of them. This observation is used to allow us to apply the color coding method efficiently. Due to lack of space, the proof is omitted.

**Observation 10.** If $(A, f, g)$ is a $q$-valid triple such that $W_q = W(A, f, g)$, then

- $|V(H) \setminus A| \le p$ and $(A, f, g)$ damages at most $2p^2$ sets in $\mathcal{U}$,

- $(A, f, g)$ damages at most $2p^2 \cdot (2^{cp} + 1)$ vertices, and

- $g(U) \ge \text{size}(U) - p$ for all $U \in \mathcal{U}$.

5 Conclusion

In this paper, we initiated the study of multi-node hubs in general, and of algorithmic aspects of MNH in particular. The concept of multi-node hubs is a natural generalization of the concept of hubs, therefore it might play a central role in the analysis of complex networks. We showed that although MNH is W[1]-hard parameterized by $k$, it is FPT parameterized by $p$. Our algorithm is primarily a classification result and should be viewed as a proof of concept that the problem is FPT. While our approach may lead to an algorithm with running time $O^*(2^{p^{O(1)}})$ (or even $O^*(2^{O(p \log p)})$), developing an algorithm with running time $O^*(2^{O(p)})$ seems challenging. It may also be interesting to consider other natural restrictions on the set $A$ such as properties expressible in monadic second order logic, or to study MNH with respect to parameters other than $k$ and $p$.

To the best of our knowledge, besides our algorithm, only algorithms for BISECTION and a problem called JUDICIOUS PARTITION [32] are based on the decomposition of [15]. Exploring the power of this decomposition more deeply might be fruitful; in this context, it is noteworthy to mention [31]. In our application, we showed how an instance of a maximization problem
can be preprocessed to a form that enables using known tools to solve cut-problems and in particular the decomposition of [15], as well as a manner in which connectivity constraints can be handled on top of cut and size constraints. We believe that our approach can be relevant to the design of algorithms for other cut-problems of this nature.

References

1 L A Adamic, R M Lukose, A R Puniyani, and B A Huberman. Search in power-law networks. CoRR cs.NI/0103016, 2001.

2 A A Ageev and M Sviridenko. Approximation algorithms formaximum coverage andmax cutwith given sizes of parts. In IPCO, pages 17–30, 1999.

3 N Alon, R Yuster, and U Zwick. Color coding. J. ACM, 42(4):844–856, 1995.

4 D Balcan, H Hu, B Goncalves, P Bajardi, C Poletto, J J Ramasco, D Paolotti, N Perra, M Tizzoni, W Van den Broeck, V Colizza, and A Vespignani. Seasonal transmission potential and activity peaks of the new influenza A(H1N1): a Monte Carlo likelihood analysis based on human mobility. BMC Medicine, 7(45):29, 2009.

5 A Barabasi and R Albert. Emergence of scaling in random networks. Science, 286:509, 1999.

6 M Berlingerio, M Coscia, F Giannotti, A Monreale, and D Pedreschi. The pursuit of hubbiness: Analysis of hubs in large multidimensional networks. J. Comput. Science, 2:223–237, 2011.

7 D Binkele-Raible. Amortized analysis of exponential time and parameterized algorithms: Measure and conquer and reference search trees. PhD Thesis, University of Trier, 2009.

8 E Bonnet, B Escoffier, V T Paschos, and E Tourniaire. Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization. Algorithmica, 71(3):566–580, 2015.

9 L Cai. Parameter complexity of cardinality constrained optimization problems. Comput. J., 51(1):102–121, 2008.

10 R H Chitnis, M Cygan, M T Hajiaghayi, M Pilipczuk, and M Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. In FOCS, pages 460–469, 2012.

11 R H Chitnis, M Cygan, M T Hajiaghayi, M Pilipczuk, and M Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. In http://arxiv.org/pdf/1207.4079v1.pdf, 2012.

12 R Crowston, G Gutin, M Jones, and G Muciaccia. Maximum balanced subgraph problem parameterized above lower bound. Theor. Comput. Sci., 513:53–64, 2013.

13 R Crowston, M Jones, and M Mnich. Max-Cut Parameterized Above the Edwards-Erdős Bound. Algorithmica, 72(3):734–757, 2015.

14 M Cygan. Deterministic parameterized connected vertex cover. In SWAT, pages 95–106, 2012.

15 M Cygan, D Lokshtanov, M Pilipczuk, M Pilipczuk, and S Saurabh. Minimum bisection is fixed parameter tractable. In STOC, pages 323–332, 2014.

16 M Cygan, J Nederlof, M Pilipczuk, M Pilipczuk, J M M van Rooij, and J O Wojtaszczyk. Deterministic parameterized connected vertex cover. In FOCS, pages 150–159, 2012.

17 U Feige and M Langberg. Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms, 41(2):174–211, 2001.

18 H Fernau and D Manlove. Vertex and edge covers with clustering properties: Complexity and algorithms. J. Discrete Algorithms, 7(2):149–167, 2009.

19 D W Franks, J Noble, P Kaufmann, and S Stagl. Extremism propagation in social networks with hubs. Adaptive Behavior – Animals, Animats, Software Agents, Robots, Adaptive Systems, 16:264–274, 2008.
can be preprocessed to a form that enables using known tools to solve cut-problems and in particular the decomposition of [15], as well as a manner in which connectivity constraints can be handled on top of cut and size constraints. We believe that our approach can be relevant to the design of algorithms for other cut-problems of this nature.

References

1 L A Adamic, R M Lukose, A R Puniyani, and B A Huberman. Search in power-law networks. CoRR cs.NI/0103016, 2001.

2 A A Ageev and M Sviridenko. Approximation algorithms formaximum coverage andmax cutwith given sizes of parts. In IPCO, pages 17–30, 1999.

3 N Alon, R Yuster, and U Zwick. Color coding. J. ACM, 42(4):844–856, 1995.

4 D Balcan, H Hu, B Goncalves, P Bajardi, C Poletto, J J Ramasco, D Paolotti, N Perra, M Tizzoni, W Van den Broeck, V Colizza, and A Vespignani. Seasonal transmission potential and activity peaks of the new influenza A(H1N1): a Monte Carlo likelihood analysis based on human mobility. BMC Medicine, 7(45):29, 2009.

5 A Barabasi and R Albert. Emergence of scaling in random networks. Science, 286:509, 1999.

6 M Berlingerio, M Coscia, F Giannotti, A Monreale, and D Pedreschi. The pursuit of hubbiness: Analysis of hubs in large multidimensional networks. J. Comput. Science, 2:223–237, 2011.

7 D Binkele-Raible. Amortized analysis of exponential time and parameterized algorithms: Measure and conquer and reference search trees. PhD Thesis, University of Trier, 2009.

8 E Bonnet, B Escoffier, V T Paschos, and E Tourniaire. Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization. Algorithmica, 71(3):566–580, 2015.

9 L Cai. Parameter complexity of cardinality constrained optimization problems. Comput. J., 51(1):102–121, 2008.

10 R H Chitnis, M Cygan, M T Hajiaghayi, M Pilipczuk, and M Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. In FOCS, pages 460–469, 2012.

11 R H Chitnis, M Cygan, M T Hajiaghayi, M Pilipczuk, and M Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. In http://arxiv.org/pdf/1207.4079v1.pdf, 2012.

12 R Crowston, G Gutin, M Jones, and G Muciaccia. Maximum balanced subgraph problem parameterized above lower bound. Theor. Comput. Sci., 513:53–64, 2013.

13 R Crowston, M Jones, and M Mnich. Max-Cut Parameterized Above the Edwards-Erdős Bound. Algorithmica, 72(3):734–757, 2015.

14 M Cygan. Deterministic parameterized connected vertex cover. In SWAT, pages 95–106, 2012.

15 M Cygan, D Lokshtanov, M Pilipczuk, M Pilipczuk, and S Saurabh. Minimum bisection is fixed parameter tractable. In STOC, pages 323–332, 2014.

16 M Cygan, J Nederlof, M Pilipczuk, M Pilipczuk, J M M van Rooij, and J O Wojtaszczyk. Deterministic parameterized connected vertex cover. In FOCS, pages 150–159, 2012.

17 U Feige and M Langberg. Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms, 41(2):174–211, 2001.

18 H Fernau and D Manlove. Vertex and edge covers with clustering properties: Complexity and algorithms. J. Discrete Algorithms, 7(2):149–167, 2009.

19 D W Franks, J Noble, P Kaufmann, and S Stagl. Extremism propagation in social networks with hubs. Adaptive Behavior – Animals, Animats, Software Agents, Robots, Adaptive Systems, 16:264–274, 2008.
20 M X Goemans and D P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. *J. ACM*, 42(6):1115–1145, 1995.

21 P Goymer. Network biology: Why do we need hubs? *Nature Reviews Genetics*, 9:650–651, 2008.

22 J Guo, R Niedermeier, and S Wernicke. Parameterized complexity of generalized vertex cover problems. In *WADS*, pages 36–48, 2005.

23 M T Hajiaghayi, G Kortsarz, R MacDavid, M Purohit, and K K Sarpatwar. Approximation algorithms for connected maximum cut and related problems. In *ESA*, pages 693–704, 2015.

24 X He and J Zhang. Why Do Hubs Tend to Be Essential in Protein Networks? *PLOS Genetics*, 2(6):e88, 2006.

25 H Jeong, B Tombor, R Albert, Z N Oltvai, and A L Barabasi. The large-scale organization of metabolic networks. *Nature*, 407:651–654, 2000.

26 S Khot, G Kindler, E Mossel, and R O'Donnell. Optimization, approximation, and complexity classes. *SICOMP*, 37(1):319–357, 2007.

27 J M Kleinberg. Authoritative sources in a hyperlinked environment. *J. ACM*, 46:604–632, 1999.

28 J Kneis, A Langer, and P Rossmanith. A new algorithm for finding trees with many leaves. *Algorithmica*, 61:882–897, 2011.

29 J Lee, V Nagarajan, and X Shen. Max-Cut Under Graph Constraints. In *IPCO*, pages 50–62, 2016.

30 J Leskovec, L A Adamic, and Huberman B A. The dynamics of viral marketing. In *EC*, pages 228–237, 2006.

31 D Lokshtanov, M S Ramanujan, S Saurabh, and M Zehavi. Reducing CMSO Model Checking to Highly Connected Graphs. In *ICALP*, pages 135:1–135:14, 2018.

32 D Lokshtanov, S Saurabh, R Sharma, and M Zehavi. Balanced Judicious Bipartition is Fixed-Parameter Tractable. In *FSTTCS*, pages 40:40–40:15, 2017.

33 X Lu, V J Vipul, P W Finn, and D L Perkins. Hubs in biological interaction networks exhibit low changes in expression in experimental asthma. *Molecular Systems Biology*, 3(98), 2008.

34 M Mahajan and V Raman. Parameterizing above Guaranteed Values: MaxSat and MaxCut. *J. Algorithms*, 31(2):335–354, 1999.

35 A S Maiya and T Y Berger-Wolf. Online sampling of high centrality individuals in social networks. In *PAKDD*, pages 91–98, 2010.

36 D Molle, S Richter, and P Rossmanith. Enumerate and expand: Improved algorithms for connected vertex cover and tree cover. *Theory Comput. Syst.*, 43(2):234–253, 2008.

37 C H Papadimitriou and M Yannakakis. Optimization, approximation, and complexity classes. *J. Comput. Syst. Sci.*, 43(3):425–440, 1991.

38 V Raman and S Saurabh. Improved fixed parameter tractable algorithms for two "edge" problems: MAXCUT and MAXDAG. *Inf. Process. Lett.*, 104(2):65–72, 2007.

39 S Saurabh and M Zehavi. $(k, n-k)$-Max-Cut: an $O^*(2^p)$-time algorithm and a polynomial kernel. In *LATIN*, pages 686–699, 2016.

40 H Shachnai and M Zehavi. Parameterized algorithms for graph partitioning problems. In *WG*, pages 384–395, 2014.

41 X Shi, B Tseng, and L Adamic. Looking at the Blogosphere Topology through Different Lenses. In *ICWSM*, 2007.

42 S Vicente, V Kolmogorov, and C Rother. Graph cut based image segmentation with connectivity priors. In *CVPR*, pages 1–8, 2008.
20 M X Goemans and D P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. *J. ACM*, 42(6):1115–1145, 1995.

21 P Goymer. Network biology: Why do we need hubs? *Nature Reviews Genetics*, 9:650–651, 2008.

22 J Guo, R Niedermeier, and S Wernicke. Parameterized complexity of generalized vertex cover problems. In *WADS*, pages 36–48, 2005.

23 M T Hajiaghayi, G Kortsarz, R MacDavid, M Purohit, and K K Sarpatwar. Approximation algorithms for connected maximum cut and related problems. In *ESA*, pages 693–704, 2015.

24 X He and J Zhang. Why Do Hubs Tend to Be Essential in Protein Networks? *PLOS Genetics*, 2(6):e88, 2006.

25 H Jeong, B Tombor, R Albert, Z N Oltvai, and A L Barabasi. The large-scale organization of metabolic networks. *Nature*, 407:651–654, 2000.

26 S Khot, G Kindler, E Mossel, and R O'Donnell. Optimization, approximation, and complexity classes. *SICOMP*, 37(1):319–357, 2007.

27 J M Kleinberg. Authoritative sources in a hyperlinked environment. *J. ACM*, 46:604–632, 1999.

28 J Kneis, A Langer, and P Rossmanith. A new algorithm for finding trees with many leaves. *Algorithmica*, 61:882–897, 2011.

29 J Lee, V Nagarajan, and X Shen. Max-Cut Under Graph Constraints. In *IPCO*, pages 50–62, 2016.

30 J Leskovec, L A Adamic, and Huberman B A. The dynamics of viral marketing. In *EC*, pages 228–237, 2006.

31 D Lokshtanov, M S Ramanujan, S Saurabh, and M Zehavi. Reducing CMSO Model Checking to Highly Connected Graphs. In *ICALP*, pages 135:1–135:14, 2018.

32 D Lokshtanov, S Saurabh, R Sharma, and M Zehavi. Balanced Judicious Bipartition is Fixed-Parameter Tractable. In *FSTTCS*, pages 40:40–40:15, 2017.

33 X Lu, V J Vipul, P W Finn, and D L Perkins. Hubs in biological interaction networks exhibit low changes in expression in experimental asthma. *Molecular Systems Biology*, 3(98), 2008.

34 M Mahajan and V Raman. Parameterizing above Guaranteed Values: MaxSat and MaxCut. *J. Algorithms*, 31(2):335–354, 1999.

35 A S Maiya and T Y Berger-Wolf. Online sampling of high centrality individuals in social networks. In *PAKDD*, pages 91–98, 2010.

36 D Molle, S Richter, and P Rossmanith. Enumerate and expand: Improved algorithms for connected vertex cover and tree cover. *Theory Comput. Syst.*, 43(2):234–253, 2008.

37 C H Papadimitriou and M Yannakakis. Optimization, approximation, and complexity classes. *J. Comput. Syst. Sci.*, 43(3):425–440, 1991.

38 V Raman and S Saurabh. Improved fixed parameter tractable algorithms for two "edge" problems: MAXCUT and MAXDAG. *Inf. Process. Lett.*, 104(2):65–72, 2007.

39 S Saurabh and M Zehavi. $(k, n-k)$-Max-Cut: an $O^*(2^p)$-time algorithm and a polynomial kernel. In *LATIN*, pages 686–699, 2016.

40 H Shachnai and M Zehavi. Parameterized algorithms for graph partitioning problems. In *WG*, pages 384–395, 2014.

41 X Shi, B Tseng, and L Adamic. Looking at the Blogosphere Topology through Different Lenses. In *ICWSM*, 2007.

42 S Vicente, V Kolmogorov, and C Rother. Graph cut based image segmentation with connectivity priors. In *CVPR*, pages 1–8, 2008.
# The Parameterised Complexity of Computing the Maximum Modularity of a Graph

Kitty Meeks<fnref n="1" />

School of Computing Science, University of Glasgow, Glasgow, UK
kitty.meeks@glasgow.ac.uk

Fiona Skerman<fnref n="2" />

Department of Mathematics, Uppsala University, Uppsala, Sweden
fiona.skerman@math.uu.se

**Abstract**

The *maximum modularity* of a graph is a parameter widely used to describe the level of clustering or community structure in a network. Determining the maximum modularity of a graph is known to be NP-complete in general, and in practice a range of heuristics are used to construct partitions of the vertex-set which give lower bounds on the maximum modularity but without any guarantee on how close these bounds are to the true maximum. In this paper we investigate the parameterised complexity of determining the maximum modularity with respect to various standard structural parameterisations of the input graph *G*. We show that the problem belongs to FPT when parameterised by the size of a minimum vertex cover for *G*, and is solvable in polynomial time whenever the treewidth or max leaf number of *G* is bounded by some fixed constant; we also obtain an FPT algorithm, parameterised by treewidth, to compute any constant-factor approximation to the maximum modularity. On the other hand we show that the problem is W[1]-hard (and hence unlikely to admit an FPT algorithm) when parameterised simultaneously by pathwidth and the size of a minimum feedback vertex set.

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

**Keywords and phrases** modularity, community detection, integer quadratic programming, vertex cover, pathwidth

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

**Acknowledgements** The authors are grateful to Jessica Enright for some helpful initial discussions about the topic.

## 1 Introduction

The increasing availability of large network datasets has led to great interest in techniques to discover network structure. An important and frequently observed structure in networks is the existence of groups of vertices with many connections between them, often referred to as ‘communities’.

Newman and Girvan introduced the modularity function in 2004 [22]. Modularity gives a measure of how well a graph can be divided into communities and is used in the most

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

<footnote n="1">¹ KM is supported by a Royal Society of Edinburgh Personal Research Fellowship, funded by the Scottish Government.</footnote>

<footnote n="2">² FS is supported by grants from Swedish Research Council and the Ragnar Söderberg Foundation. Research partially conducted while at the Heilbronn Institute for Mathematical Research, Bristol.</footnote>
# The Parameterised Complexity of Computing the Maximum Modularity of a Graph

Kitty Meeks<fnref n="1" />

School of Computing Science, University of Glasgow, Glasgow, UK
kitty.meeks@glasgow.ac.uk

Fiona Skerman<fnref n="2" />

Department of Mathematics, Uppsala University, Uppsala, Sweden
fiona.skerman@math.uu.se

**Abstract**

The *maximum modularity* of a graph is a parameter widely used to describe the level of clustering or community structure in a network. Determining the maximum modularity of a graph is known to be NP-complete in general, and in practice a range of heuristics are used to construct partitions of the vertex-set which give lower bounds on the maximum modularity but without any guarantee on how close these bounds are to the true maximum. In this paper we investigate the parameterised complexity of determining the maximum modularity with respect to various standard structural parameterisations of the input graph *G*. We show that the problem belongs to FPT when parameterised by the size of a minimum vertex cover for *G*, and is solvable in polynomial time whenever the treewidth or max leaf number of *G* is bounded by some fixed constant; we also obtain an FPT algorithm, parameterised by treewidth, to compute any constant-factor approximation to the maximum modularity. On the other hand we show that the problem is W[1]-hard (and hence unlikely to admit an FPT algorithm) when parameterised simultaneously by pathwidth and the size of a minimum feedback vertex set.

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

**Keywords and phrases** modularity, community detection, integer quadratic programming, vertex cover, pathwidth

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

**Acknowledgements** The authors are grateful to Jessica Enright for some helpful initial discussions about the topic.

## 1 Introduction

The increasing availability of large network datasets has led to great interest in techniques to discover network structure. An important and frequently observed structure in networks is the existence of groups of vertices with many connections between them, often referred to as ‘communities’.

Newman and Girvan introduced the modularity function in 2004 [22]. Modularity gives a measure of how well a graph can be divided into communities and is used in the most

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

<footnote n="1">¹ KM is supported by a Royal Society of Edinburgh Personal Research Fellowship, funded by the Scottish Government.</footnote>

<footnote n="2">² FS is supported by grants from Swedish Research Council and the Ragnar Söderberg Foundation. Research partially conducted while at the Heilbronn Institute for Mathematical Research, Bristol.</footnote>
popular algorithms to cluster large networks. For example, the Louvain method, an iterative clustering technique, uses the modularity function to choose which parts from the previous step to fuse into larger parts at each step [2, 15]. The widespread use of modularity and empirical success in finding communities makes modularity an important function to study from an algorithmic point of view.

In this paper we are concerned with the computational complexity of computing the maximum modularity of a given input graph, and specifically in the following decision problem.

### MODULARITY

*Input:* A graph $G$ and a constant $q \in [0, 1]$.

*Question:* Is the maximum modularity of $G$ at least $q$?

This problem was shown to be NP-complete in general by Brandes et. al. [3], using a construction that relies on the fact that all vertices of a sufficiently large clique must be assigned to the same part of an optimal partition. They also showed that a variation of the problem in which we wish to find the optimal partition into exactly two sets is hard; their proof for this relied again on the use of large cliques, but DasGupta and Desai [5] later showed that this 2-clustering problem remains NP-complete on $d$-regular graphs for any fixed $d \ge 9$. It has also been shown that it is NP-hard to approximate the maximum modularity within any constant factor [7], although there is a polynomial-time constant-factor approximation algorithm for certain families of scale-free networks [9]. The hardness of computing constant-factor multiplicative approximations in general has motivated research into approximation algorithms with an additive error [7, 16]: the best known result is an approximation algorithm with additive error roughly 0.42084 [16].

In this paper we initiate the study of the parameterised complexity of MODULARITY, considering its complexity with respect to several standard structural parameterisations. On the positive side, we show that the problem is in FPT when parameterised by the cardinality of a minimum vertex cover for the input graph $G$, and that it belongs to XP when parameterised by either the treewidth or max leaf number of $G$. The XP algorithm parameterised by treewidth can easily be adapted to give an FPT algorithm, parameterised by treewidth, to compute any constant-factor approximation maximum modularity. On the other hand, we demonstrate that MODULARITY, parameterised by treewidth, is unlikely to belong to FPT: we prove that the problem is W[1]-hard even when parameterised simultaneously by the pathwidth of $G$ and the size of a minimum feedback vertex set for $G$. For background on parameterised complexity, and the complexity classes discussed here, we refer the reader to [4, 10].

These results follow the same pattern as those obtained for the problem EQUITABLE CONNECTED PARTITION [11], and indeed our hardness result involves a reduction from a specialisation of this problem. There are clear similarities between the two problems: in a partition that maximises the modularity, every part will induce a connected subgraph and, in certain circumstances, we achieve the maximum modularity with a partition into parts that are as equal as possible. However, the crucial difference between the two problems is that the input to EQUITABLE CONNECTED PARTITION includes the required number of parts, whereas MODULARITY requires us to maximise over all possible partition sizes; in fact, if we restrict to partitions with a specified parts, it is no longer necessarily true that a partition maximising the modularity must induce connected subgraphs. This difference makes reductions between the two problems non-trivial.
popular algorithms to cluster large networks. For example, the Louvain method, an iterative clustering technique, uses the modularity function to choose which parts from the previous step to fuse into larger parts at each step [2, 15]. The widespread use of modularity and empirical success in finding communities makes modularity an important function to study from an algorithmic point of view.

In this paper we are concerned with the computational complexity of computing the maximum modularity of a given input graph, and specifically in the following decision problem.

### MODULARITY

*Input:* A graph $G$ and a constant $q \in [0, 1]$.

*Question:* Is the maximum modularity of $G$ at least $q$?

This problem was shown to be NP-complete in general by Brandes et. al. [3], using a construction that relies on the fact that all vertices of a sufficiently large clique must be assigned to the same part of an optimal partition. They also showed that a variation of the problem in which we wish to find the optimal partition into exactly two sets is hard; their proof for this relied again on the use of large cliques, but DasGupta and Desai [5] later showed that this 2-clustering problem remains NP-complete on $d$-regular graphs for any fixed $d \ge 9$. It has also been shown that it is NP-hard to approximate the maximum modularity within any constant factor [7], although there is a polynomial-time constant-factor approximation algorithm for certain families of scale-free networks [9]. The hardness of computing constant-factor multiplicative approximations in general has motivated research into approximation algorithms with an additive error [7, 16]: the best known result is an approximation algorithm with additive error roughly 0.42084 [16].

In this paper we initiate the study of the parameterised complexity of MODULARITY, considering its complexity with respect to several standard structural parameterisations. On the positive side, we show that the problem is in FPT when parameterised by the cardinality of a minimum vertex cover for the input graph $G$, and that it belongs to XP when parameterised by either the treewidth or max leaf number of $G$. The XP algorithm parameterised by treewidth can easily be adapted to give an FPT algorithm, parameterised by treewidth, to compute any constant-factor approximation maximum modularity. On the other hand, we demonstrate that MODULARITY, parameterised by treewidth, is unlikely to belong to FPT: we prove that the problem is W[1]-hard even when parameterised simultaneously by the pathwidth of $G$ and the size of a minimum feedback vertex set for $G$. For background on parameterised complexity, and the complexity classes discussed here, we refer the reader to [4, 10].

These results follow the same pattern as those obtained for the problem EQUITABLE CONNECTED PARTITION [11], and indeed our hardness result involves a reduction from a specialisation of this problem. There are clear similarities between the two problems: in a partition that maximises the modularity, every part will induce a connected subgraph and, in certain circumstances, we achieve the maximum modularity with a partition into parts that are as equal as possible. However, the crucial difference between the two problems is that the input to EQUITABLE CONNECTED PARTITION includes the required number of parts, whereas MODULARITY requires us to maximise over all possible partition sizes; in fact, if we restrict to partitions with a specified parts, it is no longer necessarily true that a partition maximising the modularity must induce connected subgraphs. This difference makes reductions between the two problems non-trivial.
## 1.1 The modularity function

The definition of modularity was first introduced by Newman and Girvan in [22]. Many or indeed most popular algorithms used to search for clusterings on large datasets are based on finding partitions with high modularity [17, 14], and the heuristics within them sometimes also use local modularity optimisation, for example in the Louvain method [2]. See [23, 13] for surveys on community detection including modularity based methods.

Knowledge on the maximum modularity for classes of graphs helps to understand the behaviour of the modularity function. There is a growing literature on this which began with cycles and complete graphs in [3]. Bagrow [1] and Montgolfier et al. [6] showed some classes of trees have high maximum modularity which was extended in [19] to all trees with maximum degree $o(n)$, and furthermore to all graphs where the product of treewidth and maximum degree grows more slowly than the number of edges. Many random graph models also have high modularity, see [20, 21] for a treatment of Erdős-Renyi random graphs, [19] for random regular graphs and also [24] which includes the preferential attachment model.

Given a set $A$ of vertices, let $e(A)$ denote the number of edges within $A$, and let $vol(A)$ (sometimes called the volume of $A$) denote the sum of the degree $d_v$ (in the whole graph $G$) over the vertices $v$ in $A$. For a graph $G$ with $m \ge 1$ edges and a vertex partition $\mathcal{A}$ of $G$, set the modularity of $\mathcal{A}$ on $G$ to be

$$q_{\mathcal{A}}(G) = \frac{1}{2m} \sum_{A \in \mathcal{A}} \sum_{u,v \in A} \left( \mathbf{1}_{uv \in E} - \frac{d_u d_v}{2m} \right) = \frac{1}{m} \sum_{A \in \mathcal{A}} e(A) - \frac{1}{4m^2} \sum_{A \in \mathcal{A}} \mathrm{vol}(A)^2$$

the maximum modularity of $G$ is $q^*(G) = \max_{\mathcal{A}}(G)$, where the maximum is over all partitions $\mathcal{A}$ of the vertices of $G$. Graphs with no edges are defined conventionally to have modularity 0.

The modularity function is designed to score partitions highly when most edges fall within the parts and penalise partitions with very few or very big parts. These two objectives are encoded as the edge contribution or coverage $q_{\mathcal{A}}^E(G) = \frac{1}{m} \sum_{A \in \mathcal{A}} e(A)$, and degree tax $q_{\mathcal{A}}^D(G) = \frac{1}{4m^2} \sum_{A \in \mathcal{A}} \mathrm{vol}(A)^2$, in the modularity of a vertex partition $\mathcal{A}$ of $G$.

Note that for any graph with $m \ge 1$ edges $0 \le q^*(G) < 1$. To see the lower bound, notice that the trivial partition which places all vertices in the same part has modularity zero. For example, complete graphs and stars have modularity 0 as noted in [3]. A graph consisting of $c$ disjoint cliques of the same size has modularity $1 - 1/c$ with the optimal partition taking each clique to be a part.

As modularity is at most 1 it is sometimes useful to consider the *modularity defect* $\tilde{q}_{\mathcal{A}}(G) = 1 - q_{\mathcal{A}}(G)$. Denote by $\partial(A)$ the number of edges between $A$ and the rest of the graph. Then

$$\tilde{q}_{\mathcal{A}}(G) = \frac{1}{2m} \sum_{A \in \mathcal{A}} \left( \partial(A) + \frac{\mathrm{vol}(A)^2}{2m} \right)$$

and we may equivalently minimise the modularity defect as maximise the modularity. In particular

$$\tilde{q}(G) = \min_{A \in \mathcal{A}} \tilde{q}_{\mathcal{A}}(G) = 1 - q^*(G).$$

We will make use of several facts about the maximum modularity of a graph.

**Fact 1.1 (Lemma 3.3 of [3]).** If $\mathcal{A}$ is a partition of $V(G)$ such that $q_{\mathcal{A}}(G) = q^*(G)$ then no part $A$ consists of a single vertex of degree 1.
## 1.1 The modularity function

The definition of modularity was first introduced by Newman and Girvan in [22]. Many or indeed most popular algorithms used to search for clusterings on large datasets are based on finding partitions with high modularity [17, 14], and the heuristics within them sometimes also use local modularity optimisation, for example in the Louvain method [2]. See [23, 13] for surveys on community detection including modularity based methods.

Knowledge on the maximum modularity for classes of graphs helps to understand the behaviour of the modularity function. There is a growing literature on this which began with cycles and complete graphs in [3]. Bagrow [1] and Montgolfier et al. [6] showed some classes of trees have high maximum modularity which was extended in [19] to all trees with maximum degree $o(n)$, and furthermore to all graphs where the product of treewidth and maximum degree grows more slowly than the number of edges. Many random graph models also have high modularity, see [20, 21] for a treatment of Erdős-Renyi random graphs, [19] for random regular graphs and also [24] which includes the preferential attachment model.

Given a set $A$ of vertices, let $e(A)$ denote the number of edges within $A$, and let $vol(A)$ (sometimes called the volume of $A$) denote the sum of the degree $d_v$ (in the whole graph $G$) over the vertices $v$ in $A$. For a graph $G$ with $m \ge 1$ edges and a vertex partition $\mathcal{A}$ of $G$, set the modularity of $\mathcal{A}$ on $G$ to be

$$q_{\mathcal{A}}(G) = \frac{1}{2m} \sum_{A \in \mathcal{A}} \sum_{u,v \in A} \left( \mathbf{1}_{uv \in E} - \frac{d_u d_v}{2m} \right) = \frac{1}{m} \sum_{A \in \mathcal{A}} e(A) - \frac{1}{4m^2} \sum_{A \in \mathcal{A}} \mathrm{vol}(A)^2;$$

the maximum modularity of $G$ is $q^*(G) = \max_{\mathcal{A}}(G)$, where the maximum is over all partitions $\mathcal{A}$ of the vertices of $G$. Graphs with no edges are defined conventionally to have modularity 0.

The modularity function is designed to score partitions highly when most edges fall within the parts and penalise partitions with very few or very big parts. These two objectives are encoded as the edge contribution or coverage $q_{\mathcal{A}}^E(G) = \frac{1}{m} \sum_{A \in \mathcal{A}} e(A)$, and degree tax $q_{\mathcal{A}}^D(G) = \frac{1}{4m^2} \sum_{A \in \mathcal{A}} \mathrm{vol}(A)^2$, in the modularity of a vertex partition $\mathcal{A}$ of $G$.

Note that for any graph with $m \ge 1$ edges $0 \le q^*(G) < 1$. To see the lower bound, notice that the trivial partition which places all vertices in the same part has modularity zero. For example, complete graphs and stars have modularity 0 as noted in [3]. A graph consisting of $c$ disjoint cliques of the same size has modularity $1 - 1/c$ with the optimal partition taking each clique to be a part.

As modularity is at most 1 it is sometimes useful to consider the *modularity defect* $\tilde{q}_{\mathcal{A}}(G) = 1 - q_{\mathcal{A}}(G)$. Denote by $\partial(A)$ the number of edges between $A$ and the rest of the graph. Then

$$\tilde{q}_{\mathcal{A}}(G) = \frac{1}{2m} \sum_{A \in \mathcal{A}} \left( \partial(A) + \frac{\mathrm{vol}(A)^2}{2m} \right)$$

and we may equivalently minimise the modularity defect as maximise the modularity. In particular

$$\tilde{q}(G) = \min_{A \in \mathcal{A}} \tilde{q}_{\mathcal{A}}(G) = 1 - q^*(G).$$

We will make use of several facts about the maximum modularity of a graph.

**Fact 1.1 (Lemma 3.3 of [3]).** If $\mathcal{A}$ is a partition of $V(G)$ such that $q_{\mathcal{A}}(G) = q^*(G)$ then no part $A$ consists of a single vertex of degree 1.
9:4 The Parameterised Complexity of Computing the Maximum Modularity of a Graph

► **Fact 1.2** (Lemma 3.4 of [3]). Suppose that $G$ is a graph that contains no isolated vertices. If $A$ is a partition of $V(G)$ such that $q_A(G) = q^*(G)$ then, for every $A \in A$, $G[A]$ is a connected subgraph of $G$.

► **Fact 1.3** (Corollary 1 of [3]). Let $G = (V, E)$ and suppose that $V_0 \subseteq V$ is a set of isolated vertices. Then $q(G) = q(G \setminus V_0)$. Moreover, if partitions $A$ and $A'$ agree on all vertices of $V \setminus V_0$, then $q_A(G) = q_{A'}(G)$.

► **Fact 1.4** (Lemma 1 of [8], Lemma 2.1 of [5]). For any integer $c > 0$ and any graph $G$,

$$ \max_{|A| \le c} q_A(G) > q^*(G) \left(1 - \frac{1}{c}\right). $$

1.2 Notation and definitions

Given a graph $G = (V, E)$, and a set $U \subseteq V$ of vertices, we write $G[U]$ for the subgraph of $G$ induced by $U$ and $G \setminus U$ for $G[V \setminus U]$. Given two disjoint subsets of vertices $A, B \subseteq V$, we write $e(A, B)$ for the number of edges with one endpoint in $A$ and the other in $B$. We shall often want to denote the number of edges between a set of vertices and the remainder of the graph so set $\partial(A) = e(A, \bar{A})$. If $\mathcal{P}$ is a partition of a set $X$, and $Y \subset X$, we write $\mathcal{P}[Y]$ for the restriction of $\mathcal{P}$ to $Y$.

A *vertex cover* of a graph $G = (V, E)$ is a set $U \subseteq V$ such that every edge has at least one endpoint in $U$; equivalently, $G \setminus U$ is an independent set (i.e. contains no edges). The *vertex cover number* of $G$ is the smallest cardinality of any vertex cover of $G$. A *feedback vertex set* for $G$ is a set $U \subseteq V$ such that $G \setminus U$ contains no cycles. Notice that the vertex cover number of $G$ gives an upper bound on the size of the smallest feedback vertex set for $G$, written $fvs(G)$. The *max leaf number* of $G$ is the maximum number of leaves (degree one vertices) in any spanning tree of $G$.

A *tree decomposition* of a graph $G$ is a pair $(T, \mathcal{D})$ where $T$ is a tree and $\mathcal{D} = \{\mathcal{D}(t) : t \in V(T)\}$ is a collection of non-empty subsets of $V(G)$ (or *bags*), indexed by the nodes of $T$, satisfying:

1. $V(G) = \bigcup_{t \in V(T)} \mathcal{D}(t)$,

2. for every $e = uv \in E(G)$, there exists $t \in V(T)$ such that $u, v \in \mathcal{D}(t)$,

3. for every $v \in V(G)$, if $T(v)$ is defined to be the subgraph of $T$ induced by nodes $t$ with $v \in \mathcal{D}(t)$, then $T(v)$ is connected.

If $T$ is in fact a path, we say that $(T, \mathcal{D})$ is a *path decomposition* of $G$. The *width* of the tree decomposition $(T, \mathcal{D})$ is defined to be $\max_{t \in V(T)} |\mathcal{D}(t)| - 1$, and the *treewidth* of $G$, written $tw(G)$, is the minimum width over all tree decompositions of $G$. The *pathwidth* of $G$, $pw(G)$, is the minimum width over all path decompositions of $G$.

2 Positive results

In this section we identify a number of structural restrictions on the input graph that allow us to compute the maximum modularity of a graph, or a good approximation to this quantity, efficiently.

2.1 Parameterisation by vertex cover number

In this section we demonstrate that MODULARITY is in FPT when parameterised by the vertex cover number of the input graph.
## 9:4 The Parameterised Complexity of Computing the Maximum Modularity of a Graph

**Fact 1.2 (Lemma 3.4 of [3]).** Suppose that $G$ is a graph that contains no isolated vertices. If $A$ is a partition of $V(G)$ such that $q_A(G) = q^*(G)$ then, for every $A \in A$, $G[A]$ is a connected subgraph of $G$.

**Fact 1.3 (Corollary 1 of [3]).** Let $G = (V, E)$ and suppose that $V_0 \subseteq V$ is a set of isolated vertices. Then $q(G) = q(G \setminus V_0)$. Moreover, if partitions $A$ and $A'$ agree on all vertices of $V \setminus V_0$, then $q_A(G) = q_{A'}(G)$.

**Fact 1.4 (Lemma 1 of [8], Lemma 2.1 of [5]).** For any integer $c > 0$ and any graph $G$,

$$ \max_{|A| \le c} q_A(G) > q^*(G) \left(1 - \frac{1}{c}\right). $$

## 1.2 Notation and definitions

Given a graph $G = (V, E)$, and a set $U \subseteq V$ of vertices, we write $G[U]$ for the subgraph of $G$ induced by $U$ and $G \setminus U$ for $G[V \setminus U]$. Given two disjoint subsets of vertices $A, B \subseteq V$, we write $e(A, B)$ for the number of edges with one endpoint in $A$ and the other in $B$. We shall often want to denote the number of edges between a set of vertices and the remainder of the graph so set $\partial(A) = e(A, \bar{A})$. If $\mathcal{P}$ is a partition of a set $X$, and $Y \subset X$, we write $\mathcal{P}[Y]$ for the restriction of $\mathcal{P}$ to $Y$.

A vertex cover of a graph $G = (V, E)$ is a set $U \subseteq V$ such that every edge has at least one endpoint in $U$; equivalently, $G \setminus U$ is an independent set (i.e. contains no edges). The vertex cover number of $G$ is the smallest cardinality of any vertex cover of $G$. A feedback vertex set for $G$ is a set $U \subseteq V$ such that $G \setminus U$ contains no cycles. Notice that the vertex cover number of $G$ gives an upper bound on the size of the smallest feedback vertex set for $G$, written $fvs(G)$. The max leaf number of $G$ is the maximum number of leaves (degree one vertices) in any spanning tree of $G$.

A tree decomposition of a graph $G$ is a pair $(T, \mathcal{D})$ where $T$ is a tree and $\mathcal{D} = \{\mathcal{D}(t) : t \in V(T)\}$ is a collection of non-empty subsets of $V(G)$ (or bags), indexed by the nodes of $T$, satisfying:

1. $V(G) = \bigcup_{t \in V(T)} \mathcal{D}(t)$,

2. for every $e = uv \in E(G)$, there exists $t \in V(T)$ such that $u, v \in \mathcal{D}(t)$,

3. for every $v \in V(G)$, if $T(v)$ is defined to be the subgraph of $T$ induced by nodes $t$ with $v \in \mathcal{D}(t)$, then $T(v)$ is connected.

If $T$ is in fact a path, we say that $(T, \mathcal{D})$ is a path decomposition of $G$. The width of the tree decomposition $(T, \mathcal{D})$ is defined to be $\max_{t \in V(T)} |\mathcal{D}(t)| - 1$, and the treewidth of $G$, written $tw(G)$, is the minimum width over all tree decompositions of $G$. The pathwidth of $G$, $pw(G)$, is the minimum width over all path decompositions of $G$.

# 2 Positive results

In this section we identify a number of structural restrictions on the input graph that allow us to compute the maximum modularity of a graph, or a good approximation to this quantity, efficiently.

## 2.1 Parameterisation by vertex cover number

In this section we demonstrate that MODULARITY is in FPT when parameterised by the vertex cover number of the input graph.
**► Theorem 2.1.** MODULARITY, parameterised by cardinality of a minimum vertex cover for the input graph G, is in FPT.

To prove this result, we make use of recent work of Lokshtanov [18] which gives an FPT algorithm for the following problem.

INTEGER QUADRATIC PROGRAMMING

*Input:* An $n \times n$ integer matrix $Q$, an $m \times n$ integer matrix $A$, and an $m$-dimensional vector $\mathbf{b}$.

*Parameter:* $n + \alpha$, where $\alpha$ is the maximum absolute value of any entry in $A$ or $Q$.

*Problem:* Find a vector $\mathbf{x} \in \mathbb{Z}^n$ which minimises $\mathbf{x}^T Q \mathbf{x}$, subject to $A\mathbf{x} \le \mathbf{b}$.

Before proving Theorem 2.1, we introduce some notation. Suppose that the graph $G = (V, E)$ has $|E| = m$, and that $U = \{u_1, \dots, u_k\}$ is a vertex cover for $G$. Let $\mathcal{P} = \{P_1, \dots, P_l\}$ be a partition of $U$, and set $W = V \setminus U$ (so $W$ is an independent set).

We can partition the vertices of $W$ into $2^k$ sets based on their type: the type $\tau_U(w) \in \{0, 1\}^k$ of a vertex $w \in W$ describes which of the vertices in $U$ are neighbours of $w$. Formally $\tau_U(w)_j = 1$ if $u_j w \in E(G)$ and $\tau_U(w)_j = 0$ otherwise. For each $\sigma \in \{0, 1\}^k$, we set $S_\sigma$ to be the set of all vertices in $W$ with type exactly $\sigma$, that is, $S_\sigma = \{w \in W : \tau(w) = \sigma\}$.

Now let $\mathcal{A} = \{A_1, \dots, A_r\}$ be a partition of $V$. We write $x_{\sigma,i}^A$ for the number of vertices of type $\sigma$ which are assigned to $A_i$, that is, $x_{\sigma,i}^A = |S_\sigma \cap A_i|$. Finally, we introduce 0-1 vectors to encode the sets $P_i \in \mathcal{P}$: for $1 \le i \le \ell$, we let $\pi^i \in \{0, 1\}^k$ be given by $\pi^i_j = 1$ if $u_j \in P_i$, and $\pi^i_j = 0$ otherwise.

We now argue that, if the partition $\mathcal{A}$ extends $\mathcal{P}$, we can compute the modularity of $\mathcal{A}$ using only the values $x_{\sigma,i}^A$, together with information about $\mathcal{P}$. This shows that the modularity depends only on the number of vertices of each type assigned to a given partition, and not the assignment of individual vertices. The proof is omitted due to space constraints.

**► Lemma 2.2.** Let $U = \{u_1, \dots, u_k\}$ be a vertex cover for $G = (V, E)$, where $|E| = m$, and let $\mathcal{P}$ be a partition of $U$. If $\mathcal{A}$ is any partition of $V$ which extends $\mathcal{P}$ and has the property that every $A \in \mathcal{A}$ has non-empty intersection with $U$, then

$$q_{\mathcal{A}}^{E}(G) = \frac{1}{m} \sum_{i=1}^{\ell} e(P_i) + \frac{1}{m} \sum_{(\sigma, i)} x_{\sigma, i}^{A}(\sigma \cdot \pi^i),$$

and

$$4m^2 q_{\mathcal{A}'}^{D} = 4 \sum_{i} e(P_i)^2 + 4 \sum_{(\sigma, i)} x_{\sigma, i}^{A} e(P_i)(\sigma \cdot (\mathbf{1} + \pi^i)) \\ + \sum_{(\sigma, i)(\sigma', j)} x_{\sigma, i}^{A} x_{\sigma', j}^{A}(\sigma \cdot (\mathbf{1} + \pi^i))(\sigma' \cdot (\mathbf{1} + \pi^j)).$$

**Proof of Theorem 2.1.** We will assume that the input to our instance of MODULARITY is a graph $G = (V, E)$, where $|E| = m$. We may assume without loss of generality that we are also given as input a vertex cover $U = \{u_1, \dots, u_k\}$ for $G$ (as if not we can easily compute one in the allowed time). We may further assume that $G$ does not contain any isolated vertices, as we can delete any such vertices (in polynomial time) without changing the value of the maximum modularity (by Fact 1.3).
**► Theorem 2.1.** MODULARITY, parameterised by cardinality of a minimum vertex cover for the input graph G, is in FPT.

To prove this result, we make use of recent work of Lokshtanov [18] which gives an FPT algorithm for the following problem.

INTEGER QUADRATIC PROGRAMMING

*Input:* An $n \times n$ integer matrix $Q$, an $m \times n$ integer matrix $A$, and an $m$-dimensional vector $b$.

*Parameter:* $n + \alpha$, where $\alpha$ is the maximum absolute value of any entry in $A$ or $Q$.

*Problem:* Find a vector $\mathbf{x} \in \mathbb{Z}^n$ which minimises $\mathbf{x}^T Q \mathbf{x}$, subject to $A\mathbf{x} \le \mathbf{b}$.

Before proving Theorem 2.1, we introduce some notation. Suppose that the graph $G = (V, E)$ has $|E| = m$, and that $U = \{u_1, \dots, u_k\}$ is a vertex cover for $G$. Let $\mathcal{P} = \{P_1, \dots, P_l\}$ be a partition of $U$, and set $W = V \setminus U$ (so $W$ is an independent set).

We can partition the vertices of $W$ into $2^k$ sets based on their *type*: the type $\tau_U(w) \in \{0, 1\}^k$ of a vertex $w \in W$ describes which of the vertices in $U$ are neighbours of $w$. Formally $\tau_U(w)_j = 1$ if $u_j w \in E(G)$ and $\tau_U(w)_j = 0$ otherwise. For each $\sigma \in \{0, 1\}^k$, we set $S_\sigma$ to be the set of all vertices in $W$ with type exactly $\sigma$, that is, $S_\sigma = \{w \in W : \tau(w) = \sigma\}$.

Now let $\mathcal{A} = \{A_1, \dots, A_r\}$ be a partition of $V$. We write $x_{\sigma,i}^{\mathcal{A}}$ for the number of vertices of type $\sigma$ which are assigned to $A_i$, that is, $x_{\sigma,i}^{\mathcal{A}} = |S_{\sigma} \cap A_i|$. Finally, we introduce 0-1 vectors to encode the sets $P_i \in \mathcal{P}$: for $1 \le i \le \ell$, we let $\pi^i \in \{0, 1\}^k$ be given by $\pi^i_j = 1$ if $u_j \in P_i$, and $\pi^i_j = 0$ otherwise.

We now argue that, if the partition $\mathcal{A}$ extends $\mathcal{P}$, we can compute the modularity of $\mathcal{A}$ using only the values $x_{\sigma,i}^{\mathcal{A}}$, together with information about $\mathcal{P}$. This shows that the modularity depends only on the number of vertices of each type assigned to a given partition, and not the assignment of individual vertices. The proof is omitted due to space constraints.

**► Lemma 2.2.** Let $U = \{u_1, \dots, u_k\}$ be a vertex cover for $G = (V, E)$, where $|E| = m$, and let $\mathcal{P}$ be a partition of $U$. If $\mathcal{A}$ is any partition of $V$ which extends $\mathcal{P}$ and has the property that every $A \in \mathcal{A}$ has non-empty intersection with $U$, then

$$q_{\mathcal{A}}^{E}(G) = \frac{1}{m} \sum_{i=1}^{\ell} e(P_i) + \frac{1}{m} \sum_{(\sigma, i)} x_{\sigma, i}^{\mathcal{A}}(\sigma \cdot \pi^i),$$

and

$$4m^2 q_{\mathcal{A}'}^{D} = 4 \sum_{i} e(P_i)^2 + 4 \sum_{(\sigma, i)} x_{\sigma, i}^{\mathcal{A}} e(P_i)(\sigma \cdot (\mathbf{1} + \pi^i)) \\ + \sum_{(\sigma, i)(\sigma', j)} x_{\sigma, i}^{\mathcal{A}} x_{\sigma', j}^{\mathcal{A}} (\sigma \cdot (\mathbf{1} + \pi^i))(\sigma' \cdot (\mathbf{1} + \pi^j)).$$

**Proof of Theorem 2.1.** We will assume that the input to our instance of MODULARITY is a graph $G = (V, E)$, where $|E| = m$. We may assume without loss of generality that we are also given as input a vertex cover $U = \{u_1, \dots, u_k\}$ for $G$ (as if not we can easily compute one in the allowed time). We may further assume that $G$ does not contain any isolated vertices, as we can delete any such vertices (in polynomial time) without changing the value of the maximum modularity (by Fact 1.3).
Note that the total number of possible partitions of $U$ into non-empty parts is equal to the $k^{th}$ Bell number, $B_k$ (and hence is certainly less than $k^k$). It therefore suffices to describe an fpt-algorithm which determines, given some partition $\mathcal{P}$ of $U$,

$$q^{\mathcal{P}}(G) = \max\{q_{\mathcal{A}}(G) : \mathcal{A}[U] = \mathcal{P}\}.$$

The maximum modularity of $G$ can then be calculated by taking

$$\max\{q^{\mathcal{P}}(G) : \mathcal{P} \text{ is a partition of } U\}.$$

From now on, we consider a fixed partition $\mathcal{P} = \{P_1, \dots, P_\ell\}$ of $U$, and describe how to compute $q^{\mathcal{P}}(G)$.

It follows from Facts 1.1 and 1.2, together with the fact that $W$ is an independent set that, if $\mathcal{A} = \{A_1, \dots, A_j\}$ is a partition of $V$ which achieves the maximum modularity, then every part $A_i$ has non-empty intersection with $U$. We will call a partition with this properties a $U$-partition of $G$. It then suffices to maximise the modularity over all $U$-partitions in order to determine the value of $q^{\mathcal{P}}(G)$.

Now, by Lemma 2.2, we know that we can express the modularity of a $U$-partition $\mathcal{A}$ as

$$\begin{aligned} q_{\mathcal{A}}(G) = & \frac{1}{m} \sum_{i=1}^{\ell} e(P_i) + \frac{1}{m} \sum_{(\sigma, i)} x_{\sigma, i}^{\mathcal{A}}(\sigma \cdot \pi^i) - \frac{1}{m^2} \sum_{i} e(P_i)^2 \\ & - \frac{1}{m^2} \sum_{(\sigma, i)} x_{\sigma, i}^{\mathcal{A}} e(P_i)(\sigma \cdot (\mathbf{1} + \pi^i)) \\ & - \frac{1}{4m^2} \sum_{(\sigma, i)(\sigma', j)} x_{\sigma, i}^{\mathcal{A}} x_{\sigma', j}^{\mathcal{A}} (\sigma \cdot (\mathbf{1} + \pi^i))(\sigma' \cdot (\mathbf{1} + \pi^j)). \end{aligned} \quad (1)$$

As we have fixed the partition $\mathcal{P}$, all values $e(P_i)$ can be regarded as fixed constants. In order to determine the maximum modularity we can obtain with a $U$-partition, we therefore need to find the values of $x_{\sigma, i}^{\mathcal{A}}$ which maximise this expression.

We can rewrite (1) as the sum of a constant term, two linear functions $\theta$ and $\phi$ of the $x_{\sigma, i}^{\mathcal{A}}$ and a quadratic function $\psi$ of the $x_{\sigma, i}^{\mathcal{A}}$ (up to scaling by constants):

$$\begin{aligned} q_{\mathcal{A}}(G) = & \frac{1}{m} \underbrace{\sum_{i=1}^{\ell} e(P_i)}_{\text{constant}} - \frac{1}{m^2} \underbrace{\sum_{i} e(P_i)^2}_{\theta(\mathcal{A})} \\ & + \frac{1}{m} \underbrace{\sum_{(\sigma, i)} x_{\sigma, i}^{\mathcal{A}}(\sigma \cdot \pi^i)}_{\phi(\mathcal{A})} - \frac{1}{m^2} \underbrace{\sum_{(\sigma, i)} x_{\sigma, i}^{\mathcal{A}} e(P_i)(\sigma \cdot (\mathbf{1} + \pi^i))}_{\psi(\mathcal{A})} \\ & - \frac{1}{4m^2} \underbrace{\sum_{(i, \sigma)(j, \sigma')} x_{\sigma, i}^{\mathcal{A}} x_{\sigma', j}^{\mathcal{A}} (\sigma \cdot (\mathbf{1} + \pi^i))(\sigma' \cdot (\mathbf{1} + \pi^j))}_{\psi(\mathcal{A})}. \end{aligned}$$

To find the maximum value of $q_{\mathcal{A}}(G)$ over all $U$-partitions it therefore suffices to determine, for all possible values of $\theta(\mathcal{A})$ and $\phi(\mathcal{A})$, the minimum possible value of $\psi(\mathcal{A})$. Before describing how to do this, we observe that the number of combinations of possible values for $\theta(\mathcal{A})$ and $\phi(\mathcal{A})$ and is not too large. Note that $0 \le \sum_{\sigma, i} x_{\sigma, i}^{\mathcal{A}}(\sigma \cdot \pi^i) < nk$, and $0 \le \sum_{\sigma, i} x_{\sigma, i}^{\mathcal{A}} e(P_i)(\sigma \cdot (\mathbf{1} + \pi^i)) < n \binom{k}{2} 2k < nk^3$, so the number of possible pairs $(\theta(\mathcal{A}), \phi(\mathcal{A}))$
9:6 The Parameterised Complexity of Computing the Maximum Modularity of a Graph

Note that the total number of possible partitions of $U$ into non-empty parts is equal to the $k^{th}$ Bell number, $B_k$ (and hence is certainly less than $k^k$). It therefore suffices to describe an fpt-algorithm which determines, given some partition $\mathcal{P}$ of $U$,

$$q^{\mathcal{P}}(G) = \max\{q_{\mathcal{A}}(G) : \mathcal{A}[U] = \mathcal{P}\}.$$

The maximum modularity of $G$ can then be calculated by taking

$$\max\{q^{\mathcal{P}}(G) : \mathcal{P} \text{ is a partition of } U\}.$$

From now on, we consider a fixed partition $\mathcal{P} = \{P_1, \dots, P_\ell\}$ of $U$, and describe how to compute $q^{\mathcal{P}}(G)$.

It follows from Facts 1.1 and 1.2, together with the fact that $W$ is an independent set that, if $\mathcal{A} = \{A_1, \dots, A_j\}$ is a partition of $V$ which achieves the maximum modularity, then every part $A_i$ has non-empty intersection with $U$. We will call a partition with this properties a $U$-partition of $G$. It then suffices to maximise the modularity over all $U$-partitions in order to determine the value of $q^{\mathcal{P}}(G)$.

Now, by Lemma 2.2, we know that we can express the modularity of a $U$-partition $\mathcal{A}$ as

$$q_{\mathcal{A}}(G) = \frac{1}{m} \sum_{i=1}^{\ell} e(P_i) + \frac{1}{m} \sum_{(\sigma, i)} x_{\sigma, i}^{\mathcal{A}}(\sigma \cdot \pi^i) - \frac{1}{m^2} \sum_{i} e(P_i)^2 \\ - \frac{1}{m^2} \sum_{(\sigma, i)} x_{\sigma, i}^{\mathcal{A}} e(P_i)(\sigma \cdot (\mathbf{1} + \pi^i)) \\ - \frac{1}{4m^2} \sum_{(\sigma, i)(\sigma', j)} x_{\sigma, i}^{\mathcal{A}} x_{\sigma', j}^{\mathcal{A}} (\sigma \cdot (\mathbf{1} + \pi^i))(\sigma' \cdot (\mathbf{1} + \pi^j)). \quad (1)$$

As we have fixed the partition $\mathcal{P}$, all values $e(P_i)$ can be regarded as fixed constants. In order to determine the maximum modularity we can obtain with a $U$-partition, we therefore need to find the values of $x_{\sigma, i}^{\mathcal{A}}$ which maximise this expression.

We can rewrite (1) as the sum of a constant term, two linear functions $\theta$ and $\phi$ of the $x_{\sigma, i}^{\mathcal{A}}$ and a quadratic function $\psi$ of the $x_{\sigma, i}^{\mathcal{A}}$ (up to scaling by constants):

$$q_{\mathcal{A}}(G) = \underbrace{\frac{1}{m} \sum_{i=1}^{\ell} e(P_i) - \frac{1}{m^2} \sum_{i} e(P_i)^2}_{\text{constant}} \\ + \underbrace{\frac{1}{m} \sum_{(\sigma, i)} x_{\sigma, i}^{\mathcal{A}}(\sigma \cdot \pi^i) - \frac{1}{m^2} \sum_{(\sigma, i)} x_{\sigma, i}^{\mathcal{A}} e(P_i)(\sigma \cdot (\mathbf{1} + \pi^i))}_{\theta(\mathcal{A})} \\ - \underbrace{\frac{1}{4m^2} \sum_{(i, \sigma)(j, \sigma')} x_{\sigma, i}^{\mathcal{A}} x_{\sigma', j}^{\mathcal{A}} (\sigma \cdot (\mathbf{1} + \pi^i))(\sigma' \cdot (\mathbf{1} + \pi^j))}_{\psi(\mathcal{A})}.$$

To find the maximum value of $q_{\mathcal{A}}(G)$ over all $U$-partitions it therefore suffices to determine, for all possible values of $\theta(\mathcal{A})$ and $\phi(\mathcal{A})$, the minimum possible value of $\psi(\mathcal{A})$. Before describing how to do this, we observe that the number of combinations of possible values for $\theta(\mathcal{A})$ and $\phi(\mathcal{A})$ and is not too large. Note that $0 \le \sum_{\sigma, i} x_{\sigma, i}^{\mathcal{A}}(\sigma \cdot \pi^i) < nk$, and $0 \le \sum_{\sigma, i} x_{\sigma, i}^{\mathcal{A}} e(P_i)(\sigma \cdot (\mathbf{1} + \pi^i)) < n \binom{k}{2} 2k < nk^3$, so the number of possible pairs $(\theta(\mathcal{A}), \phi(\mathcal{A}))$
is at most $n^2k^4$. Thus, if we know the minimum possible value of $\psi(\mathcal{A})$ corresponding to each possible pair $(\theta(\mathcal{A}), \phi(\mathcal{A}))$, we can compute the maximum modularity achieved by any $U$-partition $\mathcal{A}$ such that $(\theta(\mathcal{A}), \phi(\mathcal{A})) = (y, z)$, and maximising over the polynomial number of possible pairs $(y, z)$ will give $q^P(G)$.

Now, given a possible pair of values $(y, z)$ for $(\theta(\mathcal{A}), \phi(\mathcal{A}))$, we describe how to compute

$$ \min\{\psi(\mathcal{A}) : \mathcal{A} \text{ is a } U\text{-partition with } \theta(\mathcal{A}) = y \text{ and } \phi(\mathcal{A}) = z\}. $$

Our strategy is to express this minimisation problem as an instance of INTEGER QUADRATIC PROGRAMMING and then apply the FPT algorithm of [18].

In this instance, we have $n = \ell 2^k \le k 2^k$, and our vector of variables $\mathbf{x} = (x_1, \dots, x_n)^T$ is given by

$$ x_i = x_{(\sigma_i \bmod 2^k), \lceil i/2^k \rceil}^A, $$

where $\sigma_1, \dots, \sigma_{2^k}$ is a fixed enumeration of all vectors in $\{0, 1\}^k$. The matrix $Q$ expresses the value of $\psi(\mathcal{A})$ in terms of $\mathbf{x}$: if we set $Q = \{q_{i,j}\}$ where

$$ q_{i,j} = (\sigma_{(i \bmod 2^k)} \cdot (\mathbf{1} + \pi^{\lceil i/2^k \rceil})) (\sigma_{(j \bmod 2^k)} \cdot (\mathbf{1} + \pi^{\lceil j/2^k \rceil})), $$

then it is easy to see that $\psi(\mathcal{A}) = \mathbf{x}^T Q \mathbf{x}$. Note also that the maximum absolute value of any entry in $Q$ is at most $4k^2$.

We now use the linear constraints to express the conditions that

1. $\theta(\mathcal{A}) = y$,

2. $\phi(\mathcal{A}) = z$, and

3. the values $x_{i,\sigma}$ correspond to a valid $U$-partition $\mathcal{A}$.

The first of these conditions can be expressed as a single linear constraint:

$$ \sum_{(\sigma, i)} x_{\sigma, i}^{A} (\sigma \cdot \pi^{i}) = y, $$

or equivalently $\mathbf{a}_1 \mathbf{x} = y$ where $\mathbf{a}_1$ is the $1 \times n$ row vector with $i^{th}$ entry equal to

$$ \sigma_{(i \bmod 2^k)} \cdot \pi^{\lceil i/2^k \rceil}. $$

We can similarly express the second condition as a single linear constraint:

$$ \sum_{(\sigma, i)} x_{\sigma, i}^{A} e(P_i)(\sigma \cdot (\mathbf{1} + \pi^{i})) = z, $$

or equivalently $\mathbf{a}_2 \mathbf{x} = z$, where $\mathbf{a}_2$ is the $1 \times n$ row vector with $i^{th}$ entry equal to

$$ e(P_{\lceil i/2^k \rceil}) (\sigma_{(i \bmod 2^k)} \cdot (\mathbf{1} + \pi^{\lceil i/2^k \rceil})). $$

Note that every entry in the vectors $\mathbf{a}_1$ and $\mathbf{a}_2$ has absolute value no more than $2k^3$. For the third condition, note that the values $x_{i,\sigma}$ correspond to a valid $U$-partition if and only if every $x_{i,\sigma}$ is non-negative, and for each $\sigma$ we have $\sum_{i=1}^{\ell} x_{i,\sigma}^A = |S_{\sigma}|$.

We can therefore express all three conditions in the form $Ax = b$, where $A$ is a $(4 + (\ell + 1)2^k) \times n$ and $b$ is a $(4 + (\ell + 1)2^k)$-dimensional vector (notice that we use two inequalities to express each of the linear equality constraints).

Altogether, this means that a solution to this instance of INTEGER QUADRATIC PROGRAMMING will determine the values of $x_{i,\sigma}^A$ which minimize (out of all values corresponding to
is at most $n^2k^4$. Thus, if we know the minimum possible value of $\psi(\mathcal{A})$ corresponding to each possible pair $(\theta(\mathcal{A}), \phi(\mathcal{A}))$, we can compute the maximum modularity achieved by any $U$-partition $\mathcal{A}$ such that $(\theta(\mathcal{A}), \phi(\mathcal{A})) = (y, z)$, and maximising over the polynomial number of possible pairs $(y, z)$ will give $q^P(G)$.

Now, given a possible pair of values $(y, z)$ for $(\theta(\mathcal{A}), \phi(\mathcal{A}))$, we describe how to compute

$$ \min\{\psi(\mathcal{A}) : \mathcal{A} \text{ is a } U\text{-partition with } \theta(\mathcal{A}) = y \text{ and } \phi(\mathcal{A}) = z\}. $$

Our strategy is to express this minimisation problem as an instance of INTEGER QUADRATIC PROGRAMMING and then apply the FPT algorithm of [18].

In this instance, we have $n = \ell 2^k \le k 2^k$, and our vector of variables $\mathbf{x} = (x_1, \dots, x_n)^T$ is given by

$$ x_i = x_{(\sigma_i \bmod 2^k), \lceil i/2^k \rceil}^A, $$

where $\sigma_1, \dots, \sigma_{2^k}$ is a fixed enumeration of all vectors in $\{0, 1\}^k$. The matrix $Q$ expresses the value of $\psi(\mathcal{A})$ in terms of $\mathbf{x}$: if we set $Q = \{q_{i,j}\}$ where

$$ q_{i,j} = \left( \sigma_{(i \bmod 2^k)} \cdot \left( \mathbf{1} + \pi^{\lceil i/2^k \rceil} \right) \right) \left( \sigma_{(j \bmod 2^k)} \cdot \left( \mathbf{1} + \pi^{\lceil j/2^k \rceil} \right) \right), $$

then it is easy to see that $\psi(\mathcal{A}) = \mathbf{x}^T Q \mathbf{x}$. Note also that the maximum absolute value of any entry in $Q$ is at most $4k^2$.

We now use the linear constraints to express the conditions that

1. $\theta(\mathcal{A}) = y$,

2. $\phi(\mathcal{A}) = z$, and

3. the values $x_{i,\sigma}$ correspond to a valid $U$-partition $\mathcal{A}$.

The first of these conditions can be expressed as a single linear constraint:

$$ \sum_{(\sigma, i)} x_{\sigma, i}^{A} (\sigma \cdot \pi^{i}) = y, $$

or equivalently $\mathbf{a}_1\mathbf{x} = y$ where $\mathbf{a}_1$ is the $1 \times n$ row vector with $i^{th}$ entry equal to

$$ \sigma_{(i \bmod 2^k)} \cdot \pi^{\lceil i/2^k \rceil}. $$

We can similarly express the second condition as a single linear constraint:

$$ \sum_{(\sigma, i)} x_{\sigma, i}^{A} e(P_i)(\sigma \cdot (\mathbf{1} + \pi^{i})) = z, $$

or equivalently $\mathbf{a}_2\mathbf{x} = z$, where $\mathbf{a}_2$ is the $1 \times n$ row vector with $i^{th}$ entry equal to

$$ e(P_{\lceil i/2^k \rceil}) \left( \sigma_{(i \bmod 2^k)} \cdot \left( \mathbf{1} + \pi^{\lceil i/2^k \rceil} \right) \right). $$

Note that every entry in the vectors $\mathbf{a}_1$ and $\mathbf{a}_2$ has absolute value no more than $2k^3$. For the third condition, note that the values $x_{i,\sigma}$ correspond to a valid $U$-partition if and only if every $x_{i,\sigma}$ is non-negative, and for each $\sigma$ we have $\sum_{i=1}^{\ell} x_{i,\sigma}^A = |S_{\sigma}|$.

We can therefore express all three conditions in the form $Ax = b$, where $A$ is a $(4 + (\ell + 1)2^k) \times n$ and $b$ is a $(4 + (\ell + 1)2^k)$-dimensional vector (notice that we use two inequalities to express each of the linear equality constraints).

Altogether, this means that a solution to this instance of INTEGER QUADRATIC PROGRAMMING will determine the values of $x_{i,\sigma}^A$ which minimize (out of all values corresponding to
9:8 The Parameterised Complexity of Computing the Maximum Modularity of a Graph

some U-partition A) the value of ψ(A), subject to the additional requirement that θ(A) = y and φ(A) = z. Note that the number of variables n is at most k2^k and the largest absolute value of any entry in A or Q is at most 2k^3, so the parameter in the instance of INTEGER QUADRATIC PROGRAMMING is bounded by a function of k. This completes the proof. ◀

We note the algorithm described can easily be modified to output an optimal partition.

2.2 Parameterisation by treewidth

In this section we demonstrate that MODULARITY, parameterised by the treewidth of the input graph G, belongs to XP and so is solvable in polynomial time on graph classes whose treewidth is bounded by some fixed constant. We further show that for any fixed ε > 0 there is an FPT-algorithm, parameterised by treewidth, which computes a factor (1 − ε)-approximation; i.e. returning a value between (1 − ε)q* and q* where q* is the maximum modularity of the graph.

► **Theorem 2.3.** MODULARITY parameterised by the treewidth of the input graph G is in XP.

This result makes use of standard dynamic programming techniques, and details are omitted due to space constraints. The key property of modularity we use is that each part in a partition that maximises modularity must induce a connected subgraph, so it suffices to keep track of feasible statistics for each part that intersects the bag of the tree decomposition under consideration, together with the contribution to modularity from parts that are entirely “below” the current bag.

To obtain our FPT approximation result, we use a very similar approach; the key is to
restrict our attention to partitions with only a constant number of parts. For any constant
c ∈ N, we write $q_{\le c}^*(G)$ for the maximum modularity for G achievable with a partition into
at most c parts, that is

$$
q_{\le c}^{*}(G) = \max_{|A| \le c} q_{A}(G).
$$

We refer to the problem of deciding whether $q_{\le c}^*(G) \ge q$ for a given input graph $G$ and constant $q \in [0, 1]$ as $c$-MODULARITY. We now argue that $c$-MODULARITY is in FPT parameterised by the treewidth of the input graph.

► **Lemma 2.4.** *c*-MODULARITY is in FPT when parameterised by the treewidth of the input graph.

The crucial difference from our XP algorithm above is the fact that, when we fix the
number of parts in the partition, we can no longer assume that every part is connected.
However, if the maximum number of parts c is a constant, we can keep track of the necessary
statistics for every possible part, not just those that intersect the bag under consideration.

Recall (Fact 1.4) that $q^*(G) \ge q_{\le c}^*(G)) > q^*(G)(1 - \frac{1}{c})$; thus, for any constant $\epsilon > 0$, we obtain a multiplicative approximation with relative error at most $\epsilon$ by solving $\lceil \frac{1}{\epsilon} \rceil$-MODULARITY. This immediately gives the following result.

**Corollary 2.5.** *Given any constant* `ε > 0`, *there is an FPT-algorithm, parameterised by the*  
*treewidth of the input graph G, that that returns a partition A with* `q<sub>A</sub>(G) > (1 - ε)q<sub>*</sub>(G).`

We conclude this section by noting that sparse graphs, in particular graphs G with low
tree width, $\mathrm{tw}(G)$, and maximum degree, $\triangle(G)$, can have high maximum modularity. In
particular Theorem 1.11 of [19] shows $q^*(G) \ge 1 - 2((\mathrm{tw}(G) + 1)\triangle(G)/|E(G)|)^{1/2}$.
9:8 The Parameterised Complexity of Computing the Maximum Modularity of a Graph

some U-partition A) the value of ψ(A), subject to the additional requirement that θ(A) = y and φ(A) = z. Note that the number of variables n is at most k2^k and the largest absolute value of any entry in A or Q is at most 2k^3, so the parameter in the instance of INTEGER QUADRATIC PROGRAMMING is bounded by a function of k. This completes the proof. ◀

We note the algorithm described can easily be modified to output an optimal partition.

2.2 Parameterisation by treewidth

In this section we demonstrate that MODULARITY, parameterised by the treewidth of the input graph G, belongs to XP and so is solvable in polynomial time on graph classes whose treewidth is bounded by some fixed constant. We further show that for any fixed ε > 0 there is an FPT-algorithm, parameterised by treewidth, which computes a factor (1 − ε)-approximation; i.e. returning a value between (1 − ε)q* and q* where q* is the maximum modularity of the graph.

► Theorem 2.3. MODULARITY parameterised by the treewidth of the input graph G is in XP.

This result makes use of standard dynamic programming techniques, and details are omitted due to space constraints. The key property of modularity we use is that each part in a partition that maximises modularity must induce a connected subgraph, so it suffices to keep track of feasible statistics for each part that intersects the bag of the tree decomposition under consideration, together with the contribution to modularity from parts that are entirely “below” the current bag.

To obtain our FPT approximation result, we use a very similar approach; the key is to restrict our attention to partitions with only a constant number of parts. For any constant c ∈ N, we write $q_{\le c}^*(G)$ for the maximum modularity for G achievable with a partition into at most c parts, that is

$$
q_{\le c}^*(G) = \max_{|A| \le c} q_A(G).
$$

We refer to the problem of deciding whether $q_{\le c}^*(G) \ge q$ for a given input graph $G$ and constant $q \in [0, 1]$ as $c$-MODULARITY. We now argue that $c$-MODULARITY is in FPT parameterised by the treewidth of the input graph.

► Lemma 2.4. *c*-MODULARITY is in FPT when parameterised by the treewidth of the input graph.

The crucial difference from our XP algorithm above is the fact that, when we fix the
number of parts in the partition, we can no longer assume that every part is connected.
However, if the maximum number of parts c is a constant, we can keep track of the necessary
statistics for every possible part, not just those that intersect the bag under consideration.

Recall (Fact 1.4) that $q^*(G) \ge q_{\le c}^*(G)) > q^*(G)(1 - \frac{1}{c})$; thus, for any constant $\epsilon > 0$, we obtain a multiplicative approximation with relative error at most $\epsilon$ by solving $\lceil \frac{1}{\epsilon} \rceil$-MODULARITY. This immediately gives the following result.

**Corollary 2.5.** *Given any constant* `ε > 0`, *there is an FPT-algorithm, parameterised by the treewidth of the input graph G, that returns a partition A with* `q<sub>A</sub>(G) > (1 - ε)q<sup>*</sup>(G)`.

We conclude this section by noting that sparse graphs, in particular graphs G with low
tree width, $\mathrm{tw}(G)$, and maximum degree, $\triangle(G)$, can have high maximum modularity. In
particular Theorem 1.11 of [19] shows $q^*(G) \ge 1 - 2((\mathrm{tw}(G) + 1)\triangle(G)/|E(G)|)^{1/2}$.
## 2.3 Parameterisation by max leaf number

In this section we demonstrate that MODULARITY can be solved in time linear in the number of connected subgraphs of the input graph $G$; as a consequence of this result, we deduce that the problem belongs to XP when parameterised by the max leaf number of $G$.

**Theorem 2.6.** Let $G$ be a graph on $n$ vertices with $m$ edges and at most $h$ connected subgraphs. Then MODULARITY can be solved in time $O(h^2n)$.

This is achieved by means of a dynamic programming strategy, in which we compute the maximum value of a modularity-like function for each connected subgraph in turn, considering the subgraphs in nondecreasing order of their number of vertices. Full details of the proof are omitted due to space constraints.

It is known that, if the max leaf number of $G$ is $c$, then $G$ is a subdivision of some graph $H$ on at most $4c$ vertices [12]; a graph on $n$ vertices that is a subdivision of such a graph $H$ has at most $2^{4c}n^{(4c)^2}$ connected subgraphs (once we have decided which branch vertices belong to a subgraph, it remains only to decide where to cut each path from one of the chosen branch vertices to one we have not chosen). Thus, if the max leaf number of $G$ is bounded by a constant it follows that $G$ has at most a polynomial number of connected subgraphs, and the following result is an immediate consequence of Theorem 2.6.

**Corollary 2.7.** MODULARITY is in XP when parameterised by the max leaf number of the input graph $G$.

We conjecture that this result is not optimal, and that MODULARITY is in fact in FPT with respect to this parameterisation.

# 3 Hardness results

In this section we complement our positive result about the FPT approximability of the problem parameterised by treewidth by demonstrating that computing the exact value of the maximum modularity is hard even in a more restricted setting.

**Theorem 3.1.** MODULARITY, parameterised simultaneously by the pathwidth and the size of a minimum feedback vertex set for the input graph, is W[1]-hard.

Our proof of this result relies on the hardness of the following problem.

**EQUITABLE CONNECTED PARTITION (ECP)**

*Input:* A graph $G = (V, E)$ and $r \in \mathbb{N}$.

*Question:* Is there a partition of $V$ into $r$ classes $V_1, \dots, V_r$ such that $|V_i| - |V_j| \le 1$ for all $1 \le i < j \le r$, and the induced subgraph $G[V_i]$ is connected for each $i \in 1, \dots, r$?

The parameterised complexity of ECP was investigated thoroughly in [11]. Among other results, the problem is shown to be W[1]-hard even when parameterised simultaneously by $r$, pw($G$) and fvs($G$). In proving this hardness result, the authors implicitly consider the following variation of ECP.
## 2.3 Parameterisation by max leaf number

In this section we demonstrate that MODULARITY can be solved in time linear in the number of connected subgraphs of the input graph $G$; as a consequence of this result, we deduce that the problem belongs to XP when parameterised by the max leaf number of $G$.

**Theorem 2.6.** Let $G$ be a graph on $n$ vertices with $m$ edges and at most $h$ connected subgraphs. Then MODULARITY can be solved in time $O(h^2n)$.

This is achieved by means of a dynamic programming strategy, in which we compute the maximum value of a modularity-like function for each connected subgraph in turn, considering the subgraphs in nondecreasing order of their number of vertices. Full details of the proof are omitted due to space constraints.

It is known that, if the max leaf number of $G$ is $c$, then $G$ is a subdivision of some graph $H$ on at most $4c$ vertices [12]; a graph on $n$ vertices that is a subdivision of such a graph $H$ has at most $2^{4c}n^{(4c)^2}$ connected subgraphs (once we have decided which branch vertices belong to a subgraph, it remains only to decide where to cut each path from one of the chosen branch vertices to one we have not chosen). Thus, if the max leaf number of $G$ is bounded by a constant it follows that $G$ has at most a polynomial number of connected subgraphs, and the following result is an immediate consequence of Theorem 2.6.

**Corollary 2.7.** MODULARITY is in XP when parameterised by the max leaf number of the input graph $G$.

We conjecture that this result is not optimal, and that MODULARITY is in fact in FPT with respect to this parameterisation.

# 3 Hardness results

In this section we complement our positive result about the FPT approximability of the problem parameterised by treewidth by demonstrating that computing the exact value of the maximum modularity is hard even in a more restricted setting.

**Theorem 3.1.** MODULARITY, parameterised simultaneously by the pathwidth and the size of a minimum feedback vertex set for the input graph, is W[1]-hard.

Our proof of this result relies on the hardness of the following problem.

**EQUITABLE CONNECTED PARTITION (ECP)**

*Input:* A graph $G = (V, E)$ and $r \in \mathbb{N}$.

*Question:* Is there a partition of $V$ into $r$ classes $V_1, \dots, V_r$ such that $|V_i| - |V_j| \le 1$ for all $1 \le i < j \le r$, and the induced subgraph $G[V_i]$ is connected for each $i \in 1, \dots, r$?

The parameterised complexity of ECP was investigated thoroughly in [11]. Among other results, the problem is shown to be W[1]-hard even when parameterised simultaneously by $r$, pw($G$) and fvs($G$). In proving this hardness result, the authors implicitly consider the following variation of ECP.
ANCHORED EQUITABLE CONNECTED PARTITION (AECP)

Input: A graph $H = (V_H, E_H)$, and a set of distinguished anchor vertices $a_1, \dots, a_r \in V$.

Question: Is there a partition of $V_H$ into $r$ classes $V_1, \dots, V_r$ such that $a_i \in V_i$ for all $i$, $||V_i| - |V_j|| \le 1$ for all $1 \le i < j \le r$, and the induced subgraph $G[V_i]$ is connected for each $i \in 1, \dots, r$?

From the proof of [11, Theorem 1] we can extract the following statement about the hardness of AECP.

**▶ Lemma 3.2** ([11], implicit in proof of Theorem 1). AECP is W[1]-hard, parameterised simultaneously by pw($H$) and fvs($H$), even if the following conditions hold simultaneously:

1. $H$ is connected;

2. the graph $H'$ obtained from $H$ by deleting all vertices of degree one is a subdivision of a 3-regular graph $\tilde{H}$;

3. the branch vertices of $H'$ (i.e. vertices of $\tilde{H}$) are precisely the anchor vertices $a_1, \dots, a_r$;

4. $r \ge 4$ is even and divides $|V_H|$;

5. $H \setminus \{a_1, \dots, a_r\}$ is a disjoint union of isolated vertices and paths with pendant edges.

In the proof of Theorem 3.1, it is useful to analyse the ‘per unit modularity defect’ $f_m(B)$ of vertex subsets $B$. Intuitively, the following lemma (proof omitted due to space constraints) says that, if you are restricted to parts $B$ with $\delta(B) = 4$, the modularity maximising volume is $\text{vol}(B) = 2\sqrt{2m}$. Moreover, while it would usually be better to take parts with $\delta(B) < 4$ these parts are actually worse (i.e. higher $f_m(B)$ value) if their volumes are too big or too small. The function $f_m(B)$ plays a similar role to the n-cost in Proposition 1 of [19].

**▶ Lemma 3.3.** Assume that $m \ge 1$, $\text{vol}(B) \ge 1$ and define

$$f_m(B) = \frac{\partial(B)}{\text{vol}(B)} + \frac{\text{vol}(B)}{2m}.$$

Then the following properties hold:

0: if $\partial(B) = 0$ and $\text{vol}(B) > 4\sqrt{2m}$ then $f_m(B) > 2\sqrt{2/m}$.

1: if $\partial(B) = 1$ and $\text{vol}(B) > 3.7321\sqrt{2m}$ or $\text{vol}(B) < 0.2679\sqrt{2m}$ then $f_m(B) > 2\sqrt{2/m}$.

2: if $\partial(B) = 2$ and $\text{vol}(B) > 3.4143\sqrt{2m}$ or $\text{vol}(B) < 0.5857\sqrt{2m}$ then $f_m(B) > 2\sqrt{2/m}$.

3: if $\partial(B) = 3$ and $\text{vol}(B) > 3\sqrt{2m}$ or $\text{vol}(B) < \sqrt{2m}$ then $f_m(B) > 2\sqrt{2/m}$.

4: if $\partial(B) = 4$ and $\text{vol}(B) = 2\sqrt{2m}$ then $f_m(B) = 2\sqrt{2/m}$.

5: if $\partial(B) \ge 5$ then $f_m(B) > 2\sqrt{2/m}$.

**Proof of Theorem 3.1.** We give a reduction from AECP. Let $(H, \{a_1, \dots, a_r\})$ be the input to an instance of AECP; we will describe how to construct a graph $G$, where pw($G$) and fvs($G$) are both bounded by a function of $r$, together with an explicit $q_0 \in (0, 1)$ such that $(G, q_0)$ is a yes-instance for MODULARITY if and only if $(H, \{a_1, \dots, a_r\})$ is a yes-instance for AECP.

We may assume without loss of generality that our instance of AECP satisfies all of the conditions of Lemma 3.2.

We define a new graph $G$, obtained from $H$ by adding the following (see Figure 1):

- $\alpha$ new leaves adjacent to each anchor vertex $a_1, \dots, a_r$,

- $\beta$ isolated edges disjoint from $G$, and

- an arbitrary perfect matching on the anchor vertices $a_1, \dots, a_r$,
ANCHORED EQUITABLE CONNECTED PARTITION (AECP)

Input: A graph $H = (V_H, E_H)$, and a set of distinguished anchor vertices $a_1, \dots, a_r \in V$.

Question: Is there a partition of $V_H$ into $r$ classes $V_1, \dots, V_r$ such that $a_i \in V_i$ for all $i$, $||V_i| - |V_j|| \le 1$ for all $1 \le i < j \le r$, and the induced subgraph $G[V_i]$ is connected for each $i \in 1, \dots, r$?

From the proof of [11, Theorem 1] we can extract the following statement about the hardness of AECP.

► **Lemma 3.2** ([11], implicit in proof of Theorem 1). *AECP is W[1]-hard, parameterised simultaneously by pw(H) and fvs(H), even if the following conditions hold simultaneously:*

1. $H$ is connected;

2. the graph $H'$ obtained from $H$ by deleting all vertices of degree one is a subdivision of a 3-regular graph $\tilde{H}$;

3. the branch vertices of $H'$ (i.e. vertices of $\tilde{H}$) are precisely the anchor vertices $a_1, \dots, a_r$;

4. $r \ge 4$ is even and divides $|V_H|$;

5. $H \setminus \{a_1, \dots, a_r\}$ is a disjoint union of isolated vertices and paths with pendant edges.

In the proof of Theorem 3.1, it is useful to analyse the 'per unit modularity defect' $f_m(B)$ of vertex subsets $B$. Intuitively, the following lemma (proof omitted due to space constraints) says that, if you are restricted to parts $B$ with $\delta(B) = 4$, the modularity maximising volume is $\text{vol}(B) = 2\sqrt{2m}$. Moreover, while it would usually be better to take parts with $\delta(B) < 4$ these parts are actually worse (i.e. higher $f_m(B)$ value) if their volumes are too big or too small. The function $f_m(B)$ plays a similar role to the *n-cost* in Proposition 1 of [19].

► **Lemma 3.3.** Assume that $m \ge 1$, $\text{vol}(B) \ge 1$ and define

$$f_m(B) = \frac{\partial(B)}{\text{vol}(B)} + \frac{\text{vol}(B)}{2m}.$$

Then the following properties hold:

0: if $\partial(B) = 0$ and $\text{vol}(B) > 4\sqrt{2m}$ then $f_m(B) > 2\sqrt{2/m}$.

1: if $\partial(B) = 1$ and $\text{vol}(B) > 3.7321\sqrt{2m}$ or $\text{vol}(B) < 0.2679\sqrt{2m}$ then $f_m(B) > 2\sqrt{2/m}$.

2: if $\partial(B) = 2$ and $\text{vol}(B) > 3.4143\sqrt{2m}$ or $\text{vol}(B) < 0.5857\sqrt{2m}$ then $f_m(B) > 2\sqrt{2/m}$.

3: if $\partial(B) = 3$ and $\text{vol}(B) > 3\sqrt{2m}$ or $\text{vol}(B) < \sqrt{2m}$ then $f_m(B) > 2\sqrt{2/m}$.

4: if $\partial(B) = 4$ and $\text{vol}(B) = 2\sqrt{2m}$ then $f_m(B) = 2\sqrt{2/m}$.

5: if $\partial(B) \ge 5$ then $f_m(B) > 2\sqrt{2/m}$.

**Proof of Theorem 3.1.** We give a reduction from AECP. Let $(H, \{a_1, \dots, a_r\})$ be the input to an instance of AECP; we will describe how to construct a graph $G$, where pw($G$) and fvs($G$) are both bounded by a function of $r$, together with an explicit $q_0 \in (0, 1)$ such that $(G, q_0)$ is a yes-instance for MODULARITY if and only if $(H, \{a_1, \dots, a_r\})$ is a yes-instance for AECP.

We may assume without loss of generality that our instance of AECP satisfies all of the conditions of Lemma 3.2.

We define a new graph $G$, obtained from $H$ by adding the following (see Figure 1):

- $\alpha$ new leaves adjacent to each anchor vertex $a_1, \dots, a_r$,

- $\beta$ isolated edges disjoint from $G$, and

- an arbitrary perfect matching on the anchor vertices $a_1, \dots, a_r$,
<figure><img src="image_54.png" /><figcaption>Figure 1 Possible input graph H with anchors $a_1, a_2, a_3, a_4$ and the graph G constructed from it by adding $\alpha$ new leaves adjacent to each anchor, $\beta$ isolated edges and a perfect matching between the anchors.</figcaption></figure>

where the values of $\alpha$ and $\beta$ will be determined later. Notice that, even with these modifications, $G \setminus \{a_1, \dots, a_r\}$ is still a disjoint union of isolated vertices and paths with pendant edges; hence $pw(G) \le r+1$ and $fvs(G) \le r$. We set $m = |E(G)|$ so $m = |E(H)|+\alpha r+\beta+r/2$.

We now define our instance of MODULARITY to be $(G, q_0)$, where

$$q_0 = 1 - \frac{\beta}{m^2} - \frac{2\sqrt{2}(m-\beta)}{m^{3/2}}$$

We now argue that $(G, q_0)$ is a yes-instance if and only if $(H, \{a_1, \dots, a_r\})$ is a yes-instance for AECP. Recall that

$$q^*(G) = 1 - \min_{\mathcal{A}} \sum_{A \in \mathcal{A}} \left( \frac{\partial(A)}{2m} + \frac{\mathrm{vol}(A)^2}{4m^2} \right).$$

and that the partition $\mathcal{A}$ which achieves the minimum in the expression above is exactly the modularity maximal $\mathcal{A}$. In any modularity optimal partition, $\mathcal{A}$, each isolated edge will form its own part: this follows from Facts 1.1 and 1.2. Write $V'$ for vertices of $G$ without the vertices supporting the $\beta$ isolated edges, and let the minimisation be over $\mathcal{A}'$ which are vertex partitions of $V'$. We then have

$$q^*(G) = 1 - \frac{\beta}{m^2} - \min_{\mathcal{A}'} \sum_{A \in \mathcal{A}'} \frac{\partial(A)}{2m} + \frac{\mathrm{vol}(A)^2}{4m^2}.$$

Rearranging, we see that

$$1 - \frac{\beta}{m^2} - q^*(G') = \frac{m-\beta}{m} \min_{\mathcal{A}'} \sum_{A \in \mathcal{A}'} \frac{\mathrm{vol}(A)}{2(m-\beta)} \left( \frac{\partial(A)}{\mathrm{vol}(A)} + \frac{\mathrm{vol}(A)}{2m} \right) \\ = \frac{m-\beta}{m} \min_{\mathcal{A}'} \sum_{A \in \mathcal{A}'} \frac{\mathrm{vol}(A)}{2(m-\beta)} f_m(A) \qquad (2)$$

$$\geq \frac{m-\beta}{m} \min_{A \subseteq V'} f_m(A). \qquad (3)$$

The last inequality holds because $\sum_A \mathrm{vol}(A) = 2(m-\beta)$ and so (2) is a weighted sum of the $f_m(A)$ with total weight one. This, together with the fact that no $A$ has zero volume, also implies that $(2) \ge (3)$ with equality if and only if $f_m(A) = \min_{B \subseteq V'} f_m(B)$ for every $A \in \mathcal{A}'$.
<figure><img src="image_57.png" /><figcaption>Figure 1 Possible input graph H with anchors $a_1, a_2, a_3, a_4$ and the graph G constructed from it by adding $\alpha$ new leaves adjacent to each anchor, $\beta$ isolated edges and a perfect matching between the anchors.</figcaption></figure>

where the values of $\alpha$ and $\beta$ will be determined later. Notice that, even with these modifications, $G \setminus \{a_1, \dots, a_r\}$ is still a disjoint union of isolated vertices and paths with pendant edges; hence $pw(G) \le r+1$ and $fvs(G) \le r$. We set $m = |E(G)|$ so $m = |E(H)|+\alpha r+\beta+r/2$. We now define our instance of MODULARITY to be $(G, q_0)$, where

$$q_0 = 1 - \frac{\beta}{m^2} - \frac{2\sqrt{2}(m - \beta)}{m^{3/2}}$$

We now argue that $(G, q_0)$ is a yes-instance if and only if $(H, \{a_1, \dots, a_r\})$ is a yes-instance for AECP. Recall that

$$q^*(G) = 1 - \min_{\mathcal{A}} \sum_{A \in \mathcal{A}} \left( \frac{\partial(A)}{2m} + \frac{\mathrm{vol}(A)^2}{4m^2} \right).$$

and that the partition $\mathcal{A}$ which achieves the minimum in the expression above is exactly the modularity maximal $\mathcal{A}$. In any modularity optimal partition, $\mathcal{A}$, each isolated edge will form its own part: this follows from Facts 1.1 and 1.2. Write $V'$ for vertices of $G$ without the vertices supporting the $\beta$ isolated edges, and let the minimisation be over $\mathcal{A}'$ which are vertex partitions of $V'$. We then have

$$q^*(G) = 1 - \frac{\beta}{m^2} - \min_{\mathcal{A}'} \sum_{A \in \mathcal{A}'} \frac{\partial(A)}{2m} + \frac{\mathrm{vol}(A)^2}{4m^2}.$$

Rearranging, we see that

$$\begin{align}
1 - \frac{\beta}{m^2} - q^*(G') &= \frac{m - \beta}{m} \min_{\mathcal{A}'} \sum_{A \in \mathcal{A}'} \frac{\mathrm{vol}(A)}{2(m - \beta)} \left( \frac{\partial(A)}{\mathrm{vol}(A)} + \frac{\mathrm{vol}(A)}{2m} \right) \nonumber \\
&= \frac{m - \beta}{m} \min_{\mathcal{A}'} \sum_{A \in \mathcal{A}'} \frac{\mathrm{vol}(A)}{2(m - \beta)} f_m(A) \tag{2}
\end{align}$$

$$\geq \frac{m - \beta}{m} \min_{A \subseteq V'} f_m(A). \qquad (3)$$

The last inequality holds because $\sum_A \mathrm{vol}(A) = 2(m - \beta)$ and so (2) is a weighted sum of the $f_m(A)$ with total weight one. This, together with the fact that no $A$ has zero volume, also implies that $(2) \ge (3)$ with equality if and only if $f_m(A) = \min_{B \subseteq V'} f_m(B)$ for every $A \in \mathcal{A}'$.
9:12 The Parameterised Complexity of Computing the Maximum Modularity of a Graph

Note that, since $\mathcal{A}'$ is the restriction of some modularity optimal partition $\mathcal{A}$ to a connected component of $G$, we may assume that, for all $A \in \mathcal{A}'$, $G[A]$ is connected. Moreover, if $v$ is a pendant vertex adjacent to $u$ then $u$ and $v$ are in the same part in $\mathcal{A}'$; we call a partition with this last property (or, abusing notation, a set that would not violate this condition in a partition) 'pendant-consistent'.

We make the following claim, whose proof is omitted due to space constraints; we write $s = |H|/r$ for the desired part size in our instance of AECP.

► Claim 3.4. Suppose that $\alpha > 32|E(H)|^2$ and that we have $\sqrt{2m} = s + \alpha + 1$. Then:

(a) for any connected, pendant-consistent set $B \subseteq V'$ we have $f_m(B) \ge 2\sqrt{2/m}$, and if $f_m(B) = 2\sqrt{2/m}$ then $B$ contains exactly one anchor and $\text{vol}(B) = 2\sqrt{2m}$;

(b) if $(H, \{a_1, \dots, a_r\})$ is a yes-instance, then there is a vertex partition $\mathcal{A}'$ of $V'$ so that $f_m(A) = 2\sqrt{2/m}$ for all $A \in \mathcal{A}'$;

(c) if there is a vertex partition $\mathcal{A}' = \{A_1, \dots, A_r\}$ of $V'$ so that for all $A_i \in \mathcal{A}$, $f_m(A_i) = 2\sqrt{2/m}$, $A$ is pendant-consistent and $G[A]$ is connected for all $A \in \mathcal{A}'$, then $(H, \{a_1, \dots, a_r\})$ is a yes-instance.

Note that, by Claim 3.4(a) and line (3), we always have

$$q^*(G) \le q_0 = 1 - \frac{\beta}{m^2} - \frac{2\sqrt{2}(m - \beta)}{m^{3/2}}.$$

Hence in particular $(G, q_0)$ is a yes-instance if and only if there is a partition $\mathcal{A}'$ of $V'$ such that $\forall A \in \mathcal{A}'$ $f_m(A) = 2\sqrt{2/m}$.

Claim 3.4(b), together with line (2), implies that, if $(H, \{a_1, \dots, a_r\})$ is a yes-instance, then so is $(G, q_0)$. Conversely, if $(G, q_0)$ is a yes-instance, it follows from Claim 3.4(c), that $(H, \{a_1, \dots, a_r\})$ is a yes-instance.

It remains only to show that we can choose suitable values of $\alpha$ and $\beta$. Set $\alpha$ to be the least integer such that

$$\alpha \ge 32|E(H)|^2, \quad (\alpha + s + 1)^2 > 2|E(H)| + 2\alpha r + r \quad \text{and} \quad \alpha = s + 1 \pmod 2. \quad (4)$$

Recall that $r$ is even. This, along with our parity constraint between $\alpha$ and $s$, implies that $(\alpha + s + 1)^2 - r$ is even. Thus we can choose $\beta$ to be

$$\beta = \frac{1}{2}((\alpha + s + 1)^2 - r) - |E(H)| - \alpha r; \quad (5)$$

note $\beta$ is positive because we set $\alpha$ so that $(\alpha + s + 1)^2 > 2|E(H)| + 2\alpha r + r$. Finally, observe that we do have $\sqrt{2m} = s + \alpha + 1$ because, by the chosen value of $\beta$,

$$m = |E(H)| + \alpha r + \beta + r/2 = (s + \alpha + 1)^2/2.$$

4 Conclusions and Open Problems

We have shown that MODULARITY belongs to FPT when parameterised by the vertex cover number of the input graph, and that the problem is solvable in polynomial time on input graphs whose treewidth or max leaf number is bounded by some fixed constant; we also showed that there is an FPT algorithm, parameterised by treewidth, which computes any constant-factor approximation to the maximum modularity. In contrast with the positive approximation result, we demonstrated that the problem is unlikely to admit an exact FPT when the treewidth is taken to be the parameter, as it is W[1]-hard even when parameterised simultaneously by the treewidth and size of a minimum feedback vertex set for the input graph.
9:12 The Parameterised Complexity of Computing the Maximum Modularity of a Graph

Note that, since $\mathcal{A}'$ is the restriction of some modularity optimal partition $\mathcal{A}$ to a connected component of $G$, we may assume that, for all $A \in \mathcal{A}'$, $G[A]$ is connected. Moreover, if $v$ is a pendant vertex adjacent to $u$ then $u$ and $v$ are in the same part in $\mathcal{A}'$; we call a partition with this last property (or, abusing notation, a set that would not violate this condition in a partition) 'pendant-consistent'.

We make the following claim, whose proof is omitted due to space constraints; we write $s = |H|/r$ for the desired part size in our instance of AECP.

**Claim 3.4.** Suppose that $\alpha > 32|E(H)|^2$ and that we have $\sqrt{2m} = s + \alpha + 1$. Then:

(a) for any connected, pendant-consistent set $B \subseteq V'$ we have $f_m(B) \ge 2\sqrt{2/m}$, and if $f_m(B) = 2\sqrt{2/m}$ then $B$ contains exactly one anchor and $\text{vol}(B) = 2\sqrt{2m}$;

(b) if $(H, \{a_1, \dots, a_r\})$ is a yes-instance, then there is a vertex partition $\mathcal{A}'$ of $V'$ so that $f_m(A) = 2\sqrt{2/m}$ for all $A \in \mathcal{A}'$;

(c) if there is a vertex partition $\mathcal{A}' = \{A_1, \dots, A_r\}$ of $V'$ so that for all $A_i \in \mathcal{A}$, $f_m(A_i) = 2\sqrt{2/m}$, $A$ is pendant-consistent and $G[A]$ is connected for all $A \in \mathcal{A}'$, then $(H, \{a_1, \dots, a_r\})$ is a yes-instance.

Note that, by Claim 3.4(a) and line (3), we always have

$$q^*(G) \le q_0 = 1 - \frac{\beta}{m^2} - \frac{2\sqrt{2}(m - \beta)}{m^{3/2}}.$$

Hence in particular $(G, q_0)$ is a yes-instance if and only if there is a partition $\mathcal{A}'$ of $V'$ such that $\forall A \in \mathcal{A}'$ $f_m(A) = 2\sqrt{2/m}$.

Claim 3.4(b), together with line (2), implies that, if $(H, \{a_1, \dots, a_r\})$ is a yes-instance, then so is $(G, q_0)$. Conversely, if $(G, q_0)$ is a yes-instance, it follows from Claim 3.4(c), that $(H, \{a_1, \dots, a_r\})$ is a yes-instance.

It remains only to show that we can choose suitable values of $\alpha$ and $\beta$. Set $\alpha$ to be the least integer such that

$$\alpha \ge 32|E(H)|^2, \quad (\alpha + s + 1)^2 > 2|E(H)| + 2\alpha r + r \quad \text{and} \quad \alpha = s + 1 \pmod 2. \quad (4)$$

Recall that $r$ is even. This, along with our parity constraint between $\alpha$ and $s$, implies that $(\alpha + s + 1)^2 - r$ is even. Thus we can choose $\beta$ to be

$$\beta = \frac{1}{2}((\alpha + s + 1)^2 - r) - |E(H)| - \alpha r; \quad (5)$$

note $\beta$ is positive because we set $\alpha$ so that $(\alpha + s + 1)^2 > 2|E(H)| + 2\alpha r + r$. Finally, observe that we do have $\sqrt{2m} = s + \alpha + 1$ because, by the chosen value of $\beta$,

$$m = |E(H)| + \alpha r + \beta + r/2 = (s + \alpha + 1)^2/2.$$

4 Conclusions and Open Problems

We have shown that MODULARITY belongs to FPT when parameterised by the vertex cover number of the input graph, and that the problem is solvable in polynomial time on input graphs whose treewidth or max leaf number is bounded by some fixed constant; we also showed that there is an FPT algorithm, parameterised by treewidth, which computes any constant-factor approximation to the maximum modularity. In contrast with the positive approximation result, we demonstrated that the problem is unlikely to admit an exact FPT when the treewidth is taken to be the parameter, as it is W[1]-hard even when parameterised simultaneously by the treewidth and size of a minimum feedback vertex set for the input graph.
We conjecture that our XP algorithm parameterised by max leaf number is not optimal, and that MODULARITY in fact belongs to FPT with respect to this parameterisation. Another natural open question arising from our work is whether our approximation result can be extended to larger classes of graphs, for example those of bounded cliquewidth or bounded expansion.

References

1 J. P. Bagrow. Communities and bottlenecks: Trees and treelike networks have high modularity. *Physical Review E*, 85(6):066118, 2012.

2 V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre. Fast unfolding of communities in large networks. *Journal of Statistical Mechanics: Theory and Experiment*, 2008(10):P10008, 2008.

3 U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, and D. Wagner. On Modularity Clustering. *IEEE Trans. on Knowl. and Data Eng.*, 20(2):172–188, February 2008. doi:10.1109/TKDE.2007.190689.

4 M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. *Parameterized Algorithms*. Springer, Cham, 2015.

5 B. DasGupta and D. Desai. On the complexity of Newman’s community finding approach for biological and social networks. *Journal of Computer and System Sciences*, 79(1):50–67, 2013. doi:10.1016/j.jcss.2012.04.003.

6 F. De Montgolfier, M. Soto, and L. Viennot. Asymptotic modularity of some graph classes. In *Algorithms and Computation*, pages 435–444. Springer, 2011.

7 T. N. Dinh, X. Li, and M. T. Thai. Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits. In *2015 IEEE International Conference on Data Mining*, pages 101–110, November 2015. doi:10.1109/ICDM.2015.139.

8 T. N. Dinh and M. T. Thai. Finding community structure with performance guarantees in scale-free networks. In *Privacy, Security, Risk and Trust (PASSAT) and 2011 IEEE Third International Conference on Social Computing (SocialCom), 2011 IEEE Third International Conference on*, pages 888–891. IEEE, 2011.

9 T. N. Dinh and M. T. Thai. Community Detection in Scale-Free Networks: Approximation Algorithms for Maximizing Modularity. *IEEE Journal on Selected Areas in Communications*, 31(6):997–1006, June 2013. doi:10.1109/JSAC.2013.130602.

10 R. G. Downey and M. R. Fellows. *Fundamentals of Parameterized Complexity*. Springer London, 2013.

11 R. Enciso, M. R. Fellows, J. Guo, I. Kanj, F. Rosamond, and O. Suchý. *What Makes Equitable Connected Partition Easy*, pages 122–133. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. doi:10.1007/978-3-642-11269-0_10.

12 V. Estivill-Castro, M. Fellows, M. Langston, and F. Rosamond. FPT is P-time extremal structure I. In *Algorithms and Complexity in Durham 2005, Proceedings of the first ACID Workshop, volume 4 of Texts in Algorithmics*, pages 1–41. King’s College Publications, 2005.

13 S. Fortunato. Community detection in graphs. *Physics Reports*, 486(3):75–174, 2010.

14 S. Fortunato and D. Hric. Community detection in networks: A user guide. *Physics Reports*, 659:1–44, 2016.

15 I. S. Jutla, L. G. S. Jeub, and P. J. Mucha. A generalized Louvain method for community detection implemented in MATLAB. URL http://netwiki.amath.unc.edu/GenLouvain, 2011.

16 Y. Kawase, T. Matsui, and A. Miyauchi. Additive Approximation Algorithms for Modularity Maximization. In *Seok-Hee Hong, editor, 27th International Symposium on Algorithms*
We conjecture that our XP algorithm parameterised by max leaf number is not optimal, and that MODULARITY in fact belongs to FPT with respect to this parameterisation. Another natural open question arising from our work is whether our approximation result can be extended to larger classes of graphs, for example those of bounded cliquewidth or bounded expansion.

References

1 J. P. Bagrow. Communities and bottlenecks: Trees and treelike networks have high modularity. *Physical Review E*, 85(6):066118, 2012.

2 V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre. Fast unfolding of communities in large networks. *Journal of Statistical Mechanics: Theory and Experiment*, 2008(10):P10008, 2008.

3 U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, and D. Wagner. On Modularity Clustering. *IEEE Trans. on Knowl. and Data Eng.*, 20(2):172–188, February 2008. doi:10.1109/TKDE.2007.190689.

4 M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. *Parameterized Algorithms*. Springer, Cham, 2015.

5 B. DasGupta and D. Desai. On the complexity of Newman’s community finding approach for biological and social networks. *Journal of Computer and System Sciences*, 79(1):50–67, 2013. doi:10.1016/j.jcss.2012.04.003.

6 F. De Montgolfier, M. Soto, and L. Viennot. Asymptotic modularity of some graph classes. In *Algorithms and Computation*, pages 435–444. Springer, 2011.

7 T. N. Dinh, X. Li, and M. T. Thai. Network Clustering via Maximizing Modularity: Approximation Algorithms and Theoretical Limits. In *2015 IEEE International Conference on Data Mining*, pages 101–110, November 2015. doi:10.1109/ICDM.2015.139.

8 T. N. Dinh and M. T. Thai. Finding community structure with performance guarantees in scale-free networks. In *Privacy, Security, Risk and Trust (PASSAT) and 2011 IEEE Third International Conference on Social Computing (SocialCom), 2011 IEEE Third International Conference on*, pages 888–891. IEEE, 2011.

9 T. N. Dinh and M. T. Thai. Community Detection in Scale-Free Networks: Approximation Algorithms for Maximizing Modularity. *IEEE Journal on Selected Areas in Communications*, 31(6):997–1006, June 2013. doi:10.1109/JSAC.2013.130602.

10 R. G. Downey and M. R. Fellows. *Fundamentals of Parameterized Complexity*. Springer London, 2013.

11 R. Enciso, M. R. Fellows, J. Guo, I. Kanj, F. Rosamond, and O. Suchý. *What Makes Equitable Connected Partition Easy*, pages 122–133. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. doi:10.1007/978-3-642-11269-0_10.

12 V. Estivill-Castro, M. Fellows, M. Langston, and F. Rosamond. FPT is P-time extremal structure I. In *Algorithms and Complexity in Durham 2005, Proceedings of the first ACID Workshop, volume 4 of Texts in Algorithmics*, pages 1–41. King’s College Publications, 2005.

13 S. Fortunato. Community detection in graphs. *Physics Reports*, 486(3):75–174, 2010.

14 S. Fortunato and D. Hric. Community detection in networks: A user guide. *Physics Reports*, 659:1–44, 2016.

15 I. S. Jutla, L. G. S. Jeub, and P. J. Mucha. A generalized Louvain method for community detection implemented in MATLAB. URL http://netwiki.amath.unc.edu/GenLouvain, 2011.

16 Y. Kawase, T. Matsui, and A. Miyauchi. Additive Approximation Algorithms for Modularity Maximization. In *Seok-Hee Hong, editor, 27th International Symposium on Algorithms*
9:14 The Parameterised Complexity of Computing the Maximum Modularity of a Graph

and Computation (ISAAC 2016), volume 64 of Leibniz International Proceedings in Informatics (LIPIcs), pages 43:1–43:13, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.ISAAC.2016.43.

17 A. Lancichinetti and S. Fortunato. Limits of modularity maximization in community detection. Physical Review E, 84(6):066122, 2011.

18 D. Lokshtanov. Parameterized Integer Quadratic Programming: Variables and Coefficients. arXiv:1511.00310 [cs.DS], 2015.

19 C. McDiarmid and F. Skerman. Modularity of regular and treelike graphs. Journal of Complex Networks, 5, 2017.

20 C. McDiarmid and F. Skerman. Modularity of Erdős-Rényi Random Graphs. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, volume 1, 2018.

21 C. McDiarmid and F. Skerman. Modularity of Erdős-Rényi random graphs. arXiv:1808.02243 [math.CO], 2018.

22 M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69(2):026113, 2004.

23 M. Porter, J.-P. Onnela, and P. Mucha. Communities in networks. Notices of the AMS, 56(9):1082–1097, 2009.

24 L. O. Prokhorenkova, P. Prałat, and A. Raigorodskii. Modularity of models of complex networks. Electronic Notes in Discrete Mathematics, 61:947–953, 2017.
9:14 The Parameterised Complexity of Computing the Maximum Modularity of a Graph

and Computation (ISAAC 2016), volume 64 of Leibniz International Proceedings in Informatics (LIPIcs), pages 43:1–43:13, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.ISAAC.2016.43.

17 A. Lancichinetti and S. Fortunato. Limits of modularity maximization in community detection. Physical Review E, 84(6):066122, 2011.

18 D. Lokshtanov. Parameterized Integer Quadratic Programming: Variables and Coefficients. arXiv:1511.00310 [cs.DS], 2015.

19 C. McDiarmid and F. Skerman. Modularity of regular and treelike graphs. Journal of Complex Networks, 5, 2017.

20 C. McDiarmid and F. Skerman. Modularity of Erdős-Rényi Random Graphs. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, volume 1, 2018.

21 C. McDiarmid and F. Skerman. Modularity of Erdős-Rényi random graphs. arXiv:1808.02243 [math.CO], 2018.

22 M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69(2):026113, 2004.

23 M. Porter, J.-P. Onnela, and P. Mucha. Communities in networks. Notices of the AMS, 56(9):1082–1097, 2009.

24 L. O. Prokhorenkova, P. Prałat, and A. Raigorodskii. Modularity of models of complex networks. Electronic Notes in Discrete Mathematics, 61:947–953, 2017.
# On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs

Florian Barbero

LIRMM, Université de Montpellier, 161 rue Ada, 34095, Montpellier, France
florian.barbero@lirmm.fr

Lucas Isenmann

LIRMM, Université de Montpellier, 161 rue Ada, 34095, Montpellier, France
lucas.isenmann@lirmm.fr

Jocelyn Thiebaut

LIRMM, Université de Montpellier, 161 rue Ada, 34095, Montpellier, France
jocelyn.thiebaut@lirmm.fr

## Abstract

Numerous problems consisting in identifying vertices in graphs using distances are useful in domains such as network verification and graph isomorphism. Unifying them into a meta-problem may be of main interest. We introduce here a promising solution named DISTANCE IDENTIFYING SET. The model contains IDENTIFYING CODE (IC), LOCATING DOMINATING SET (LD) and their generalizations *r*-IC and *r*-LD where the closed neighborhood is considered up to distance *r*. It also contains METRIC DIMENSION (MD) and its refinement *r*-MD in which the distance between two vertices is considered as infinite if the real distance exceeds *r*. Note that while IC = 1-IC and LD = 1-LD, we have MD = ∞-MD; we say that MD is not *local*.

In this article, we prove computational lower bounds for several problems included in DISTANCE IDENTIFYING SET by providing generic reductions from (PLANAR) HITTING SET to the meta-problem. We focus on two families of problem from the meta-problem: the first one, called *bipartite gifted local*, contains *r*-IC, *r*-LD and *r*-MD for each positive integer *r* while the second one, called 1-layered, contains LD, MD and *r*-MD for each positive integer *r*. We have:

- the 1-layered problems are NP-hard even in bipartite apex graphs,

- the bipartite gifted local problems are NP-hard even in bipartite planar graphs,

- assuming ETH, all these problems cannot be solved in $2^{o(\sqrt{n})}$ when restricted to bipartite planar or apex graph, respectively, and they cannot be solved in $2^{o(n)}$ on bipartite graphs,

- even restricted to bipartite graphs, they do not admit parameterized algorithms in $2^{O(k)} \cdot n^{O(1)}$ except if $W[0] = W[2]$. Here *k* is the solution size of a relevant identifying set.

In particular, METRIC DIMENSION cannot be solved in $2^{o(n)}$ under ETH, answering a question of Hartung in [20].

**2012 ACM Subject Classification** Mathematics of computing → Graph algorithms, Theory of computation → Problems, reductions and completeness

**Keywords and phrases** identifying code, resolving set, metric dimension, distance identifying set, parameterized complexity, W-hierarchy, meta-problem, hitting set

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

**Related Version** The full version of the article can be found in [4], https://arxiv.org/abs/1810.03868.

**Acknowledgements** We want to thank Stéphane Bessy and Anaël Grandjean for their precious advice concerning the correctness of the claims, and the structure of the article.

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

© Florian Barbero, Lucas Isenmann, and Jocelyn Thiebaut;
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. 10; pp. 10:1–10:14

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

LIPICS

Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
# On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs

Florian Barbero

LIRMM, Université de Montpellier, 161 rue Ada, 34095, Montpellier, France
florian.barbero@lirmm.fr

Lucas Isenmann

LIRMM, Université de Montpellier, 161 rue Ada, 34095, Montpellier, France
lucas.isenmann@lirmm.fr

Jocelyn Thiebaut

LIRMM, Université de Montpellier, 161 rue Ada, 34095, Montpellier, France
jocelyn.thiebaut@lirmm.fr

## Abstract

Numerous problems consisting in identifying vertices in graphs using distances are useful in domains such as network verification and graph isomorphism. Unifying them into a meta-problem may be of main interest. We introduce here a promising solution named DISTANCE IDENTIFYING SET. The model contains IDENTIFYING CODE (IC), LOCATING DOMINATING SET (LD) and their generalizations *r*-IC and *r*-LD where the closed neighborhood is considered up to distance *r*. It also contains METRIC DIMENSION (MD) and its refinement *r*-MD in which the distance between two vertices is considered as infinite if the real distance exceeds *r*. Note that while IC = 1-IC and LD = 1-LD, we have MD = ∞-MD; we say that MD is not *local*.

In this article, we prove computational lower bounds for several problems included in DISTANCE IDENTIFYING SET by providing generic reductions from (PLANAR) HITTING SET to the meta-problem. We focus on two families of problem from the meta-problem: the first one, called *bipartite gifted local*, contains *r*-IC, *r*-LD and *r*-MD for each positive integer *r* while the second one, called 1-layered, contains LD, MD and *r*-MD for each positive integer *r*. We have:

- the 1-layered problems are NP-hard even in bipartite apex graphs,

- the bipartite gifted local problems are NP-hard even in bipartite planar graphs,

- assuming ETH, all these problems cannot be solved in $2^{o(\sqrt{n})}$ when restricted to bipartite planar or apex graph, respectively, and they cannot be solved in $2^{o(n)}$ on bipartite graphs,

- even restricted to bipartite graphs, they do not admit parameterized algorithms in $2^{O(k)} \cdot n^{O(1)}$ except if $W[0] = W[2]$. Here *k* is the solution size of a relevant identifying set.

In particular, METRIC DIMENSION cannot be solved in $2^{o(n)}$ under ETH, answering a question of Hartung in [20].

**2012 ACM Subject Classification** Mathematics of computing → Graph algorithms, Theory of computation → Problems, reductions and completeness

**Keywords and phrases** identifying code, resolving set, metric dimension, distance identifying set, parameterized complexity, W-hierarchy, meta-problem, hitting set

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

**Related Version** The full version of the article can be found in [4], https://arxiv.org/abs/1810.03868.

**Acknowledgements** We want to thank Stéphane Bessy and Anaël Grandjean for their precious advice concerning the correctness of the claims, and the structure of the article.

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

© Florian Barbero, Lucas Isenmann, and Jocelyn Thiebaut;
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. 10; pp. 10:1–10:14

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

LIPICS

Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
1 Introduction and Corresponding Works

Problems consisting in identifying each element of a combinatorial structure with a hopefully
small number of elements have been widely investigated. Here, we study a meta identific-
ation problem which generalizes three of the most well-known identification problems in
graphs, namely IDENTIFYING CODE (IC), LOCATING DOMINATING SET (LD) and METRIC
DIMENSION (MD). These problems are used in network verification [3, 5], fault-detection in
networks [22, 28], graph isomorphism [2] or logical definability of graphs [23]. The versions
of these problems in hypergraphs have been studied under different names in [6], [7] and [8].

Given a graph $G$ with vertex set $V$, the classical identifying sets are defined as follows:

- IC: Introduced by Karposky et al. [22], a set C of vertices of G is said to be an *identifying code* if none of the sets $N[v] \cap C$ are empty, for $v \in V$ and they are all distinct.

- LD: Introduced by Slater [25, 26], a set *C* of vertices of *G* is said to be a *locating-dominating set* if none of the sets *N*[*v*] ∩ *C* are empty, for *v* ∈ *V* \ *C* and they are all distinct. When not considering the dominating property (*N*[*v*] ∩ *C* may be empty), these sets have been studied in [2] as distinguishing sets and in [23] as sieves.

- MD: Introduced independently by Harary et al. [18] and Slater [24], a set *C* of vertices of *G* is said to be a *resolving set* if *C* contains one vertex from each connected component of *G* and, for every distinct vertices *u* and *v* of *G*, there exists a vertex *w* of *C* such that *d*(*w*, *u*) ≠ *d*(*w*, *v*). The *metric dimension* of *G* is the minimum size of its resolving sets.

The corresponding minimization problems of the previous identifying sets are defined
as follows: given a graph *G*, compute a suitable set *C* of minimal size, if one exists. In this
paper, we mainly focus on the computational complexity of these minimization problems.

**Known results.** A wide collection of NP-hardness results has been proven for the problems.

For IC and LD, the minimization problems are indeed NP-hard [10, 11]. Charon et al.
showed the NP-hardness when restricted to bipartite graphs [9], while Auger showed it for
planar graphs with arbitrarily large girth [1]. For trees, there exists a linear algorithm [25].

The MD problem is also NP-hard, even when restricted to Gabriel unit disk graphs [17, 21].
Epstein et al. [14] showed that MD is polynomial on several classes as trees, cycles, cographs,
partial wheels, and graphs of bounded cyclomatic number, but it remains NP-hard on split
graphs, bipartite graphs, co-bipartite and line graphs of bipartite graphs. Additionally, Diaz
et al. [12] proved a quite tight separation: the problem is polynomial on outerplanar graphs
whereas it remains NP-hard on bounded degree planar graphs.

In a recent publication, Foucaud et al. [16] also proved the NP-hardness of the three
problems restricted to interval graphs and permutation graphs.

These notions may be considered under the parameterized point of view; see [13] for a
comprehensive study of Fixed Parameter Tractability (FPT). In the following, the parameter
$k$ is chosen as the solution size of a distance identifying set.

For IC and LD, the parameterized problems are clearly FPT since the number of vertices
of a positive instance is bounded by $2^k + k$ ($k$ vertices may characterize $2^k$ neighbors).

Such complexity is not likely to be achievable in the case of MD, since it would imply
$W[2] = \text{FPT} (= W[0])$. Indeed, Hartung et al. [19, 20] showed MD is $W[2]$-hard for bipartite
subcubic graphs. The problem is however FPT on families of graphs with degree $\Delta$ growing
with the number of vertices because the size $k$ of a resolving set must satisfy $\log_3(\Delta) < k$.
Finally, Foucaud et al. [16] provided a FPT algorithm on interval graphs.
1 Introduction and Corresponding Works

Problems consisting in identifying each element of a combinatorial structure with a hopefully
small number of elements have been widely investigated. Here, we study a meta identific-
ation problem which generalizes three of the most well-known identification problems in
graphs, namely IDENTIFYING CODE (IC), LOCATING DOMINATING SET (LD) and METRIC
DIMENSION (MD). These problems are used in network verification [3, 5], fault-detection in
networks [22, 28], graph isomorphism [2] or logical definability of graphs [23]. The versions
of these problems in hypergraphs have been studied under different names in [6], [7] and [8].

Given a graph $G$ with vertex set $V$, the classical identifying sets are defined as follows:

- IC: Introduced by Karposky et al. [22], a set C of vertices of G is said to be an *identifying code* if none of the sets $N[v] \cap C$ are empty, for $v \in V$ and they are all distinct.

- LD: Introduced by Slater [25, 26], a set *C* of vertices of *G* is said to be a *locating-dominating set* if none of the sets *N*[*v*] ∩ *C* are empty, for *v* ∈ *V* \ *C* and they are all distinct. When not considering the dominating property (*N*[*v*] ∩ *C* may be empty), these sets have been studied in [2] as distinguishing sets and in [23] as sieves.

- MD: Introduced independently by Harary et al. [18] and Slater [24], a set *C* of vertices of *G* is said to be a *resolving set* if *C* contains one vertex from each connected component of *G* and, for every distinct vertices *u* and *v* of *G*, there exists a vertex *w* of *C* such that *d*(*w*, *u*) ≠ *d*(*w*, *v*). The *metric dimension* of *G* is the minimum size of its resolving sets.

The corresponding minimization problems of the previous identifying sets are defined
as follows: given a graph *G*, compute a suitable set *C* of minimal size, if one exists. In this
paper, we mainly focus on the computational complexity of these minimization problems.

**Known results.** A wide collection of NP-hardness results has been proven for the problems.

For IC and LD, the minimization problems are indeed NP-hard [10, 11]. Charon et al.
showed the NP-hardness when restricted to bipartite graphs [9], while Auger showed it for
planar graphs with arbitrarily large girth [1]. For trees, there exists a linear algorithm [25].

The MD problem is also NP-hard, even when restricted to Gabriel unit disk graphs [17, 21].
Epstein et al. [14] showed that MD is polynomial on several classes as trees, cycles, cographs,
partial wheels, and graphs of bounded cyclomatic number, but it remains NP-hard on split
graphs, bipartite graphs, co-bipartite and line graphs of bipartite graphs. Additionally, Diaz
et al. [12] proved a quite tight separation: the problem is polynomial on outerplanar graphs
whereas it remains NP-hard on bounded degree planar graphs.

In a recent publication, Foucaud et al. [16] also proved the NP-hardness of the three
problems restricted to interval graphs and permutation graphs.

These notions may be considered under the parameterized point of view; see [13] for a
comprehensive study of Fixed Parameter Tractability (FPT). In the following, the parameter
$k$ is chosen as the solution size of a distance identifying set.

For IC and LD, the parameterized problems are clearly FPT since the number of vertices
of a positive instance is bounded by $2^k + k$ ($k$ vertices may characterize $2^k$ neighbors).

Such complexity is not likely to be achievable in the case of MD, since it would imply
$W[2] = \text{FPT} (= W[0])$. Indeed, Hartung et al. [19, 20] showed MD is $W[2]$-hard for bipartite
subcubic graphs. The problem is however FPT on families of graphs with degree $\Delta$ growing
with the number of vertices because the size $k$ of a resolving set must satisfy $\log_3(\Delta) < k$.
Finally, Foucaud et al. [16] provided a FPT algorithm on interval graphs.
<table><caption>Figure 1 The computational lower bounds implied by our generic reductions.</caption><thead><tr><th></th><th>1-layered problems</th><th>r-local 0-layered problems</th><th>r-local problems</th></tr></thead><tbody><tr><td>PLANAR HITTING SET with ETH</td><td>NP-hard on bipartite apex graphs</td><td>NP-hard on bipartite planar graphs</td><td>(bipartite) planar gadget ⇒ NP-hard on (bipartite) planar graphs</td></tr><tr><td>HITTING SET with ETH with W[2] ≠ W[0]</td><td>no algorithm running in 2<sup>O(√n)</sup></td><td>no algorithm running in 2<sup>O(n)</sup> for (bipartite) graphs. no parameterized algorithm in 2<sup>O(k)</sup> · n<sup>O(1)</sup> for (bipartite) graphs.</td><td>time for relevant classes of graphs.</td></tr></tbody></table>

**Our contributions.** In order to unify the previous minimization problems, we introduce the concept of distance identifying functions. Given a distance identifying function $f$ and a value $r$ as a positive integer or infinity, the DISTANCE IDENTIFYING SET meta-problem consists in finding a minimal sized $r$-dominating set which distinguishes every couple of vertices of an input graph thanks to the function $f$. Here, we mainly focus on two natural subfamilies of problems of DISTANCE IDENTIFYING SET named *local*, in which a vertex cannot discern the vertices outside of its $i$-neighborhood, for $i$ a fixed positive integer, and 1-layered, where a vertex is able to separate its open neighborhood from the distant vertices.

With this approach, we obtain several computational lower bounds for problems included in DISTANCE IDENTIFYING SET by providing generic reductions from (PLANAR) HITTING SET to the meta-problem. The reductions rely on the set/element-gadget technique, the noteworthy adaptation of the clause/variable-gadget technique from SAT to HITTING SET.

As we provide a 1-layered generic gadget, the 1-layered reductions operate without condition. For local problems, the existence of a local gadget is not always guaranteed. Thus, a local reduction operates only if a local gadget is provided. However, the local planar reduction is slightly more efficient than its 1-layered counterpart: it indeed implies computational lower bounds for planar graphs whereas the 1-layered reduction requires an auxiliary apex, limiting the consequences to apex graphs.

The reductions in general graphs are designed to exploit the W[2]-hardness of HITTING SET parameterized by the solution size $k_{HS}$ of an hitting set, hereby using:

**Theorem 1 (folklore).** Let $n_{HS}$ and $m_{HS}$ be the number of elements and sets of an HITTING SET instance, and $k_{HS}$ be its solution size. A parameterized problem with parameter $k$ admitting a reduction from HITTING SET verifying $k = O(k_{HS} + \log(n_{HS} + m_{HS}))$ does not have a parameterized algorithm running in $2^{O(k)} \cdot n^{O(1)}$ time except if W[2] = FPT.

**Proof.** Given a reduction from HITTING SET to a parameterized problem $\Pi$ such that the reduced parameter satisfies $k = O(k_{HS} + \log(n_{HS} + m_{HS}))$ and the size of the reduced instance verifies $n = (n_{HS} + m_{HS})^{O(1)}$, an algorithm for $\Pi$ of running time $2^{O(k)} \cdot n^{O(1)}$ is actually an algorithm for HITTING SET of running time $2^{O(k_{HS})} \cdot (n_{HS} + m_{HS})^{O(1)}$, meaning that HITTING SET is FPT, a contradiction to its W[2]-hardness (otherwise W[2] = FPT). ◀

Hence, as each gadget contributes to the resulting solution size of a distance identifying set, we set up a binary compression of the gadgets to limit their number to the logarithm order. From the best of our knowledge, this merging gadgets technique has never been employed.

The organization of the paper is as follows. After a short reminder of the computational properties of HITTING SET, Section 2 contains the definitions of distance identifying functions and sets, allowing us to precise the computation lower bounds we obtain. Section 3 designs
<table><caption>Figure 1 The computational lower bounds implied by our generic reductions.</caption><thead><tr><th></th><th>1-layered problems</th><th>r-local 0-layered problems</th><th>r-local problems</th></tr></thead><tbody><tr><td>PLANAR HITTING SET with ETH</td><td>NP-hard on bipartite apex graphs</td><td>NP-hard on bipartite planar graphs</td><td>(bipartite) planar gadget ⇒ NP-hard on (bipartite) planar graphs</td></tr><tr><td>HITTING SET with ETH with W[2] ≠ W[0]</td><td>no algorithm running in 2<sup>O(√n)</sup></td><td>no algorithm running in 2<sup>O(n)</sup> for (bipartite) graphs. no parameterized algorithm in 2<sup>O(k) · n<sup>O(1)</sup></sup> for (bipartite) graphs.</td><td>time for relevant classes of graphs.</td></tr></tbody></table>

**Our contributions.** In order to unify the previous minimization problems, we introduce the concept of distance identifying functions. Given a distance identifying function $f$ and a value $r$ as a positive integer or infinity, the DISTANCE IDENTIFYING SET meta-problem consists in finding a minimal sized $r$-dominating set which distinguishes every couple of vertices of an input graph thanks to the function $f$. Here, we mainly focus on two natural subfamilies of problems of DISTANCE IDENTIFYING SET named *local*, in which a vertex cannot discern the vertices outside of its $i$-neighborhood, for $i$ a fixed positive integer, and 1-layered, where a vertex is able to separate its open neighborhood from the distant vertices.

With this approach, we obtain several computational lower bounds for problems included in DISTANCE IDENTIFYING SET by providing generic reductions from (PLANAR) HITTING SET to the meta-problem. The reductions rely on the set/element-gadget technique, the noteworthy adaptation of the clause/variable-gadget technique from SAT to HITTING SET.

As we provide a 1-layered generic gadget, the 1-layered reductions operate without condition. For local problems, the existence of a local gadget is not always guaranteed. Thus, a local reduction operates only if a local gadget is provided. However, the local planar reduction is slightly more efficient than its 1-layered counterpart: it indeed implies computational lower bounds for planar graphs whereas the 1-layered reduction requires an auxiliary apex, limiting the consequences to apex graphs.

The reductions in general graphs are designed to exploit the W[2]-hardness of HITTING SET parameterized by the solution size $k_{HS}$ of an hitting set, hereby using:

**Theorem 1 (folklore).** Let $n_{HS}$ and $m_{HS}$ be the number of elements and sets of an HITTING SET instance, and $k_{HS}$ be its solution size. A parameterized problem with parameter $k$ admitting a reduction from HITTING SET verifying $k = O(k_{HS} + \log(n_{HS} + m_{HS}))$ does not have a parameterized algorithm running in $2^{O(k) \cdot n_{HS}}$ time except if $W[2] = \text{FPT}$.

**Proof.** Given a reduction from HITTING SET to a parameterized problem $\Pi$ such that the reduced parameter satisfies $k = O(k_{HS} + \log(n_{HS} + m_{HS}))$ and the size of the reduced instance verifies $n = (n_{HS} + m_{HS})^{O(1)}$, an algorithm for $\Pi$ of running time $2^{O(k) \cdot n_{HS}}$ is actually an algorithm for HITTING SET of running time $2^{O(k_{HS}) \cdot (n_{HS} + m_{HS})^{O(1)}}$, meaning that HITTING SET is FPT, a contradiction to its W[2]-hardness (otherwise $W[2] = \text{FPT}$). ◀

Hence, as each gadget contributes to the resulting solution size of a distance identifying set, we set up a binary compression of the gadgets to limit their number to the logarithm order. From the best of our knowledge, this merging gadgets technique has never been employed.

The organization of the paper is as follows. After a short reminder of the computational properties of HITTING SET, Section 2 contains the definitions of distance identifying functions and sets, allowing us to precise the computation lower bounds we obtain. Section 3 designs
10:4 On the Distance Identifying Set Meta-Problem

the supports of the reductions as *distance identifying graphs* and *compressed graph*. Finally,
the gadgets needed for the reductions to apply are given in Section 4.

2 Definition of the Meta-Problem and Related Concepts

**2.1 Preliminaries**

**Notations.** Throughout the paper, we consider simple non oriented graphs.

Given a positive integer $n$, the set of positive integers smaller than $n$ is denoted by $\llbracket n\rrbracket$. By extension, we define $\llbracket\infty\rrbracket = \mathbb{N}_{>0} \cup \{\infty\}$. Given two vertices $u, v$ of a graph $G$, the distance between $u$ and $v$ corresponds to the number of vertices in the shortest path between $u$ and $v$ and is denoted $d(u, v)$. The *open neighborhood of* $u$ is denoted by $N(u)$, its *closed neighborhood* is $N[u] = N(u) \cup \{u\}$, and for a value $r \in \llbracket\infty\rrbracket$, the *r-neighborhood of* $u$ is $N_r[u]$, that is the set of vertices at distance less than $r+1$ of $u$. For $r = \infty$, the $\infty$-neighborhood of $u$ is the set of vertices in the same connected component than $u$. We recall that a subset $D$ of $V$ is called a $r$-dominating set of $G$ if for all vertices $u$ of $V$, the set $N_r[u] \cap D$ is non-empty. Thus an $\infty$-dominating set of $G$ contains at least a vertex for each connected component of $G$.

Given two subsets $X$ and $Y$ of $V$, the distance $d(X, Y)$ corresponds to the value $d(X, Y) = \min\{d(x, y) \mid x \in X, y \in Y\}$. For a vertex $u$, we will also use $d(u, X)$ and $d(X, u)$, defined similarly. The symmetric difference between $X$ and $Y$ is denoted by $X \Delta Y$, and the 2-combination of a set $X$ is denoted $\mathcal{P}_2(X)$

Given two graphs $G = (V_G, E_G)$ and $H = (V_H, E_H)$, $H$ is an *induced subgraph of* $G$ if $V_H \subseteq V_G$ and for all vertices $u$ and $v$ of $V_H$, $(u, v) \in E_G$ if and only if $(u, v) \in E_H$. We denote $H = G[V_H]$ and $V_G \setminus V_H$ by $V_G \setminus H$. Symmetrically, $G$ is an *induced supergraph of* $H$.

**The (Planar) Hitting Set problem**

Consider a universe of $n$ elements denoted $\Omega = \{u_i \mid i \in \llbracket n\rrbracket\}$ and a set of $m$ non-empty subsets of $\Omega$ denoted $S = \{S_i \mid i \in \llbracket m\rrbracket\}$ such that every element belongs to at least a subset.
Then, a subset of $\Omega$ intersecting every set of $S$ is called an *hitting set of S*:

HITTING SET

**Input:** A universe $\Omega$ and a set $S$ of non-empty subsets of $\Omega$ whose union covers $\Omega$.

**Output:** A minimal-sized hitting set $C$ of $S$, i.e. a subset of $\Omega$ satisfying $\forall S_i \in S, S_i \cap C \neq \emptyset$.

The parameterized version HITTING SET(k) decides if there exists a hitting set of size k.

► **Theorem 2** (R.G. Downey and M.R Fellows [13]). HITTING SET cannot be solved in $2^{o(n)}$ time under ETH even if $m = O(n)$. Moreover, HITTING SET(k) is W[2]-hard.

HITTING SET may be translated into a dominating problem on bipartite graphs. Given an instance $(\Omega, S)$ of HITTING SET, let us define $\phi(\Omega, S) = (V_{\Omega} \cup V_{S}, E)$ as the bipartite graph of size $n+m$ such that for each $i \in \llbracket n\rrbracket$, there exists a vertex $v_i^{\Omega}$ in $V_{\Omega}$, for each $j \in \llbracket m\rrbracket$, there exists a vertex $v_j^S$ in $V_S$, and the edge $(v_i^{\Omega}, v_j^S)$ is present in $E$ if and only if the element $u_i$ belongs to the subset $S_j$. Henceforth, a hitting set of $S$ is equivalent to a subset $C$ of $V_{\Omega}$ that dominates $V_S$. We call $\phi(\Omega, S)$ the associated graph of $(\Omega, S)$:

PLANAR HITTING SET

**Input:** An instance $(\Omega, S)$ of HITTING SET such that $\phi(\Omega, S)$ is planar.

**Output:** A hitting set $C$ of $S$ of minimal size.

We also consider the parameterized version PLANAR HITTING SET(k) of the latter problem.
10:4 On the Distance Identifying Set Meta-Problem

the supports of the reductions as *distance identifying graphs* and *compressed graph*. Finally,
the gadgets needed for the reductions to apply are given in Section 4.

2 Definition of the Meta-Problem and Related Concepts

**2.1 Preliminaries**

**Notations.** Throughout the paper, we consider simple non oriented graphs.

Given a positive integer $n$, the set of positive integers smaller than $n$ is denoted by $\llbracket n \rrbracket$. By extension, we define $\llbracket \infty \rrbracket = \mathbb{N}_{>0} \cup \{\infty\}$. Given two vertices $u, v$ of a graph $G$, the distance between $u$ and $v$ corresponds to the number of vertices in the shortest path between $u$ and $v$ and is denoted $d(u, v)$. The *open neighborhood of* $u$ is denoted by $N(u)$, its *closed neighborhood* is $N[u] = N(u) \cup \{u\}$, and for a value $r \in \llbracket \infty \rrbracket$, the *r-neighborhood of* $u$ is $N_r[u]$, that is the set of vertices at distance less than $r+1$ of $u$. For $r = \infty$, the $\infty$-neighborhood of $u$ is the set of vertices in the same connected component than $u$. We recall that a subset $D$ of $V$ is called a $r$-dominating set of $G$ if for all vertices $u$ of $V$, the set $N_r[u] \cap D$ is non-empty. Thus an $\infty$-dominating set of $G$ contains at least a vertex for each connected component of $G$.

Given two subsets $X$ and $Y$ of $V$, the distance $d(X, Y)$ corresponds to the value $d(X, Y) = \min\{d(x, y) \mid x \in X, y \in Y\}$. For a vertex $u$, we will also use $d(u, X)$ and $d(X, u)$, defined similarly. The symmetric difference between $X$ and $Y$ is denoted by $X \Delta Y$, and the 2-combination of a set $X$ is denoted $\mathcal{P}_2(X)$

Given two graphs $G = (V_G, E_G)$ and $H = (V_H, E_H)$, $H$ is an *induced subgraph of* $G$ if $V_H \subseteq V_G$ and for all vertices $u$ and $v$ of $V_H$, $(u, v) \in E_G$ if and only if $(u, v) \in E_H$. We denote $H = G[V_H]$ and $V_G \setminus V_H$ by $V_G \setminus H$. Symmetrically, $G$ is an *induced supergraph of* $H$.

**The (Planar) Hitting Set problem**

Consider a universe of $n$ elements denoted $\Omega = \{u_i \mid i \in \llbracket n \rrbracket\}$ and a set of $m$ non-empty subsets of $\Omega$ denoted $S = \{S_i \mid i \in \llbracket m \rrbracket\}$ such that every element belongs to at least a subset.
Then, a subset of $\Omega$ intersecting every set of $S$ is called an *hitting set of S*:

HITTING SET

**Input:** A universe $\Omega$ and a set $S$ of non-empty subsets of $\Omega$ whose union covers $\Omega$.

**Output:** A minimal-sized hitting set $C$ of $S$, i.e. a subset of $\Omega$ satisfying $\forall S_i \in S, S_i \cap C \neq \emptyset$.

The parameterized version HITTING SET(k) decides if there exists a hitting set of size k.

► **Theorem 2** (R.G. Downey and M.R Fellows [13]). HITTING SET cannot be solved in $2^{o(n)}$ time under ETH even if $m = O(n)$. Moreover, HITTING SET(k) is W[2]-hard.

HITTING SET may be translated into a dominating problem on bipartite graphs. Given an instance $(\Omega, S)$ of HITTING SET, let us define $\phi(\Omega, S) = (V_{\Omega} \cup V_{S}, E)$ as the bipartite graph of size $n+m$ such that for each $i \in \llbracket n \rrbracket$, there exists a vertex $v_i^{\Omega}$ in $V_{\Omega}$, for each $j \in \llbracket m \rrbracket$, there exists a vertex $v_j^S$ in $V_S$, and the edge $(v_i^{\Omega}, v_j^S)$ is present in $E$ if and only if the element $u_i$ belongs to the subset $S_j$. Henceforth, a hitting set of $S$ is equivalent to a subset $C$ of $V_{\Omega}$ that dominates $V_S$. We call $\phi(\Omega, S)$ the associated graph of $(\Omega, S)$:

PLANAR HITTING SET

**Input:** An instance $(\Omega, S)$ of HITTING SET such that $\phi(\Omega, S)$ is planar.

**Output:** A hitting set $C$ of $S$ of minimal size.

We also consider the parameterized version PLANAR HITTING SET(k) of the latter problem.
**► Theorem 3 (folklore).** *There exists a reduction from SAT to PLANAR HITTING SET(n) producing associated graphs of quadratic size in the number n of variables of the instances of SAT. Thus PLANAR HITTING SET cannot be solved in 2<sup>o(√n)</sup> under ETH even if m = O(n).*

**Sketch of proof.** A linear reduction from SAT to HITTING SET is known. To guarantee the planarity of $\phi(\Omega, \mathcal{S})$, we apply the reduction on a restriction of SAT named SEPARATE SIMPLE PLANAR SAT which is not solvable in 2<sup>o(\sqrt{n})</sup> under ETH. See [27]. ▼

## 2.2 The Distance Identifying Set meta-problem

Given a graph $G = (V, E)$ and $r \in [\infty]$, the classical identifying sets may be rewritten:

- r-IC: a subset $C$ of $V$ is a $r$-identifying code of $G$ if it is an $r$-dominating set and for every distinct vertices $u, v$ of $V$, a vertex $w$ in $C$ verifies $w \in N_r[u] \Delta N_r[v]$.

- r-LD: a subset $C$ of $V$ is a $r$-locating dominating set of $G$ if it is an $r$-dominating set and for every distinct vertices $u, v$ of $V$, a vertex $w$ in $C$ verifies $w \in (N_r[u] \Delta N_r[v]) \cup \{u, v\}$.

- r-MD: a subset $C$ of $V$ is a $r$-resolving set of $G$ if it is an $r$-dominating set and for every distinct vertices $u, v$ of $V$, a vertex $w$ in $C$ verifies $w \in N_r[u] \cup N_r[v]$ and $d(u, w) \neq d(v, w)$.

A pattern clearly appears: the previous identifying sets only deviate on the criterion that the vertex $w$ must verify. The pivotal idea is to consider an abstract version of the criterion which does not depend on the input graph. Hence:

**► Definition 4 (identifying function).** A function $f$ of type: $G \to (V \times \mathcal{P}_2(V)) \to \{\text{true, false}\}$, is called an *identifying function*. Given three vertices $u, v$ and $w$ of a graph $G$ such that $u \neq v$, we write $f_G[w](u, v)$ to get the resulting boolean. The notation $\mathcal{P}_2(V)$ implies that $f_G$ is symmetric, that is $f_G[w](u, v) = f_G[w](v, u)$.

We need to require some useful properties on identifying functions to produce generic results. By mimicking the classical identifying sets, the main property we consider is that a vertex cannot distinguish two vertices at the same distance from it. Then:

**► Definition 5 (distance function).** A distance identifying function $f$ is an identifying function such that for every graph $G$ and all vertices $u, v$ and $w$ of $G$ with $u \neq v$:

($\alpha$) $f_G[w](u, v)$ is false when $d(u, w) = d(v, w)$.

Besides this mandatory criterion, we suggest two paradigms related to the neighborhood of a vertex. Let $i \in [\infty]$. First, we may restrain the range of a vertex to its $i$-neighborhood: a vertex should not distinguish two vertices if they do not lie in its $i$-neighborhood but it should always distinguish them whenever exactly one of them lies to that $i$-neighborhood. Reciprocally, we may ensure that a vertex could distinguish the vertices of its $i$-neighborhood: a vertex should distinguish a vertex belonging to its $i$-neighborhood from all the other vertices, assuming the distances are different. Formally, we have:

**► Definition 6 (i-local function).** For $i \in [\infty]$, an $i$-local identifying function $f$ is an identifying function such that for every graph $G$ and all vertices $u, v, w$ of $G$ with $u \neq v$:

($\beta_1$) $f_G[w](u, v)$ is true when $d(u, w) \le i < d(v, w)$ or, symmetrically, $d(v, w) \le i < d(u, w)$.

($\beta_2$) $f_G[w](u, v)$ is false when $i < \min\{d(u, w), d(v, w)\}$.

**► Definition 7 (i-layered function).** For $i \in [\infty]$, an $i$-layered identifying function $f$ is an identifying function such that for every graph $G$ and all vertices $u, v, w$ of $G$ with $u \neq v$:

($\gamma$) $f_G[w](u, v)$ is true when $\min\{d(u, w), d(v, w)\} \le i$ and $d(u, w) \neq d(v, w)$.
**► Theorem 3 (folklore).** *There exists a reduction from SAT to PLANAR HITTING SET(n) producing associated graphs of quadratic size in the number n of variables of the instances of SAT. Thus PLANAR HITTING SET cannot be solved in 2<sup>o(√n)</sup> under ETH even if m = O(n).*

**Sketch of proof.** A linear reduction from SAT to HITTING SET is known. To guarantee the planarity of $\phi(\Omega, \mathcal{S})$, we apply the reduction on a restriction of SAT named SEPARATE SIMPLE PLANAR SAT which is not solvable in 2<sup>o(√n)</sup> under ETH. See [27]. ▼

## 2.2 The Distance Identifying Set meta-problem

Given a graph $G = (V, E)$ and $r \in [\infty]$, the classical identifying sets may be rewritten:

- r-IC: a subset $C$ of $V$ is a $r$-identifying code of $G$ if it is an $r$-dominating set and for every distinct vertices $u, v$ of $V$, a vertex $w$ in $C$ verifies $w \in N_r[u] \Delta N_r[v]$.

- r-LD: a subset $C$ of $V$ is a $r$-locating dominating set of $G$ if it is an $r$-dominating set and for every distinct vertices $u, v$ of $V$, a vertex $w$ in $C$ verifies $w \in (N_r[u] \Delta N_r[v]) \cup \{u, v\}$.

- r-MD: a subset $C$ of $V$ is a $r$-resolving set of $G$ if it is an $r$-dominating set and for every distinct vertices $u, v$ of $V$, a vertex $w$ in $C$ verifies $w \in N_r[u] \cup N_r[v]$ and $d(u, w) \neq d(v, w)$.

A pattern clearly appears: the previous identifying sets only deviate on the criterion that the vertex $w$ must verify. The pivotal idea is to consider an abstract version of the criterion which does not depend on the input graph. Hence:

**► Definition 4 (identifying function).** A function $f$ of type: $G \to (V \times \mathcal{P}_2(V)) \to \{\text{true, false}\}$, is called an *identifying function*. Given three vertices $u, v$ and $w$ of a graph $G$ such that $u \neq v$, we write $f_G[w](u, v)$ to get the resulting boolean. The notation $\mathcal{P}_2(V)$ implies that $f_G$ is symmetric, that is $f_G[w](u, v) = f_G[w](v, u)$.

We need to require some useful properties on identifying functions to produce generic results. By mimicking the classical identifying sets, the main property we consider is that a vertex cannot distinguish two vertices at the same distance from it. Then:

**► Definition 5 (distance function).** A distance identifying function $f$ is an identifying function such that for every graph $G$ and all vertices $u, v$ and $w$ of $G$ with $u \neq v$:

($\alpha$) $f_G[w](u, v)$ is false when $d(u, w) = d(v, w)$.

Besides this mandatory criterion, we suggest two paradigms related to the neighborhood of a vertex. Let $i \in [\infty]$. First, we may restrain the range of a vertex to its *i*-neighborhood: a vertex should not distinguish two vertices if they do not lie in its *i*-neighborhood but it should always distinguish them whenever exactly one of them lies to that *i*-neighborhood. Reciprocally, we may ensure that a vertex could distinguish the vertices of its *i*-neighborhood: a vertex should distinguish a vertex belonging to its *i*-neighborhood from all the other vertices, assuming the distances are different. Formally, we have:

**► Definition 6 (i-local function).** For $i \in [\infty]$, an *i*-local identifying function $f$ is an identifying function such that for every graph $G$ and all vertices $u, v, w$ of $G$ with $u \neq v$:

($\beta_1$) $f_G[w](u, v)$ is true when $d(u, w) \le i < d(v, w)$ or, symmetrically, $d(v, w) \le i < d(u, w)$.

($\beta_2$) $f_G[w](u, v)$ is false when $i < \min\{d(u, w), d(v, w)\}$.

**► Definition 7 (i-layered function).** For $i \in [\infty]$, an *i*-layered identifying function $f$ is an identifying function such that for every graph $G$ and all vertices $u, v, w$ of $G$ with $u \neq v$:

($\gamma$) $f_G[w](u, v)$ is true when $\min\{d(u, w), d(v, w)\} \le i$ and $d(u, w) \neq d(v, w)$.
10:6 On the Distance Identifying Set Meta-Problem

In the following, given an identifying function $f$ and three vertices $u, v, w$ of a graph $G$, we say that $w$ *f*-distinguishes $u$ and $v$ if and only if $f_G[w](u, v)$ is true. By extension, given three vertex sets $C, X$ and $Y$ of $G$, we say that $C$ *f*-distinguishes $X$ and $Y$ if for every $u$ in $X$ and $v$ in $Y$, either $u = v$ or there exists $w$ in $C$ verifying $f_G[w](u, v)$. Finally, a graph $G$ of vertex set $V$ is *f*-distinguished by $C$ when $C$ *f*-distinguishes $V$ and $V$.

We are now ready to define the DISTANCE IDENTIFYING SET meta-problem.

**Definition 8** ((*f*,*r*)-distance identifying set). For a distance identifying function *f* and *r* ∈ [[∞]], a (*f*,*r*)-distance identifying set of a graph *G* is an *r*-dominating set of *G* that *f*-distinguishes *G*.

DISTANCE IDENTIFYING SET

**Input:** A distance identifying function $f$ and $r \in [\infty]$. A graph $G$.

**Output:** A $(f, r)$-distance identifying set of $G$ of minimal size, if one exists.

Given a distance identifying function $f$ and $r \in [\infty]$ as inputs of the meta-problem, the resulting problem is called (*f*,*r*)-DISTANCE IDENTIFYING SET and denoted (*f*,*r*)-DIS. The problem (*f*,*r*)-DIS is said to be *i*-layered when the function $f$ is *i*-layered, and it is said to be *i*-local when $f$ is *i*-local and $r = i$. A problem is *local* if it is *i*-local for an integer $i$. Recall that our local reductions need a local gadget to operate: the subfamilies of local problems admitting a (bipartite) local gadget is called (bipartite) *gifted local*. We do not need to define *gifted 1-layered* as every 1-layered problem admits a 1-layered gadget. We also consider the parameterized version DISTANCE IDENTIFYING SET($k$).

2.3 Detailed Computational Lower Bounds

Using the DISTANCE IDENTIFYING SET meta-problem, we get the following lower bounds:

**Theorem 9.** For each 1-layered distance identifying function $f$ and every $r \in [\infty]$, the (*f*,*r*)-DISTANCE IDENTIFYING SET problem restricted to bipartite apex graphs is NP-hard, and does not admit an algorithm running in $2^{O(\sqrt{n})}$ time under ETH.

**Theorem 10.** The (bipartite) gifted local problems restricted to (bipartite) planar graphs are NP-hard, and do not admit an algorithm running in $2^{O(\sqrt{n})}$ time under ETH.

**Theorem 11.** For each $r$-local 0-layered distance identifying function $f$, $(f,r)$-DIS restricted to bipartite planar graphs is NP-hard, and cannot be solved in $2^{O(\sqrt{n})}$ under ETH.

**Theorem 12.** Let $f, g$ and $h$ be distance identifying functions such that $f$ is 1-layered, $g$ is $q$-local 0-layered and $h$ is $p$-local and admits a local (bipartite) gadget. Let $r \in [\infty]$. The $(f,r)$-, $(g,q)$- and $(h,p)$- DIS problems are NP-hard, and do not admit:

- algorithms running in $2^{o(n)}$ time, except if ETH fails,

- parameterized algorithms running in $2^{O(k)} \cdot n^{O(1)}$ time, except if $W[2] = \text{FPT}$.

The parameter $k$ denotes here the solution size of a relevant distance identifying set.

All bounds still hold in the bipartite case (whenever the gadget associated with $h$ is bipartite).

As a side result, the 1-layered general reduction answers a question of Hartung in [20]:

**Corollary 13.** Under ETH, METRIC DIMENSION cannot be solved in $2^{o(n)}$.

Finally, notice that the parameterized lower bound from Theorem 12 may be complemented by an elementary upper bound inspired from the kernel of IC and LD of size $2^k + k$:

**Proposition 14.** For every $r$-local distance identifying function $f$, the $(f,r)$-DISTANCE IDENTIFYING SET problem has a kernel of size $(r+1)^k + k$ where $k$ is the solution size. Therefore, it admits a naive parameterized algorithm running in $O(n^{k+3}) \in O^*(r^{k^2})$ time.
10:6 On the Distance Identifying Set Meta-Problem

In the following, given an identifying function $f$ and three vertices $u, v, w$ of a graph $G$, we say that $w$ *f*-distinguishes $u$ and $v$ if and only if $f_G[w](u, v)$ is true. By extension, given three vertex sets $C, X$ and $Y$ of $G$, we say that $C$ *f*-distinguishes $X$ and $Y$ if for every $u$ in $X$ and $v$ in $Y$, either $u = v$ or there exists $w$ in $C$ verifying $f_G[w](u, v)$. Finally, a graph $G$ of vertex set $V$ is *f*-distinguished by $C$ when $C$ *f*-distinguishes $V$ and $V$.

We are now ready to define the DISTANCE IDENTIFYING SET meta-problem.

**Definition 8** ((*f*, *r*)-distance identifying set). For a distance identifying function *f* and *r* ∈ [[∞]], a (*f*, *r*)-distance identifying set of a graph *G* is an *r*-dominating set of *G* that *f*-distinguishes *G*.

DISTANCE IDENTIFYING SET

**Input:** A distance identifying function $f$ and $r \in [\infty]$. A graph $G$.

**Output:** A $(f, r)$-distance identifying set of $G$ of minimal size, if one exists.

Given a distance identifying function $f$ and $r \in [\infty]$ as inputs of the meta-problem, the resulting problem is called (*f*, *r*)-DISTANCE IDENTIFYING SET and denoted (*f*, *r*)-DIS. The problem (*f*, *r*)-DIS is said to be *i*-layered when the function $f$ is *i*-layered, and it is said to be *i*-local when $f$ is *i*-local and $r = i$. A problem is *local* if it is *i*-local for an integer $i$. Recall that our local reductions need a local gadget to operate: the subfamilies of local problems admitting a (bipartite) local gadget is called (bipartite) *gifted local*. We do not need to define *gifted 1-layered* as every 1-layered problem admits a 1-layered gadget. We also consider the parameterized version DISTANCE IDENTIFYING SET($k$).

2.3 Detailed Computational Lower Bounds

Using the DISTANCE IDENTIFYING SET meta-problem, we get the following lower bounds:

**Theorem 9.** For each 1-layered distance identifying function $f$ and every $r \in [\infty]$, the (*f*, *r*)-DISTANCE IDENTIFYING SET problem restricted to bipartite apex graphs is NP-hard, and does not admit an algorithm running in $2^{O(\sqrt{n})}$ time under ETH.

**Theorem 10.** The (bipartite) gifted local problems restricted to (bipartite) planar graphs are NP-hard, and do not admit an algorithm running in $2^{O(\sqrt{n})}$ time under ETH.

**Theorem 11.** For each $r$-local 0-layered distance identifying function $f$, $(f, r)$-DIS restricted to bipartite planar graphs is NP-hard, and cannot be solved in $2^{O(\sqrt{n})}$ under ETH.

**Theorem 12.** Let $f, g$ and $h$ be distance identifying functions such that $f$ is 1-layered, $g$ is $q$-local 0-layered and $h$ is $p$-local and admits a local (bipartite) gadget. Let $r \in [\infty]$. The $(f, r)$-, $(g, q)$- and $(h, p)$- DIS problems are NP-hard, and do not admit:

- algorithms running in $2^{o(n)}$ time, except if ETH fails,

- parameterized algorithms running in $2^{O(k)} \cdot n^{O(1)}$ time, except if $W[2] = \text{FPT}$.

The parameter $k$ denotes here the solution size of a relevant distance identifying set.

All bounds still hold in the bipartite case (whenever the gadget associated with $h$ is bipartite).

As a side result, the 1-layered general reduction answers a question of Hartung in [20]:

**Corollary 13.** Under ETH, METRIC DIMENSION cannot be solved in $2^{o(n)}$.

Finally, notice that the parameterized lower bound from Theorem 12 may be complemented by an elementary upper bound inspired from the kernel of IC and LD of size $2^k + k$:

**Proposition 14.** For every $r$-local distance identifying function $f$, the (*f*, *r*)-DISTANCE IDENTIFYING SET problem has a kernel of size $(r+1)^k + k$ where $k$ is the solution size. Therefore, it admits a naive parameterized algorithm running in $O(n^{k+3}) \in O^*(r^{(k^2)})$ time.
# 3 The Supports of the Reductions for Distance Identifying Set

## 3.1 The Distance Identifying Graphs

Consider the associated graph $\phi(\Omega, S)$ as defined in Section 2.1. The differences between the DISTANCE IDENTIFYING SET meta-problem and the dominating problem related to associated graphs actually raise two issues for a reduction based on these latter notions to be effective on DISTANCE IDENTIFYING SET. First, contrarily to the dominating problem where a vertex may only discern its close neighborhood, the meta-problem may allow a vertex to discern further than its direct neighborhood. In that case, we cannot certify that a vertex $v_i^\Omega$ does not distinguish a vertex $v_j^S$ when $u_i$ is not in $S_j$, the adjacency not remaining a sufficient argument. Secondly, one may object that a vertex $v_i^\Omega$ formally has to distinguish a vertex $v_j^S$ from another vertex, but that distinguishing a single vertex is not defined.

To circumvent these problems, we suggest the following fix: rather than producing a single vertex for each $S_j \in S$, the set $V_S$ may contain two vertices $v_j^S$ and $\bar{v}_j^S$. Then, the role of $v_i^\Omega$ would be to distinguish them if and only if $u_i \in S_j$. To ensure that the vertex $v_i^\Omega$ distinguishes $v_j^S$ and $\bar{v}_j^S$ when $u_i \in S_j$, we may use the properties $(\beta_1)$ and $(\gamma)$ of Definition 6 and 7 for the *r*-local and 1-layered problems, respectively. Precisely, when $u_i \in S_j$, $v_i^\Omega$ should be at distance *r* to $v_j^S$ (with *r* = 1 in the 1-layered cases) while $\bar{v}_j^S$ should not be in the *r*-neighborhood of $v_i^\Omega$. Similarly, to ensure that $v_i^\Omega$ cannot distinguish $v_j^S$ and $\bar{v}_j^S$ when $u_i \notin S_j$, we may use properties (*α*) or (*β*₂) of Definitions 5 and 6. Hence, when $u_i \notin S_j$, $v_j^S$ should not be in the *r*-neighborhood of $v_i^\Omega$, or $d(v_i^\Omega, v_j^S)$ and $d(v_i^\Omega, \bar{v}_j^S)$ should be equal.

That fix fairly indicates how to initiate the transformation of the associated graphs in order to deliver an equivalence between a hitting set formed by elements of $\Omega$ and the vertices of a distance identifying set included in $V_\Omega$. However, it is clearly not sufficient since we also have to distinguish the couples of vertices of $V_\Omega$ for which nothing is required. To solve that problem, we suggest to append to each vertex of the associated graph a copy of some gadget with the intuitive requirement that the gadget is able to distinguish the close neighborhood of its vertices from the whole graph. We introduce the notion of *B-extension*:

**Definition 15 (B-extension).** Let $H = (V_H, E_H)$ be a connected graph, and $B \subseteq V_H$. An induced supergraph $G = (V_G, E_G)$ is said to be a *B-extension* of $H$ if it is connected and for every vertex $v$ of $V_{G\setminus H}$, the set $N(v) \cap V_H$ is either equal to $\emptyset$ or $B$.

A vertex $v$ of $V_{G\setminus H}$ such that $N(v) \cap V_H = B$ is said to be *B-adjacent*. The *B-extensions of* $H$ such that $V_{G\setminus H}$ contains exactly a *B-adjacent vertex* or two *B-adjacent* (but not neighbors) vertices are called the *B-single-extension* and the *B-twin-extension* of $H$, respectively.

Here, the border $B$ makes explicit the connections between a copy of a gadget $H$ and a vertex outside the copy. In particular, a *B-single-extension* is formed by a gadget with its related vertex $v_i^\Omega$, while a *B-twin-extension* contains a gadget with its two related vertices $v_j^S$ and $\bar{v}_j^S$. Piecing all together, we may adapt the associated graphs to the meta-problem:

**Definition 16 (distance identifying graph).** Let $(\Omega = \{u_i | i \in \llbracket n \rrbracket\}, S = \{S_i | i \in \llbracket m \rrbracket\})$ be an instance of HITTING SET. Let $H$ be a connected graph, $B$ a subset of its vertices, and $r$ a positive integer. The $(H, B, r)$-distance identifying graph $\Phi[H, B, r](\Omega, S)$ is as follows.

- for each $i \in \llbracket n \rrbracket$, the graph $\Phi[H, B, r](\Omega, S)$ contains as induced subgraph a copy $H_i^\Omega$ of $H$ together with a $B_i^\Omega$-adjacent vertex $v_i^\Omega$, where $B_i^\Omega$ denotes the copy of $B$.

- similarly, for each $j \in \llbracket m \rrbracket$, the graph $\Phi[H, B, r](\Omega, S)$ contains a copy $H_j^S$ of $H$ together with two $B_j^S$-adjacent vertices $v_j^S$ and $\bar{v}_j^S$; the latter vertices are not adjacent.

- finally, for each $S_j \in S$ and each $u_i \in S_j$, $v_i^\Omega$ is connected to $v_j^S$ by a path of $r-1$ vertices denoted $l_{i,j}^k$ with $d(v_i^\Omega, l_{i,j}^k) = k$ for each $k \in \llbracket r-1 \rrbracket$.
# 3 The Supports of the Reductions for Distance Identifying Set

## 3.1 The Distance Identifying Graphs

Consider the associated graph $\phi(\Omega, S)$ as defined in Section 2.1. The differences between the DISTANCE IDENTIFYING SET meta-problem and the dominating problem related to associated graphs actually raise two issues for a reduction based on these latter notions to be effective on DISTANCE IDENTIFYING SET. First, contrarily to the dominating problem where a vertex may only discern its close neighborhood, the meta-problem may allow a vertex to discern further than its direct neighborhood. In that case, we cannot certify that a vertex $v_i^\Omega$ does not distinguish a vertex $v_j^S$ when $u_i$ is not in $S_j$, the adjacency not remaining a sufficient argument. Secondly, one may object that a vertex $v_i^\Omega$ formally has to distinguish a vertex $v_j^S$ from another vertex, but that distinguishing a single vertex is not defined.

To circumvent these problems, we suggest the following fix: rather than producing a single vertex for each $S_j \in S$, the set $V_S$ may contain two vertices $v_j^S$ and $\bar{v}_j^S$. Then, the role of $v_i^\Omega$ would be to distinguish them if and only if $u_i \in S_j$. To ensure that the vertex $v_i^\Omega$ distinguishes $v_j^S$ and $\bar{v}_j^S$ when $u_i \in S_j$, we may use the properties $(\beta_1)$ and $(\gamma)$ of Definition 6 and 7 for the *r*-local and 1-layered problems, respectively. Precisely, when $u_i \in S_j$, $v_i^\Omega$ should be at distance *r* to $v_j^S$ (with *r* = 1 in the 1-layered cases) while $\bar{v}_j^S$ should not be in the *r*-neighborhood of $v_i^\Omega$. Similarly, to ensure that $v_i^\Omega$ cannot distinguish $v_j^S$ and $\bar{v}_j^S$ when $u_i \notin S_j$, we may use properties ($\alpha$) or ($\beta_2$) of Definitions 5 and 6. Hence, when $u_i \notin S_j$, $v_j^S$ should not be in the *r*-neighborhood of $v_i^\Omega$, or $d(v_i^\Omega, v_j^S)$ and $d(v_i^\Omega, \bar{v}_j^S)$ should be equal.

That fix fairly indicates how to initiate the transformation of the associated graphs in order to deliver an equivalence between a hitting set formed by elements of $\Omega$ and the vertices of a distance identifying set included in $V_\Omega$. However, it is clearly not sufficient since we also have to distinguish the couples of vertices of $V_\Omega$ for which nothing is required. To solve that problem, we suggest to append to each vertex of the associated graph a copy of some gadget with the intuitive requirement that the gadget is able to distinguish the close neighborhood of its vertices from the whole graph. We introduce the notion of *B-extension*:

**Definition 15 (B-extension).** Let $H = (V_H, E_H)$ be a connected graph, and $B \subseteq V_H$. An induced supergraph $G = (V_G, E_G)$ is said to be a *B-extension* of $H$ if it is connected and for every vertex $v$ of $V_{G\setminus H}$, the set $N(v) \cap V_H$ is either equal to $\emptyset$ or $B$.

A vertex $v$ of $V_{G\setminus H}$ such that $N(v) \cap V_H = B$ is said to be *B-adjacent*. The *B-extensions* of $H$ such that $V_{G\setminus H}$ contains exactly a *B-adjacent* vertex or two *B-adjacent* (but not neighbors) vertices are called the *B-single-extension* and the *B-twin-extension* of $H$, respectively.

Here, the border $B$ makes explicit the connections between a copy of a gadget $H$ and a vertex outside the copy. In particular, a *B-single-extension* is formed by a gadget with its related vertex $v_i^\Omega$, while a *B-twin-extension* contains a gadget with its two related vertices $v_j^S$ and $\bar{v}_j^S$. Piecing all together, we may adapt the associated graphs to the meta-problem:

**Definition 16 (distance identifying graph).** Let $(\Omega = \{u_i | i \in \llbracket n \rrbracket\}, S = \{S_i | i \in \llbracket m \rrbracket\})$ be an instance of HITTING SET. Let $H$ be a connected graph, $B$ a subset of its vertices, and $r$ a positive integer. The $(H, B, r)$-distance identifying graph $\Phi[H, B, r](\Omega, S)$ is as follows.

- for each $i \in \llbracket n \rrbracket$, the graph $\Phi[H, B, r](\Omega, S)$ contains as induced subgraph a copy $H_i^\Omega$ of $H$ together with a $B_i^\Omega$-adjacent vertex $v_i^\Omega$, where $B_i^\Omega$ denotes the copy of $B$.

- similarly, for each $j \in \llbracket m \rrbracket$, the graph $\Phi[H, B, r](\Omega, S)$ contains a copy $H_j^S$ of $H$ together with two $B_j^S$-adjacent vertices $v_j^S$ and $\bar{v}_j^S$; the latter vertices are not adjacent.

- finally, for each $S_j \in S$ and each $u_i \in S_j$, $v_i^\Omega$ is connected to $v_j^S$ by a path of $r-1$ vertices denoted $l_{i,j}^k$ with $d(v_i^\Omega, l_{i,j}^k) = k$ for each $k \in \llbracket r-1 \rrbracket$.
10:8 On the Distance Identifying Set Meta-Problem

<figure><img src="image_57.png" /><figcaption>■ **Figure 2** A $(H, B, 3)$-distance identifying graph and a $(H, B)$-apex distance identifying graph built on the planar instance formed by $\Omega = \{1, 2, 3, 4\}$ and $S = \{\{1, 2\}, \{2, 3, 4\}\}$.</figcaption></figure>

When the problem is not local, we prefer the following identifying graph:

► **Definition 17** ($(H, B)$-apex distance identifying graph). An $(H, B)$-apex distance identifying graph $\Phi^*[H, B](\Omega, S)$ is the union of a $(H, B, 1)$-distance identifying graph with an additional vertex $a$ called *apex* such that:

for each $u_i \in \Omega$, the apex $a$ is $B_i^\Omega$-adjacent to $H_i^\Omega$.

for each $S_j \in S$, the apex $a$ is adjacent to $v_j^S$ and $\bar{v}_j^S$.

► **Proposition 18.** *Given an instance $(\Omega, S)$ of PLANAR HITTING SET where $|\Omega| = n$, $|S| = m$, the graphs $G = \Phi[H, B, r](\Omega, S)$ and $G' = \Phi^*[H, B](\Omega, S)$*

are connected and have size bounded by $(|H| + 2r)(n + m)$, (with $r = 1$ for $G'$),

may be built in polynomial time in their size,

are bipartite if the $B$-single extension of $H$ is bipartite,

are respectively planar and an apex graph if the $B$-twin-extension of $H$ is planar.

Having defined the (apex) distance identifying graphs, the main effort to obtain generic reduction from PLANAR HITTING SET is done. We now define relevant gadgets:

► **Definition 19** ($(f, r)$-gadgets). Let $f$ be a distance identifying function and $r \in [\infty]$. Let $H = (V_H, E_H)$ be a connected graph, and $B, C$ be two subsets of $V_H$. We said that the triple $(H, B, C)$ is a $(f, r)$-gadget if for every $B$-extension $G$ of $H$:

(ph) $C$ f-distinguishes $V_H$ and $V_G$.

(pb) $C$ f-distinguishes $N_B$ and $V_{G \setminus H} \setminus N_B$, where $N_B$ is the set of $B$-adjacent vertices of $G$.

(pd) $C$ is an $r$-dominating set of $G[V_H \cup N_B]$.

(ps) For all $(f, r)$-distance identifying set $S$ of $G$, $|C| \le |S \cap V_H|$.

► **Definition 20** (local gadgets). A $(f, r)$-gadget is a *local gadget*, if $f$ is a $r$-local identifying function with $r \ne \infty$, and $(p_l)$: for every $k \in [r]$, there exists $c \in C$ such that $d(c, B) = k - 1$.

Consistently, we say that a $(f, r)$-gadget $(H, B, C)$ is *bipartite* if the $B$-single-extension of $H$ is bipartite, and that it is *planar* if the $B$-twin-extension of $H$ is planar.

► **Theorem 21.** *Let $(\Omega, S)$ be an instance of HITTING SET such that $|\Omega| = n > 1$, $|S| = m$. Let $(H, B, C)$ be a $(f, r)$-gadget for a 1-layered identifying function $f$ and let $(H', B', C')$ be a local $(g, q)$-gadget. The following propositions are equivalent:*

there exists a hitting set of $S$ of size $k$.

there exists a $(f, r)$-distance identifying set of $\Phi^*[H, B](\Omega, S)$ of size $k + |C|(n + m)$.

there exists a $(g, q)$-distance identifying set of $\Phi[H', B', q](\Omega, S)$ of size $k + |C'|(n + m)$.
10:8 On the Distance Identifying Set Meta-Problem

<figure><img src="image_60.png" /><figcaption>Figure 2 A $(H, B, 3)$-distance identifying graph and a $(H, B)$-apex distance identifying graph built on the planar instance formed by $\Omega = \{1, 2, 3, 4\}$ and $S = \{\{1, 2\}, \{2, 3, 4\}\}$.</figcaption></figure>

When the problem is not local, we prefer the following identifying graph:

**Definition 17** ((*H*, *B*)-apex distance identifying graph). An (*H*, *B*)-apex distance identifying graph $\Phi^*[H, B](\Omega, S)$ is the union of a (*H*, *B*, 1)-distance identifying graph with an additional vertex *a* called *apex* such that:

- for each $u_i \in \Omega$, the apex $a$ is $B_i^\Omega$-adjacent to $H_i^\Omega$.

- for each $S_j \in S$, the apex $a$ is adjacent to $v_j^S$ and $\bar{v}_j^S$.

**Proposition 18.** *Given an instance (Ω, S) of PLANAR HITTING SET where |Ω| = n, |S| = m, the graphs G = Φ[H, B, r](Ω, S) and G' = Φ*[H, B](Ω, S)*

- are connected and have size bounded by $(|H| + 2r)(n + m)$, (with $r = 1$ for $G'$),

- may be built in polynomial time in their size,

- are bipartite if the B-single extension of H is bipartite,

- are respectively planar and an apex graph if the B-twin-extension of H is planar.

Having defined the (apex) distance identifying graphs, the main effort to obtain generic reduction from PLANAR HITTING SET is done. We now define relevant gadgets:

**Definition 19** ((*f*, *r*)-gadgets). Let *f* be a distance identifying function and *r* ∈ [∞]. Let *H* = (*V*<sub>*H*</sub>, *E*<sub>*H*</sub>) be a connected graph, and *B*, *C* be two subsets of *V*<sub>*H*</sub>. We said that the triple (*H*, *B*, *C*) is a (*f*, *r*)-gadget if for every *B*-extension *G* of *H*:

(ph) *C f-distinguishes* $V_H$ and $V_G$.

(pb) *C f-distinguishes* $N_B$ and $V_{G\setminus H} \setminus N_B$, where $N_B$ is the set of *B*-adjacent vertices of *G*.

(pd) *C* is an *r*-dominating set of* $G[V_H \cup N_B]$.

(ps) For all (*f*, *r*)-distance identifying set *S* of *G*, $|C| \le |S \cap V_H|$.

**Definition 20 (local gadgets).** A (*f*, *r*)-gadget is a *local gadget*, if *f* is a *r*-local identifying function with *r* ≠ ∞, and (*p*<sub>*l*</sub>): for every *k* ∈ [r], there exists *c* ∈ *C* such that *d*(*c*, *B*) = *k* − 1.

Consistently, we say that a (*f*, *r*)-gadget (*H*, *B*, *C*) is *bipartite* if the *B*-single-extension of *H* is bipartite, and that it is *planar* if the *B*-twin-extension of *H* is planar.

**Theorem 21.** Let $(\Omega, S)$ be an instance of HITTING SET such that $|\Omega| = n > 1$, $|S| = m$. Let $(H, B, C)$ be a $(f, r)$-gadget for a 1-layered identifying function $f$ and let $(H', B', C')$ be a local $(g, q)$-gadget. The following propositions are equivalent:

- there exists a hitting set of $S$ of size $k$.

- there exists a $(f, r)$-distance identifying set of $\Phi^*[H, B](\Omega, S)$ of size $k + |C|(n + m)$.

- there exists a $(g, q)$-distance identifying set of $\Phi[H', B', q](\Omega, S)$ of size $k + |C'|(n + m)$.
**Proof of Theorem 21.** We focus on the equivalence between the first and second items.

Suppose first that $P$ is a hitting set of $(\Omega, S)$ of size $k$. By denoting $C_i^\Omega$ and $C_j^S$ the copies of $C$ associated to the copies $H_i^\Omega$ and $H_j^S$ of $H$, we suggest the following set $I$ of size $k + |C|(n+m)$ as a $(f, r)$-distance identifying set of $G = \Phi^*[H, B](\Omega, S)$:

$$I = \{v_i^\Omega: u_i \in P\} \cup \bigcup_{i \in [n]} C_i^\Omega \cup \bigcup_{j \in [m]} C_j^S.$$

Recall that by construction, $G$ is a $B_i^\Omega$-extension of $H_i^\Omega$ (respectively $B_j^S$-extension of $H_j^S$) for any $i \in [n]$ (respectively $j \in [m]$). This directly implies that $I$ is an $r$-dominating set of $G$. Indeed, the condition $(p_d)$ of Definition 19 implies that $C_i^\Omega$ (respectively $C_j^S$) $r$-dominates $H_i^\Omega$ plus $v_i^\Omega$ (respectively of $H_j^S$ plus $v_j^S$, $\bar{v}_j^S$). The remaining apex is also $r$-dominated by any $C_i^\Omega$, as it is $B_i^\Omega$-adjacent for every $i \in [n]$.

We now have to show that $I$ $f$-distinguishes $G$. We begin with the vertices of the gadget copies because the condition $(p_h)$ implies that $C_i^\Omega \subseteq I$ $f$-distinguishes the vertices of $H_i^\Omega$ and $G$ for every $i \in [n]$, and $I$ $f$-distinguishes the vertices of $H_j^S$ and $G$ for every $j \in [m]$. Thereby, we only have to study the vertices of the form $v_i^\Omega$, $v_j^S$, $\bar{v}_j^S$, and the apex $a$ (there is no vertex of the form $l_{i,j}^k$ in an apex distance identifying graph). To distinguish them, we use the condition $(p_b)$. Recall that $n > 1$. Then, for each distinct $i, i' \in [n]$, we have:

- $v_i^\Omega$ is $B_i^\Omega$-adjacent but not $B_{i'}^{\Omega'}$-adjacent,

- $a$ is both $B_i^\Omega$-adjacent and $B_{i'}^{\Omega'}$-adjacent,

- a vertex of the form $v_j^S$ or $\bar{v}_j^S$ is neither $B_i^\Omega$-adjacent nor $B_{i'}^{\Omega'}$-adjacent.

Enumerating the relevant $i$ and $i'$, we deduce that every couple of vertices is distinguished except when they are both of the form $v_j^S$ or $\bar{v}_{j'}^S$ for $j, j' \in [m]$. But we may distinguish $v_j^S$ or $\bar{v}_{j'}^S$ for distinct $j, j'$ by applying $(p_b)$ on $H_j^S$.

It remains to distinguish $v_j^S$ and $\bar{v}_j^S$ for $j \in [m]$. We now use the fact that $P$ is a hitting set for $(\Omega, S)$. By definition of a hitting set, for any set $S_j \in S$, there exists a vertex $u_i \in P$ such that $u_i \in S_j$. We observe that $d(v_i^\Omega, v_j^S) = 1 < d(v_i^\Omega, \bar{v}_j^S)$ by construction of $G$ and that $v_i^\Omega \in I$ by definition of $I$. Since $f$ is 1-layered, $I$ $f$-distinguishes $v_j^S$ and $\bar{v}_j^S$.

In the other direction, assume that $I$ is a distance identifying set of $G$ of size $k + |C|(n+m)$. As every set of $S$ is not empty, we may define a function $\varphi: [m] \to [n]$ such that $u_{\varphi(j)} \in S_j$. We suggest the following set $P$ as an hitting set of $S$ of size at most $k$:

$$P = \{u_i \in \Omega \mid v_i^\Omega \in I\} \cup \{u_{\varphi(j)} \in \Omega \mid v_j^S \in I \text{ or } \bar{v}_j^S \in I\}$$

We claim that the only vertices that may $f$-distinguish $v_j^S$ and $\bar{v}_j^S$ are themselves and the vertices $v_i^\Omega$ such that $u_i \in S_j$. To prove so, we apply propriety (α) of Definition 5:

- the apex $a$ verifies $d(a, v_j^S) = 1 = d(a, \bar{v}_j^S)$

- a vertex $v_i^\Omega$ such that $u_i \notin S_j$ verifies $d(v_i^\Omega, v_j^S) = 3 = d(v_i^\Omega, \bar{v}_j^S)$

- a vertex $v$ of $H_i^\Omega$ verifies $d(v, v_j^S) = 2 + d(v, B_i^\Omega) = d(v, \bar{v}_j^S)$

- a vertex $v$ of $H_{j'}^S$ with $j \neq j'$ verifies $d(v, v_j^S) = 3 + d(v, B_{j'}^S) = d(v, \bar{v}_j^S)$

- both $v_j^S$ and $\bar{v}_j^S$ are $B_j^S$-adjacent, so they are at the same distance of any vertex of $H_j^S$.

We deduce that $v_j^S$ and $\bar{v}_j^S$ are $f$-distinguished only if either one on them belongs to $I$ (in that case $u_{\varphi(j)} \in P \cap S_j$) or there exists $v_i^\Omega \in I$ such that $u_i \in S_j$ (and then $u_i \in P \cap S_j$).

It remains to show that $|P| \le k$. By the condition $(p_s)$ of Definition 19, we know that $|I \cap V_{H_i^\Omega}| \ge |C_i^\Omega|$ and $|I \cap V_{H_j^S}| \ge |C_j^S|$ for any $i \in [n]$ and $j \in [m]$, implying

$$k = |I| - |C|(n+m) \ge \sum_{i \in [n]} |I \cap \{v_i^\Omega\}| + \sum_{j \in [m]} |I \cap \{v_j^S, \bar{v}_j^S\}| \ge \sum_{v_i^\Omega \in I} 1 + \sum_{I \cap \{v_j^S, \bar{v}_j^S\} \neq \emptyset} 1 = |P|$$

The equivalence between the first and third points is proven in [4].

<figure><img src="image_58.png" /></figure>
**Proof of Theorem 21.** We focus on the equivalence between the first and second items.

Suppose first that $P$ is a hitting set of $(\Omega, S)$ of size $k$. By denoting $C_i^\Omega$ and $C_j^S$ the copies of $C$ associated to the copies $H_i^\Omega$ and $H_j^S$ of $H$, we suggest the following set $I$ of size $k + |C|(n+m)$ as a $(f, r)$-distance identifying set of $G = \Phi^*[H, B](\Omega, S)$:

$$I = \{v_i^\Omega: u_i \in P\} \cup \bigcup_{i \in [n]} C_i^\Omega \cup \bigcup_{j \in [m]} C_j^S.$$

Recall that by construction, $G$ is a $B_i^\Omega$-extension of $H_i^\Omega$ (respectively $B_j^S$-extension of $H_j^S$) for any $i \in [n]$ (respectively $j \in [m]$). This directly implies that $I$ is an $r$-dominating set of $G$. Indeed, the condition $(p_d)$ of Definition 19 implies that $C_i^\Omega$ (respectively $C_j^S$) $r$-dominates $H_i^\Omega$ plus $v_i^\Omega$ (respectively of $H_j^S$ plus $v_j^S$, $\bar{v}_j^S$). The remaining apex is also $r$-dominated by any $C_i^\Omega$, as it is $B_i^\Omega$-adjacent for every $i \in [n]$.

We now have to show that $I$ $f$-distinguishes $G$. We begin with the vertices of the gadget copies because the condition $(p_h)$ implies that $C_i^\Omega \subseteq I$ $f$-distinguishes the vertices of $H_i^\Omega$ and $G$ for every $i \in [n]$, and $I$ $f$-distinguishes the vertices of $H_j^S$ and $G$ for every $j \in [m]$. Thereby, we only have to study the vertices of the form $v_i^\Omega$, $v_j^S$, $\bar{v}_j^S$, and the apex $a$ (there is no vertex of the form $l_{i,j}^k$ in an apex distance identifying graph). To distinguish them, we use the condition $(p_b)$. Recall that $n > 1$. Then, for each distinct $i, i' \in [n]$, we have:

- $v_i^\Omega$ is $B_i^\Omega$-adjacent but not $B_{i'}^{\Omega'}$-adjacent,

- $a$ is both $B_i^\Omega$-adjacent and $B_{i'}^{\Omega'}$-adjacent,

- a vertex of the form $v_j^S$ or $\bar{v}_j^S$ is neither $B_i^\Omega$-adjacent nor $B_{i'}^{\Omega'}$-adjacent.

Enumerating the relevant $i$ and $i'$, we deduce that every couple of vertices is distinguished except when they are both of the form $v_j^S$ or $\bar{v}_{j'}^S$ for $j, j' \in [m]$. But we may distinguish $v_j^S$ or $\bar{v}_{j'}^S$ for distinct $j, j'$ by applying $(p_b)$ on $H_j^S$.

It remains to distinguish $v_j^S$ and $\bar{v}_j^S$ for $j \in [m]$. We now use the fact that $P$ is a hitting set for $(\Omega, S)$. By definition of a hitting set, for any set $S_j \in S$, there exists a vertex $u_i \in P$ such that $u_i \in S_j$. We observe that $d(v_i^\Omega, v_j^S) = 1 < d(v_i^\Omega, \bar{v}_j^S)$ by construction of $G$ and that $v_i^\Omega \in I$ by definition of $I$. Since $f$ is 1-layered, $I$ $f$-distinguishes $v_j^S$ and $\bar{v}_j^S$.

In the other direction, assume that $I$ is a distance identifying set of $G$ of size $k + |C|(n+m)$. As every set of $S$ is not empty, we may define a function $\varphi: [m] \to [n]$ such that $u_{\varphi(j)} \in S_j$.

We suggest the following set $P$ as an hitting set of $S$ of size at most $k$:

$$P = \{u_i \in \Omega \mid v_i^\Omega \in I\} \cup \{u_{\varphi(j)} \in \Omega \mid v_j^S \in I \text{ or } \bar{v}_j^S \in I\}$$

We claim that the only vertices that may $f$-distinguish $v_j^S$ and $\bar{v}_j^S$ are themselves and the vertices $v_i^\Omega$ such that $u_i \in S_j$. To prove so, we apply propriety $(\alpha)$ of Definition 5:

- the apex $a$ verifies $d(a, v_j^S) = 1 = d(a, \bar{v}_j^S)$

- a vertex $v_i^\Omega$ such that $u_i \notin S_j$ verifies $d(v_i^\Omega, v_j^S) = 3 = d(v_i^\Omega, \bar{v}_j^S)$

- a vertex $v$ of $H_i^\Omega$ verifies $d(v, v_j^S) = 2 + d(v, B_i^\Omega) = d(v, \bar{v}_j^S)$

- a vertex $v$ of $H_{j'}^S$ with $j \neq j'$ verifies $d(v, v_j^S) = 3 + d(v, B_{j'}^S) = d(v, \bar{v}_j^S)$

- both $v_j^S$ and $\bar{v}_j^S$ are $B_j^S$-adjacent, so they are at the same distance of any vertex of $H_j^S$.

We deduce that $v_j^S$ and $\bar{v}_j^S$ are $f$-distinguished only if either one on them belongs to $I$ (in that case $u_{\varphi(j)} \in P \cap S_j$) or there exists $v_i^\Omega \in I$ such that $u_i \in S_j$ (and then $u_i \in P \cap S_j$).

It remains to show that $|P| \le k$. By the condition $(p_s)$ of Definition 19, we know that $|I \cap V_{H_i^\Omega}| \ge |C_i^\Omega|$ and $|I \cap V_{H_j^S}| \ge |C_j^S|$ for any $i \in [n]$ and $j \in [m]$, implying

$$k = |I| - |C|(n+m) \ge \sum_{i \in [n]} |I \cap \{v_i^\Omega\}| + \sum_{j \in [m]} |I \cap \{v_j^S, \bar{v}_j^S\}| \ge \sum_{v_i^\Omega \in I} 1 + \sum_{I \cap \{v_j^S, \bar{v}_j^S\} \neq \emptyset} 1 = |P|$$

The equivalence between the first and third points is proven in [4].

<figure><img src="image_61.png" /></figure>
10:10 On the Distance Identifying Set Meta-Problem

3.2 Binary Compression of Gadgets

The Theorem 21 is a powerful tool to get reductions, in particular in the planar cases.
However, the number of involved gadgets does not allow to use Theorem 1. This limitation
is due to the uses of a gadget per vertex to identify in the distance identifying graphs. Using
power set, we may obtain a better order: given $k$ gadgets, we may identify $2^k - 1$ vertices
(we avoid to identify a vertex with the empty subset of gadgets). Thus, we will consider
binary representations of integers as sequences of bits, with weakest bit at last position. For
a positive integer $n$, we define the integer $\lg_n = 1 + \lfloor \log_2(n) \rfloor$ and introduce a new graph:

► **Definition 22** ($(H, B, r)$-compressed graph). Let $(\Omega = \{u_i | i \in \lfloor n \rfloor\}, S = \{S_i | i \in \lfloor m \rfloor\})$ be an instance of HITTING SET. Let $H$ be a connected graph, $B$ be a subset of its vertices, and $r$ be a positive integer. The $(H, B, r)$-compressed graph $\Psi[H, B, r](\Omega, S)$ is defined as follows. $\Psi[H, B, r](\Omega, S)$ contains as induced subgraphs $\lg_{n+1}$ copies of $H$ denoted $H_i^\Omega$ for $i \in \lfloor \lg_{n+1} \rfloor$ and $\lg_m$ another copies of $H$ denoted $H_j^S$ for $j \in \lfloor \lg_m \rfloor$. Then:

- for each $j \in \lfloor m \rfloor$, we add two non-adjacent vertices $v_j^S$ and $\bar{v}_j^S$. They are $B_k^S$-adjacent for each $k \in \lfloor \lg_m \rfloor$ such that the $k^{th}$ bit of the binary representation of $j$ is 1.

- for each $i \in \lfloor n \rfloor$, we add $r$ vertices denoted $l_i^{j-1}$ with $j \in \lfloor r \rfloor$ to form a fresh path such that $d(v_i^{\Omega}, l_i^{j-1}) = j - 1$ where $v_i^{\Omega} = l_i^0$. We make $v_i^{\Omega} B_k^{\Omega}$-adjacent for each $k \in \lfloor \lg_{n+1} \rfloor$ such that the $k^{th}$ bit of the binary representation of $i$ is 1.

- for each $S_j \in S$ and each $u_i \in S_j$, we add the edge $(l_i^{r-1}, v_j^S)$.

- we add $r$ vertices denoted $a^{j-1}$ with $j \in \lfloor r \rfloor$ to form a path such that $d(a^0, a^{j-1}) = j - 1$. The vertex $a^0$ is $B_k^\Omega$-adjacent for every $k \in \lfloor \lg_{n+1} \rfloor$, and we add the edges $(a^{r-1}, v_j^S)$ and $(a^{r-1}, \bar{v}_j^S)$ for each $j \in \lfloor m \rfloor$.

By definition of $\lg_{n+1}$, for every $i \in \lfloor n \rfloor$, one of the last $\lg_{n+1}$ bits of the binary representation of $i$ is 0. So, $a^0$ has a distinct characterization in the power set formed by the gadgets $H_i^\Omega$.

► **Proposition 23.** The graph $\Psi[H, B, r](\Omega, S)$ built on an instance $(\Omega, S)$ of HITTING SET

- is connected and has size at most $|H|(\lg_{n+1} + \lg_m) + r(n+1) + 2m$, where $|\Omega| = n$, $|S| = m$

- may be built in polynomial time in its size,

- is bipartite if the $B$-single extension of $H$ is bipartite.

**Theorem 24.** Let $(\Omega, S)$ be an instance of HITTING SET such that $|\Omega| = n$, $|S| = m$. Let $(H, B, C)$ be a $(f, r)$-gadget for a 1-layered identifying function $f$ and let $(H', B', C')$ be a local $(g, q)$-gadget. The following propositions are equivalent:

- there exists a hitting set of $S$ of size $k$.

- there exists a $(f, r)$-distance identifying set of $\Psi[H, B, 1](\Omega, S)$ of size $k + |C|(\lg_{n+1} + \lg_m)$.

- there exists a $(q, r)$-distance identifying set of $\Psi[H', B', q](\Omega, S)$ of size $k + |C'|(\lg_{n+1} + \lg_m)$.

4 On Providing Gadgets to Establish Generic Reductions

In this section, we finalize the reductions by furnishing some gadgets and combining them
with the suitable theorems and propositions from Section 3. We directly define the gadgets.

► **Definition 25 (The 1-layered gadget).** Let $H$ be the bipartite planar graph such that:

- Its ten vertices are denoted $b, \bar{b}, u_1, \bar{u}_1, u_2, \bar{u}_2, v_1, \bar{v}_1, v_2$ and $\bar{v}_2$,

- The vertices $u_1, u_2, \bar{u}_1$ and $\bar{u}_2$ form a cycle as well as the vertices $v_1, v_2, \bar{v}_1$ and $\bar{v}_2$.

- The vertices $b$ and $\bar{b}$ are adjacent to $u_1, \bar{u}_1, v_1$ and $\bar{v}_1$.
10:10 On the Distance Identifying Set Meta-Problem

## 3.2 Binary Compression of Gadgets

The Theorem 21 is a powerful tool to get reductions, in particular in the planar cases. However, the number of involved gadgets does not allow to use Theorem 1. This limitation is due to the uses of a gadget per vertex to identify in the distance identifying graphs. Using power set, we may obtain a better order: given $k$ gadgets, we may identify $2^k - 1$ vertices (we avoid to identify a vertex with the empty subset of gadgets). Thus, we will consider *binary representations* of integers as sequences of bits, with weakest bit at last position. For a positive integer $n$, we define the integer $\lg_n = 1 + \lfloor \log_2(n) \rfloor$ and introduce a new graph:

**► Definition 22 (H, B, r)-compressed graph.** Let $(\Omega = \{u_i | i \in \lfloor n \rfloor\}, S = \{S_i | i \in \lfloor m \rfloor\})$ be an instance of HITTING SET. Let $H$ be a connected graph, $B$ be a subset of its vertices, and $r$ be a positive integer. The $(H, B, r)$-compressed graph $\Psi[H, B, r](\Omega, S)$ is defined as follows. $\Psi[H, B, r](\Omega, S)$ contains as induced subgraphs $\lg_{n+1}$ copies of $H$ denoted $H_i^\Omega$ for $i \in \lfloor \lg_{n+1} \rfloor$ and $\lg_m$ another copies of $H$ denoted $H_j^S$ for $j \in \lfloor \lg_m \rfloor$. Then:

- for each $j \in \lfloor m \rfloor$, we add two non-adjacent vertices $v_j^S$ and $\bar{v}_j^S$. They are $B_k^S$-adjacent for each $k \in \lfloor \lg_m \rfloor$ such that the $k^{th}$ bit of the binary representation of $j$ is 1.

- for each $i \in \lfloor n \rfloor$, we add $r$ vertices denoted $l_i^{j-1}$ with $j \in \lfloor r \rfloor$ to form a fresh path such that $d(v_i^\Omega, l_i^{j-1}) = j - 1$ where $v_i^\Omega = l_i^0$. We make $v_i^\Omega B_k^\Omega$-adjacent for each $k \in \lfloor \lg_{n+1} \rfloor$ such that the $k^{th}$ bit of the binary representation of $i$ is 1.

- for each $S_j \in S$ and each $u_i \in S_j$, we add the edge $(l_i^{r-1}, v_j^S)$.

- we add $r$ vertices denoted $a^{j-1}$ with $j \in \lfloor r \rfloor$ to form a path such that $d(a^0, a^{j-1}) = j - 1$. The vertex $a^0$ is $B_k^\Omega$-adjacent for every $k \in \lfloor \lg_{n+1} \rfloor$, and we add the edges $(a^{r-1}, v_j^S)$ and $(a^{r-1}, \bar{v}_j^S)$ for each $j \in \lfloor m \rfloor$.

By definition of $\lg_{n+1}$, for every $i \in \lfloor n \rfloor$, one of the last $\lg_{n+1}$ bits of the binary representation of $i$ is 0. So, $a^0$ has a distinct characterization in the power set formed by the gadgets $H_i^\Omega$.

**► Proposition 23.** The graph $\Psi[H, B, r](\Omega, S)$ built on an instance $(\Omega, S)$ of HITTING SET

- is connected and has size at most $|H|(\lg_{n+1} + \lg_m) + r(n+1) + 2m$, where $|\Omega| = n$, $|S| = m$

- may be built in polynomial time in its size,

- is bipartite if the $B$-single extension of $H$ is bipartite.

**► Theorem 24.** Let $(\Omega, S)$ be an instance of HITTING SET such that $|\Omega| = n$, $|S| = m$. Let $(H, B, C)$ be a $(f, r)$-gadget for a 1-layered identifying function $f$ and let $(H', B', C')$ be a local $(g, q)$-gadget. The following propositions are equivalent:

- there exists a hitting set of $S$ of size $k$.

- there exists a $(f, r)$-distance identifying set of $\Psi[H, B, 1](\Omega, S)$ of size $k + |C|(\lg_{n+1} + \lg_m)$.

- there exists a $(q, r)$-distance identifying set of $\Psi[H', B', q](\Omega, S)$ of size $k + |C'|(\lg_{n+1} + \lg_m)$.

# 4 On Providing Gadgets to Establish Generic Reductions

In this section, we finalize the reductions by furnishing some gadgets and combining them with the suitable theorems and propositions from Section 3. We directly define the gadgets.

**► Definition 25 (The 1-layered gadget).** Let $H$ be the bipartite planar graph such that:

- Its ten vertices are denoted $b, \bar{b}, u_1, \bar{u}_1, u_2, \bar{u}_2, v_1, \bar{v}_1, v_2$ and $\bar{v}_2$,

- The vertices $u_1, u_2, \bar{u}_1$ and $\bar{u}_2$ form a cycle as well as the vertices $v_1, v_2, \bar{v}_1$ and $\bar{v}_2$.

- The vertices $b$ and $\bar{b}$ are adjacent to $u_1, \bar{u}_1, v_1$ and $\bar{v}_1$.
<figure><img src="image_59.png" /><figcaption>■ **Figure 3** A (H,B,2)-compressed graph built with $\Omega = \{1, 2, 3, 4\}$ and $S = \{\{1, 2\}, \{2, 3, 4\}\}$.</figcaption></figure>

<figure><img src="image_60.png" /><figcaption>■ **Figure 5** The 2-local 0-layered gadget. $C_2$ contains the colored vertices.</figcaption></figure>

<figure><img src="image_61.png" /><figcaption>■ **Figure 4** The 1-layered gadget $(H, B, C)$. $C$ contains the colored vertices.</figcaption></figure>

<figure><img src="image_62.png" /><figcaption>■ **Figure 6** The 2-IC gadget. $C_2$ contains the colored vertices.</figcaption></figure>

We define the sets $B = \{b, \bar{b}\}$ and $C = \{b, u_1, u_2, v_1, v_2\}$.

The triple $(H, B, C)$ is called the 1-layered gadget (see Fig. 4).

► **Definition 26** (The $r$-local 0-layered gadget). Given an integer $r > 1$ (respectively $r = 1$), let $H_r$ be the bipartite planar graph of size $4r + 2$ (respectively 8) such that:

■ its vertices are denoted $a_i$ and $b_i$ for $i \in \llbracket 2r+1 \rrbracket$ (respectively $i \in \llbracket 4 \rrbracket$),

■ for each $i \in \llbracket 2r \rrbracket$ (respectively $i \in \llbracket 3 \rrbracket$), both $a_i$ and $b_i$ are adjacent to $a_{i+1}$ and $b_{i+1}$

We define the sets $B_r = \{a_1, b_1\}$ and $C_r = \{a_i \mid i \in \llbracket 2r+1 \rrbracket\}$ (respectively $C_1 = \{a_1, a_2, a_3, a_4\}$). The triple $(H_r, B_r, C_r)$ is called the $r$-local 0-layered gadget (see Fig. 5).

For each positive integer $r$, $r$-LD and $r$-MD are $r$-local 0-layered problems, whereas $r$-IC is not 0-layered. We define a specific gadget for this remaining problem.

► **Definition 27** (The $r$-IC gadget). Given a positive integer $r$, let $H_r$ be the bipartite planar graph of size $6r + 4$ such that:

■ its vertices are denoted $a_{i-1}$ and $b_{i-1}$ for $i \in \llbracket r+2 \rrbracket$, and $a_i^j$ and $b_i^j$ for $i \in \llbracket r \rrbracket$ and $j \in \llbracket 2 \rrbracket$.

We also denote $a_0$ as $a_{r+1}^1$ and $a_{r+1}^2$ and we denote $b_0$ as $b_{r+1}^1$, $b_{r+1}^2$, $a_0^1$ and $a_0^2$.

■ the edges are all included in the six following paths

■ from $a_0$ to $a_{r+1}$ such that $d(a_0, a_i) = i$ for $i \in \llbracket r+1 \rrbracket$.

■ from $b_0$ to $b_{r+1}$ such that $d(b_0, b_i) = i$ for $i \in \llbracket r+1 \rrbracket$.

■ from $a_0^1$ to $a_{r+1}^1$ such that $d(a_0^1, a_i^1) = i$ for $i \in \llbracket r+1 \rrbracket$.

■ from $a_0^2$ to $a_{r+1}^2$ such that $d(a_0^2, a_i^2) = i$ for $i \in \llbracket r+1 \rrbracket$.

■ from $b_1^1$ to $b_{r+1}^1$ such that $d(b_1^1, b_i^1) = i - 1$ for $i \in \llbracket r+1 \rrbracket$.

■ from $b_1^2$ to $b_{r+1}^2$ such that $d(b_1^2, b_i^2) = i - 1$ for $i \in \llbracket r+1 \rrbracket$.

We define the sets $B_r = \{b_1^1, b_1^2\}$ and $C_r = \{a_{r+1}, b_{r+1}\} \cup \bigcup_{i \in \llbracket r+1 \rrbracket} \{a_i^1, b_i^1\}$.

The triple $(H_r, B_r, C_r)$ is called the $r$-IC gadget (see Fig. 6).

As expected, we have the following propositions:
<figure><img src="image_62.png" /><figcaption>■ **Figure 3** A (H,B,2)-compressed graph built with $\Omega = \{1, 2, 3, 4\}$ and $S = \{\{1, 2\}, \{2, 3, 4\}\}$.</figcaption></figure>

<figure><img src="image_63.png" /><figcaption>■ **Figure 5** The 2-local 0-layered gadget. $C_2$ contains the colored vertices.</figcaption></figure>

<figure><img src="image_64.png" /><figcaption>■ **Figure 4** The 1-layered gadget $(H, B, C)$. $C$ contains the colored vertices.</figcaption></figure>

<figure><img src="image_65.png" /><figcaption>■ **Figure 6** The 2-IC gadget. $C_2$ contains the colored vertices.</figcaption></figure>

We define the sets $B = \{b, \bar{b}\}$ and $C = \{b, u_1, u_2, v_1, v_2\}$.

The triple $(H, B, C)$ is called the 1-layered gadget (see Fig. 4).

► **Definition 26** (The $r$-local 0-layered gadget). Given an integer $r > 1$ (respectively $r = 1$), let $H_r$ be the bipartite planar graph of size $4r + 2$ (respectively 8) such that:

■ its vertices are denoted $a_i$ and $b_i$ for $i \in \llbracket 2r+1 \rrbracket$ (respectively $i \in \llbracket 4 \rrbracket$),

■ for each $i \in \llbracket 2r \rrbracket$ (respectively $i \in \llbracket 3 \rrbracket$), both $a_i$ and $b_i$ are adjacent to $a_{i+1}$ and $b_{i+1}$

We define the sets $B_r = \{a_1, b_1\}$ and $C_r = \{a_i \mid i \in \llbracket 2r+1 \rrbracket\}$ (respectively $C_1 = \{a_1, a_2, a_3, a_4\}$). The triple $(H_r, B_r, C_r)$ is called the $r$-local 0-layered gadget (see Fig. 5).

For each positive integer $r$, $r$-LD and $r$-MD are $r$-local 0-layered problems, whereas $r$-IC is not 0-layered. We define a specific gadget for this remaining problem.

► **Definition 27** (The $r$-IC gadget). Given a positive integer $r$, let $H_r$ be the bipartite planar graph of size $6r + 4$ such that:

■ its vertices are denoted $a_{i-1}$ and $b_{i-1}$ for $i \in \llbracket r+2 \rrbracket$, and $a_i^j$ and $b_i^j$ for $i \in \llbracket r \rrbracket$ and $j \in \llbracket 2 \rrbracket$.

We also denote $a_0$ as $a_{r+1}^1$ and $a_{r+1}^2$ and we denote $b_0$ as $b_{r+1}^1$, $b_{r+1}^2$, $a_0^1$ and $a_0^2$.

■ the edges are all included in the six following paths

■ from $a_0$ to $a_{r+1}$ such that $d(a_0, a_i) = i$ for $i \in \llbracket r+1 \rrbracket$.

■ from $b_0$ to $b_{r+1}$ such that $d(b_0, b_i) = i$ for $i \in \llbracket r+1 \rrbracket$.

■ from $a_0^1$ to $a_{r+1}^1$ such that $d(a_0^1, a_i^1) = i$ for $i \in \llbracket r+1 \rrbracket$.

■ from $a_0^2$ to $a_{r+1}^2$ such that $d(a_0^2, a_i^2) = i$ for $i \in \llbracket r+1 \rrbracket$.

■ from $b_1^1$ to $b_{r+1}^1$ such that $d(b_1^1, b_i^1) = i - 1$ for $i \in \llbracket r+1 \rrbracket$.

■ from $b_1^2$ to $b_{r+1}^2$ such that $d(b_1^2, b_i^2) = i - 1$ for $i \in \llbracket r+1 \rrbracket$.

We define the sets $B_r = \{b_1^1, b_1^2\}$ and $C_r = \{a_{r+1}, b_{r+1}\} \cup \bigcup_{i \in \llbracket r+1 \rrbracket} \{a_i^1, b_i^1\}$.

The triple $(H_r, B_r, C_r)$ is called the $r$-IC gadget (see Fig. 6).

As expected, we have the following propositions:
10:12 On the Distance Identifying Set Meta-Problem

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

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

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

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

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

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

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

5 Conclusion

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