Metric dimension (graph theory)

Last updated March 13, 2024

In graph theory, the metric dimension of a graph G is the minimum cardinality of a subset S of vertices such that all other vertices are uniquely determined by their distances to the vertices in S. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.

Detailed definition

For an ordered subset $W=\{w_{1},w_{2},\dots ,w_{k}\}$ of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the ordered k-tuple $r(v|W)=(d(v,w_{1}),d(v,w_{2}),\dots ,d(v,w_{k}))$ , where d(x,y) represents the distance between the vertices x and y. The set W is a resolving set (or locating set) for G if every two vertices of G have distinct representations. The metric dimension of G is the minimum cardinality of a resolving set for G. A resolving set containing a minimum number of vertices is called a basis (or reference set) for G. Resolving sets for graphs were introduced independently by Slater (1975) and Harary & Melter (1976), while the concept of a resolving set and that of metric dimension were defined much earlier in the more general context of metric spaces by Blumenthal in his monograph Theory and Applications of Distance Geometry. Graphs are special examples of metric spaces with their intrinsic path metric.

Trees

If a tree is a path, its metric dimension is one. Otherwise, let L denote the set of leaves, degree-one vertices in the tree. Let K be the set of vertices that have degree greater than two, and that are connected by paths of degree-two vertices to one or more leaves. Then the metric dimension is |L| − |K|. A basis of this cardinality may be formed by removing from L one of the leaves associated with each vertex in K.^[1] The same algorithm is valid for the line graph of the tree, and thus any tree and its line graph have the same metric dimension.^[2]

Properties

In Chartrand et al. (2000), it is proved that:

The metric dimension of a graph $G$ is 1 if and only if $G$ is a path.
The metric dimension of an $n$ -vertex graph is $n - 1$ if and only if it is a complete graph.
The metric dimension of an $n$ -vertex graph is $n - 2$ if and only if the graph is a complete bipartite graph $K s, t$ , a split graph $K_{s}+{\overline {K_{t}}}(s\geq 1,t\geq 2)$ , or $K_{s}+(K_{1}\cup K_{t})(s,t\geq 1)$ .

Relations between the order, the metric dimension and the diameter

Khuller, Raghavachari & Rosenfeld (1996) prove the inequality $n\leq D^{\beta }+\beta$ for any $n$ -vertex graph with diameter $D$ and metric dimension $\beta$ . This bounds follows from the fact that each vertex that is not in the resolving set is uniquely determined by a distance vector of length $\beta$ with each entry being an integer between 1 and $D$ (there are precisely $D^{\beta }$ such vectors). However, the bound is only achieved for $D\leq 3$ or $\beta =1$ ; the more precise bound

n\leq \left(\lfloor 2D/3\rfloor +1\right)^{\beta }+\beta \sum _{i=1}^{\lceil D/3\rceil }(2i-1)^{\beta -1}

is proved by Hernando et al. (2010).

For specific graph classes, smaller bounds can hold. For example, Beaudou et al. (2018) proved that $n\leq (\beta D+4)(D+2)/8$ for trees (the bound being tight for even values of $D$ ), and a bound of the form $n=O(D^{2}\beta )$ for outerplanar graphs. The same authors proved that $n\leq (D\beta +1)^{t-1}$ for graphs with no complete graph of order $t$ as a minor and also gave bounds for chordal graphs and graphs of bounded treewidth. The authors Foucaud et al. (2017a) proved bounds of the form $n=O(D\beta ^{2})$ for interval graphs and permutation graphs, and bounds of the form $n=O(D\beta )$ for unit interval graphs, bipartite permutation graphs and cographs.

Computational complexity

Decision complexity

Deciding whether the metric dimension of a graph is at most a given integer is NP-complete.^[3] It remains NP-complete for bounded-degree planar graphs,^[4] split graphs, bipartite graphs and their complements, line graphs of bipartite graphs,^[5] unit disk graphs,^[6] interval graphs of diameter 2 and permutation graphs of diameter 2,^[7] and graphs of bounded treewidth.^[8]

For any fixed constant k, the graphs of metric dimension at most k can be recognized in polynomial time, by testing all possible k-tuples of vertices, but this algorithm is not fixed-parameter tractable (for the natural parameter k, the solution size). Answering a question posed by Lokshtanov (2010), Hartung & Nichterlein (2013) show that the metric dimension decision problem is complete for the parameterized complexity class W[2], implying that a time bound of the form n^O(k) as achieved by this naive algorithm is likely optimal and that a fixed-parameter tractable algorithm (for the parameterization by k) is unlikely to exist. Nevertheless, the problem becomes fixed-parameter tractable when restricted to interval graphs,^[7] and more generally to graphs of bounded tree-length,^[9] such as chordal graphs, permutation graphs or asteroidal-triple-free graphs.

