S. ?. For, 2}| = 1 for every If g(v i ) = 2, we set that u(v i ) is the center of its star for all i, 1 ? i ? n. Otherwise, u(v i ) is a leaf of a star (if g(v i ) = 1) or 715 it is not in a star (if g(v i ) = 0). Thus, we get that S?S 1 + |V (S)| ? k. References References [AK97] Paola Alimonti and Viggo Kann. Hardness of approximating problems on cubic graphs, Algorithms and Complexity, volume 1203 of Lecture Notes in Computer Science, pp.288-298

J. Boissonnat, C. S. Karthik, and S. Tavenas, Building Efficient and Compact Data Structures for Simplicial Complexes, International Symposium on Computational Geometry 2015, 2015.
DOI : 10.1007/s00453-016-0207-y

URL : https://hal.archives-ouvertes.fr/hal-01145407

[. Boissonnat and C. Maria, The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes, Algorithmica, vol.132, issue.23, pp.406-427, 2014.
DOI : 10.1007/s00453-014-9887-3

URL : https://hal.archives-ouvertes.fr/hal-01108416

M. R. Garey and D. S. Johnson, The Rectilinear Steiner Tree Problem is $NP$-Complete, SIAM Journal on Applied Mathematics, vol.32, issue.4, pp.826-834, 1977.
DOI : 10.1137/0132071

D. [. Garey, M. R. Johnson, D. S. Garey, L. Johnson, and . Stockmeyer, Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co Some simplified NP-complete problems, Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC '74, pp.800-847, 1974.

]. D. Hoc83 and . Hochbaum, Efficient bounds for the stable set, vertex cover and set packing problems, Discrete Applied Mathematics, vol.6, issue.3, pp.243-254, 1983.

V. Th and . Paschos, Combinatorial Optimization and Theoretical Computer Science - Interfaces and Perspectives: 30th Anniversary of the LAMSADE, 2008.