Abstract
A general instance of a Degree-Constrained Subgraph problem consists of an edge-weighted or vertex-weighted graph G and the objective is to find an optimal weighted subgraph, subject to certain degree constraints on the vertices of the subgraph. This paper considers two natural Degree-Constrained Subgraph problems and studies their behavior in terms of approximation algorithms. These problems take as input an undirected graph G = (V,E), with |V| = n and |E| = m. Our results, together with the definition of the two problems, are listed below.
-
The Maximum Degree-Bounded Connected Subgraph problem (MDBCS d ) takes as input a weight function \(\omega : E \rightarrow \mathbb R^+\) and an integer d ≥ 2, and asks for a subset E′ ⊆ E such that the subgraph G′ = (V,E′) is connected, has maximum degree at most d, and ∑ e ∈ E′ ω(e) is maximized. This problem is one of the classical NP-hard problems listed by Garey and Johnson in [Computers and Intractability, W.H. Freeman, 1979], but there were no results in the literature except for d = 2. We prove that MDBCS d is not in Apx for any d ≥ 2 (this was known only for d = 2) and we provide a \((\min \{m/ \log n,\ nd/(2 \log n)\})\)-approximation algorithm for unweighted graphs, and a \((\min\{n/2,\ m/d\})\)-approximation algorithm for weighted graphs. We also prove that when G has a low-degree spanning tree, in terms of d, MDBCS d can be approximated within a small constant factor in unweighted graphs.
-
The Minimum Subgraph of Minimum Degree ≥ d (MSMD d ) problem requires finding a smallest subgraph of G (in terms of number of vertices) with minimum degree at least d. We prove that MSMD d is not in Apx for any d ≥ 3 and we provide an \(\mathcal{O}(n/\log n)\)-approximation algorithm for the class of graphs excluding a fixed graph as a minor, using dynamic programming techniques and a known structural result on graph minors.
This work has been partially supported by European project IST FET AEOLUS, PACA region of France, Ministerio de Educación y Ciencia of Spain, European Regional Development Fund under project TEC2005-03575, Catalan Research Council under project 2005SGR00256 and COST action 293 GRAAL, and has been done in the context of the crc Corso with France Telecom.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Addario-Berry, L., Dalal, K., Reed, B.: Degree constrained subgraphs. Discrete Appl. Math. 156(7), 1168–1174 (2008)
Alon, N., Yuster, R., Zwick, U.: Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs. In: Proc. 26th ACM Symp. on Theory of Computing, New York, USA, pp. 326–335 (1994)
Amini, O., Peleg, D., Pérennes, S., Sau, I., Saurabh, S.: Degree-Constrained Subgraph Problems: Hardness and Approximation Results. Technical Report 6690, INRIA, Accessible in Ignasi Sau’s homepage (2008)
Amini, O., Pérennes, S., Sau, I.: Hardness and Approximation of Traffic Grooming. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 561–573. Springer, Heidelberg (2007)
Amini, O., Sau, I., Saurabh, S.: Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 13–29. Springer, Heidelberg (2008)
Björklund, A., Husfeldt, T.: Finding a Path of Superlogarithmic Length. SIAM J. on Computing 32(6), 1395–1402 (2003)
Demaine, E., Hajiaghayi, M., Kawarabayashi, K.C.: Algorithmic Graph Minor Theory: Decomposition, Approximation and Coloring. In: Proc. 46th IEEE Symp. on Foundations of Computer Science, pp. 637–646 (October 2005)
Erdős, P., Faudree, R., Rousseau, C.C., Schelp, R.H.: Subgraphs of minimal degree k. Discrete Math. 85(1), 53–58 (1990)
Feige, U., Peleg, D., Kortsarz, G.: The Dense k-Subgraph Problem. Algorithmica 29(3), 410–421 (2001)
Fürer, M., Raghavachari, B.: Approximating the minimum-degree spanning tree to within one from the optimal degree. In: Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms, USA, pp. 317–324 (1992)
Fürer, M., Raghavachari, B.: Approximating the minimum-degree steiner tree to within one of optimal. J. Algorithms, 409–423 (1994)
Gabow, H.: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proc. 15th ACM Symp. on Theory of Computing, USA, pp. 448–456. ACM Press, New York (1983)
Garey, M., Johnson, D.: Computers and Intractability. W.H. Freeman, San Francisco (1979)
Karger, D., Motwani, R., Ramkumar, G.: On approximating the longest path in a graph. Algorithmica 18(1), 82–98 (1997)
Khot, S.: Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique. In: Proc. 45th IEEE Symp. on Foundations of Computer Science, pp. 136–145 (2004)
Lovász, L., Plummer, M.: Matching Theory. Annals of Discrete Math, vol. 29. North-Holland, Amsterdam (1986)
Lund, C., Yannakakis, M.: The Approximation of Maximum Subgraph Problems. In: Proc. 20th Int. Colloq. on Automata, Languages, and Programming (1993)
Munro, J., Raman, V.: Succinct Representation of Balanced Parentheses and Static Trees. SIAM J. on Computing 31(3), 762–776 (2001)
Papadimitriou, C., Yannakakis, M.: The traveling salesman problem with distances one and two. Mathematics of Operations Research 18(1), 1–11 (1993)
Ravi, R., Marathe, M., Ravi, S., Rosenkrantz, D., Hunt III, H.B.: Approximation algorithms for degree-constrained minimum-cost network-design problems. Algorithmica 31(1), 58–78 (2001)
Richard, O.: The Number of Trees. Annals of Mathematics, Second Series 49(3), 583–599 (1948)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Amini, O., Peleg, D., Pérennes, S., Sau, I., Saurabh, S. (2009). Degree-Constrained Subgraph Problems: Hardness and Approximation Results. In: Bampis, E., Skutella, M. (eds) Approximation and Online Algorithms. WAOA 2008. Lecture Notes in Computer Science, vol 5426. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-93980-1_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-93980-1_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-93979-5
Online ISBN: 978-3-540-93980-1
eBook Packages: Computer ScienceComputer Science (R0)