Deciding whether the metric dimension of a tree is at most a given integer can be done in linear time^[10] Other linear-time algorithms exist for cographs,^[5] chain graphs,^[11] and cactus block graphs^[12] (a class including both cactus graphs and block graphs). The problem may be solved in polynomial time on outerplanar graphs.^[4] It may also be solved in polynomial time for graphs of bounded cyclomatic number,^[5] but this algorithm is again not fixed-parameter tractable (for the parameter "cyclomatic number") because the exponent in the polynomial depends on the cyclomatic number. There exist fixed-parameter tractable algorithms to solve the metric dimension problem for the parameters "vertex cover",^[13] "max leaf number",^[14] and "modular width".^[9] Graphs with bounded cyclomatic number, vertex cover number or max leaf number all have bounded treewidth, however it is an open problem to determine the complexity of the metric dimension problem even on graphs of treewidth 2, that is, series–parallel graphs.^[9]

Approximation complexity

The metric dimension of an arbitrary n-vertex graph may be approximated in polynomial time to within an approximation ratio of $2\log n$ by expressing it as a set cover problem, a problem of covering all of a given collection of elements by as few sets as possible in a given family of sets. ^[15] In the set cover problem formed from a metric dimension problem, the elements to be covered are the ${\tbinom {n}{2}}$ pairs of vertices to be distinguished, and the sets that can cover them are the sets of pairs that can be distinguished by a single chosen vertex. The approximation bound then follows by applying standard approximation algorithms for set cover. An alternative greedy algorithm that chooses vertices according to the difference in entropy between the equivalence classes of distance vectors before and after the choice achieves an even better approximation ratio, $\log n+\log \log _{2}n+1$ .^[16] This approximation ratio is close to best possible, as under standard complexity-theoretic assumptions a ratio of $(1-\epsilon )\log n$ cannot be achieved in polynomial time for any $\epsilon >0$ .^[16] The latter hardness of approximation still holds for instances restricted to subcubic graphs,^[13] and even to bipartite subcubic graphs.^[17]

Related Research Articles

In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined objective function. One well-known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals and minimizes the total weight of its edges. Further well-known variants are the Euclidean Steiner tree problem and the rectilinear minimum Steiner tree problem.

In graph theory, a vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.

In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. This appears to have been first demonstrated in Gurevich, Stockmeyer & Vishkin (1984). The first systematic work on parameterized complexity was done by Downey & Fellows (1999).

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly $k$ are called $k$ -trees, and the graphs with treewidth at most $k$ are called partial $k$ -trees. Many other well-studied graph families also have bounded treewidth.

In graph theory, a path decomposition of a graph $G$ is, informally, a representation of $G$ as a "thickened" path graph, and the pathwidth of $G$ is a number that measures how much the path was thickened to form $G$ . More formally, a path-decomposition is a sequence of subsets of vertices of $G$ such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.

In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the maximum number of colors that can be used by a greedy coloring strategy that considers the vertices of the graph in sequence and assigns each vertex its first available color, using a vertex ordering chosen to use as many colors as possible. Grundy numbers are named after P. M. Grundy, who studied an analogous concept for directed graphs in 1939. The undirected version was introduced by Christen & Selkow (1979).

<span class="mw-page-title-main">Boxicity</span> Smallest dimension where a graph can be represented as an intersection graph of boxes

In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969.

In computer science, a kernelization is a technique for designing efficient algorithms that achieve their efficiency by a preprocessing stage in which inputs to the algorithm are replaced by a smaller input, called a "kernel". The result of solving the problem on the kernel should either be the same as on the original input, or it should be easy to transform the output on the kernel to the desired output for the original problem.

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

In graph theory, the metric $k$ -center problem is a combinatorial optimization problem studied in theoretical computer science. Given $n$ cities with specified distances, one wants to build $k$ warehouses in different cities and minimize the maximum distance of a city to a warehouse. In graph theory, this means finding a set of $k$ vertices for which the largest distance of any point to its closest vertex in the $k$ -set is minimum. The vertices must be in a metric space, providing a complete graph that satisfies the triangle inequality.

In graph theory, the tree-depth of a connected undirected graph $is a numerical invariant of, the minimum height of a Trémaux tree for a supergraph of . This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages. Intuitively, where the treewidth of a graph measures how far it is from being a tree, this parameter measures how far a graph is from being a star.$

Bidimensionality theory characterizes a broad range of graph problems (bidimensional) that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs. These graph classes include planar graphs, map graphs, bounded-genus graphs and graphs excluding any fixed minor. In particular, bidimensionality theory builds on the graph minor theory of Robertson and Seymour by extending the mathematical results and building new algorithmic tools. The theory was introduced in the work of Demaine, Fomin, Hajiaghayi, and Thilikos, for which the authors received the Nerode Prize in 2015.

In the study of graph algorithms, Courcelle's theorem is the statement that every graph property definable in the monadic second-order logic of graphs can be decided in linear time on graphs of bounded treewidth. The result was first proved by Bruno Courcelle in 1990 and independently rediscovered by Borie, Parker & Tovey (1992). It is considered the archetype of algorithmic meta-theorems.

The vertex k-center problem is a classical NP-hard problem in computer science. It has application in facility location and clustering. Basically, the vertex k-center problem models the following real problem: given a city with $facilities, find the best facilities where to build fire stations. Since firemen must attend any emergency as quickly as possible, the distance from the farthest facility to its nearest fire station has to be as small as possible. In other words, the position of the fire stations must be such that every possible fire is attended as quickly as possible.$

In graph theory, the cutwidth of an undirected graph is the smallest integer $with the following property: there is an ordering of the vertices of the graph, such that every cut obtained by partitioning the vertices into earlier and later subsets of the ordering is crossed by at most edges. That is, if the vertices are numbered, then for every, the number of edges with and is at most .$

The twin-width of an undirected graph is a natural number associated with the graph, used to study the parameterized complexity of graph algorithms. Intuitively, it measures how similar the graph is to a cograph, a type of graph that can be reduced to a single vertex by repeatedly merging together twins, vertices that have the same neighbors. The twin-width is defined from a sequence of repeated mergers where the vertices are not required to be twins, but have nearly equal sets of neighbors.

A parameterized approximation algorithm is a type of algorithm that aims to find approximate solutions to NP-hard optimization problems in polynomial time in the input size and a function of a specific parameter. These algorithms are designed to combine the best aspects of both traditional approximation algorithms and fixed-parameter tractability.

The highway dimension is a graph parameter modelling transportation networks, such as road networks or public transportation networks. It was first formally defined by Abraham et al. based on the observation by Bast et al. that any road network has a sparse set of "transit nodes", such that driving from a point A to a sufficiently far away point B along the shortest route will always pass through one of these transit nodes. It has also been proposed that the highway dimension captures the properties of public transportation networks well, given that longer routes using busses, trains, or airplanes will typically be serviced by larger transit hubs. This relates to the spoke–hub distribution paradigm in transport topology optimization.

The small set expansion hypothesis or small set expansion conjecture in computational complexity theory is an unproven computational hardness assumption. Under the small set expansion hypothesis it is assumed to be computationally infeasible to distinguish between a certain class of expander graphs called "small set expanders" and other graphs that are very far from being small set expanders. This assumption implies the hardness of several other computational problems, and the optimality of certain known approximation algorithms.

References

Notes

↑ Slater 1975; Harary & Melter 1976; Khuller, Raghavachari & Rosenfeld 1996. Note Slater's nonstandard definition of the leaves of a tree.
↑ Feng, Xu & Wang 2013.
↑ Garey & Johnson 1979.
1 2 Díaz et al. 2012.
1 2 3 Epstein, Levin & Woeginger 2012.
↑ Hoffmann & Wanke 2013.
1 2 Foucaud et al. 2017b.
↑ Li & Pilipczuk 2022.
1 2 3 Belmonte et al. 2015.
↑ Slater 1975; Harary & Melter 1976.
↑ Fernau et al. 2015.
↑ Hoffmann, Elterman & Wanke 2016.
1 2 Hartung & Nichterlein 2013.
↑ Eppstein 2015.
↑ Khuller, Raghavachari & Rosenfeld 1996.
1 2 Hauptmann, Schmied & Viehmann 2012.
↑ Hartung 2014.

Bibliography

Beaudou, Laurent; Dankelmann, Peter; Foucaud, Florent; Henning, Michael A.; Mary, Arnaud; Parreau, Aline (2018), "Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension", SIAM Journal on Discrete Mathematics, 32 (2): 902–918, arXiv: 1610.01475 , doi:10.1137/16M1097833, S2CID 51882750
Belmonte, R.; Fomin, F. V.; Golovach, P. A.; Ramanujan, M. S. (2015), "Metric dimension of bounded width graphs", in Italiano, G. F.; Pighizzini, G.; Sannella, D. T. (eds.), Mathematical Foundations of Computer Science 2015 – MFCS 2015: 40th International Symposium, Milan, Italy, August 24-28, 2015, Proceedings, Lecture Notes in Computer Science, vol. 9235, Springer, pp. 115–126, doi:10.1007/978-3-662-48054-0_10, ISBN 978-3-662-48053-3 .
Blumenthal, L.M. (1953), Theory and Applications of Distance Geometry, Clarendon, Oxford.
Bonnet, E.; Purohit, N. (2019), "Metric Dimension Parameterized by Treewidth", in Jansen, B. M. P.; Telle, J. A. (eds.), Parameterized and Exact Computation 2019 – IPEC 2019: 14th International Symposium, Proceedings, Leibniz International Proceedings in Informatics (LIPIcs), vol. 148, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, pp. 5:1–5:15, arXiv: 1907.08093 , doi:10.4230/LIPIcs.IPEC.2019.5 .
Buczkowski, P.; Chartrand, G.; Poisson, C.; Zhang, P. (2003), "On $k$ -dimensional graphs and their bases", Periodica Mathematica Hungarica, 46 (1): 9–15, doi:10.1023/A:1025745406160, MR 1975342, S2CID 33390310 .
Chartrand, G.; Eroh, L.; Johnson, M. A.; Oellermann, O. R. (2000), "Resolvability in graphs and the metric dimension of a graph", Discrete Applied Mathematics , 105 (1–3): 99–113, doi:10.1016/S0166-218X(00)00198-0, hdl: 10338.dmlcz/127843 , MR 1780464 .
Díaz, J.; Pottonen, O.; Serna, M. J.; van Leeuwen, E. J. (2012), "On the complexity of metric dimension" (PDF), in Epstein, Leah; Ferragina, Paolo (eds.), Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012, Proceedings, Lecture Notes in Computer Science, vol. 7501, Springer, pp. 419–430, arXiv: 1107.2256 , doi:10.1007/978-3-642-33090-2_37, ISBN 978-3-642-33089-6 .
Eppstein, David (2015), "Metric dimension parameterized by max leaf number", Journal of Graph Algorithms and Applications , 19 (1): 313–323, arXiv: 1506.01749 , doi:10.7155/jgaa.00360, S2CID 1318601 .
Epstein, Leah; Levin, Asaf; Woeginger, Gerhard J. (2012), "The (weighted) metric dimension of graphs: hard and easy cases", in Golumbic, Martin Charles; Stern, Michal; Levy, Avivit; et al. (eds.), Graph-Theoretic Concepts in Computer Science: 38th International Workshop, WG 2012, Jerusalem, Israel, June 26-28, 2012, Revised Selected Papers, Lecture Notes in Computer Science, vol. 7551, pp. 114–125, doi:10.1007/978-3-642-34611-8_14, ISBN 978-3-642-34610-1 .
Feng, Min; Xu, Min; Wang, Kaishun (2013), "On the metric dimension of line graphs", Discrete Applied Mathematics , 161 (6): 802–805, arXiv: 1107.4140 , doi:10.1016/j.dam.2012.10.018, S2CID 36010185 .
Fernau, Henning; Heggernes, Pinar; van 't Hof, Pim; Meister, Daniel; Saei, Reza (2015), "Computing the metric dimension for chain graphs", Information Processing Letters , 115 (9): 671–676, doi:10.1016/j.ipl.2015.04.006 .
Foucaud, Florent; Mertzios, George B.; Naserasr, Reza; Parreau, Aline; Valicov, Petru (2017a), "Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds", Theoretical Computer Science, 68: 43–58, arXiv: 1507.08164 , doi:10.1016/j.tcs.2017.01.006, S2CID 25244200
Foucaud, Florent; Mertzios, George B.; Naserasr, Reza; Parreau, Aline; Valicov, Petru (2017b), "Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity", Algorithmica , 78 (3): 914–944, arXiv: 1405.2424 , doi:10.1007/s00453-016-0184-1, S2CID 1520161 .
Garey, M. R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W.H. Freeman, ISBN 0-7167-1045-5 A1.5: GT61, p. 204.
Harary, F.; Melter, R. A. (1976), "On the metric dimension of a graph", Ars Combinatoria , 2: 191–195, MR 0457289 .
Hartung, Sepp (2014), Exploring parameter spaces in coping with computational intractability, PhD thesis, Technische Universität Berlin, retrieved 2015-09-15.
Hartung, Sepp; Nichterlein, André (2013), "On the parameterized and approximation hardness of metric dimension", 2013 IEEE Conference on Computational Complexity (CCC), Stanford, CA, USA, June 5-7, 2013, Proceedings, IEEE, pp. 266–276, arXiv: 1211.1636 , doi:10.1109/CCC.2013.36, S2CID 684505 .
Hauptmann, Mathias; Schmied, Richard; Viehmann, Claus (2012), "Approximation complexity of metric dimension problem", Journal of Discrete Algorithms, 14: 214–222, doi: 10.1016/j.jda.2011.12.010 , MR 2922072 .
Hernando, Carmen; Mora, Mercè; Pelayo, Ignacio M.; Seara, Carlos; Wood, David R. (2010), "Extremal graph theory for metric dimension and diameter", Electronic Journal of Combinatorics , 17: #R30, doi: 10.37236/302 , hdl: 2117/8261 .
Hoffmann, Stefan; Elterman, Alina; Wanke, Egon (2016), "A linear time algorithm for metric dimension of cactus block graphs", Theoretical Computer Science, 630: 43–62, doi: 10.1016/j.tcs.2016.03.024
Hoffmann, Stefan; Wanke, Egon (2013), "Metric Dimension for Gabriel Unit Disk Graphs Is NP-Complete", in Bar-Noy, Amotz; Halldórsson, Magnús M. (eds.), Algorithms for Sensor Systems: 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2012, Ljubljana, Slovenia, September 13-14, 2012, Revised Selected Papers, Lecture Notes in Computer Science, vol. 7718, Springer, pp. 90–92, arXiv: 1306.2187 , doi:10.1007/978-3-642-36092-3_10, ISBN 978-3-642-36091-6, S2CID 9740623 .
Khuller, S.; Raghavachari, B.; Rosenfeld, A. (1996), "Landmarks in graphs", Discrete Applied Mathematics , 70 (3): 217–229, doi:10.1016/0166-218x(95)00106-2, hdl: 10338.dmlcz/140702 .
Li, Shaohua; Pilipczuk, Marcin (July 2022), "Hardness of metric dimension in graphs of constant treewidth", Algorithmica, 84 (11): 3110–3155, arXiv: 2102.09791 , doi:10.1007/s00453-022-01005-y, S2CID 231979414
Lokshtanov, Daniel (2010), "Open problems – Parameterized complexity and approximation algorithms: Metric Dimension", in Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Marx, Dániel (eds.), Parameterized Complexity and Approximation Algorithms, Dagstuhl Seminar Proceedings, Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik .
Slater, P. J. (1975), "Leaves of trees", Proc. 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), Congressus Numerantium, vol. 14, Winnipeg: Utilitas Math., pp. 549–559, MR 0422062 .
Slater, P. J. (1988), "Dominating and reference sets in a graph", Journal of Mathematical and Physical Sciences, 22 (4): 445–455, MR 0966610 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Slater 1975; Harary & Melter 1976; Khuller, Raghavachari & Rosenfeld 1996. Note Slater's nonstandard definition of the leaves of a tree.

[FOOTNOTEFengXuWang2013-2] Feng, Xu & Wang 2013.

[FOOTNOTEGareyJohnson1979-3] Garey & Johnson 1979.

[FOOTNOTEDíazPottonenSernavan_Leeuwen2012-4] 1 2 Díaz et al. 2012.

[FOOTNOTEEpsteinLevinWoeginger2012-5] 1 2 3 Epstein, Levin & Woeginger 2012.

[FOOTNOTEHoffmannWanke2013-6] Hoffmann & Wanke 2013.

[FOOTNOTEFoucaudMertziosNaserasrParreau2017b-7] 1 2 Foucaud et al. 2017b.

[FOOTNOTELiPilipczuk2022-8] Li & Pilipczuk 2022.

[FOOTNOTEBelmonteFominGolovachRamanujan2015-9] 1 2 3 Belmonte et al. 2015.

[10] Slater 1975; Harary & Melter 1976.

[FOOTNOTEFernauHeggernesvan_'t_HofMeister2015-11] Fernau et al. 2015.

[FOOTNOTEHoffmannEltermanWanke2016-12] Hoffmann, Elterman & Wanke 2016.

[FOOTNOTEHartungNichterlein2013-13] 1 2 Hartung & Nichterlein 2013.

[FOOTNOTEEppstein2015-14] Eppstein 2015.

[FOOTNOTEKhullerRaghavachariRosenfeld1996-15] Khuller, Raghavachari & Rosenfeld 1996.

[FOOTNOTEHauptmannSchmiedViehmann2012-16] 1 2 Hauptmann, Schmied & Viehmann 2012.

[FOOTNOTEHartung2014-17] Hartung 2014.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]