nach oben

Theory of Computing Systems

Erschienen in:

01.01.2016

Approximating the Sparsest k-Subgraph in Chordal Graphs

verfasst von: Rémi Watrigant, Marin Bougeret, Rodolphe Giroudeau

Erschienen in: Theory of Computing Systems | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Given a simple undirected graph G = (V, E) and an integer k < |V|, the Sparsest k-Subgraph problem asks for a set of k vertices which induces the minimum number of edges. As a generalization of the classical independent set problem, Sparsest k-Subgraph is 𝓝𝓟-hard and even not approximable unless 𝓟𝓝𝓟 in general graphs. Thus, we investigate Sparsest k-Subgraph in graph classes where independent set is polynomial-time solvable, such as subclasses of perfect graphs. Our two main results are the 𝓝𝓟-hardness of Sparsest k-Subgraph on chordal graphs, and a greedy 2-approximation algorithm. Finally, we also show how to derive a P T A S for Sparsest k-Subgraph on proper interval graphs.

Vorheriger Artikel Min-Sum 2-Paths Problems

Nächster Artikel Low Dimensional Embeddings of Doubling Metrics

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Apollonio, N., Sebő, A.: Minconvex Factors of Prescribed Size in Graphs. SIAM J. Discret. Math. 23(3), 1297–1310 (2009)MATHMathSciNetCrossRef

Apollonio, N., Simeone, B.: The Maximum Vertex Coverage Problem on Bipartite Graphs. in press (2013)

Brandsta̋d, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Soc. Ind. Appl. Math. (1987)

Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting High Log-Densities: an \(\mathcal {O}(n^{1/4})\) Approximation for Densest k-Subgraph. In: Proceedings of the 42nd ACM symposium on Theory of Computing, pp. 201–210 (2010)

Bourgeois, N., Giannakos, A., Lucarelli, G., Milis, I., Paschos, V.Th., Pottié, O.: The Max Quasi-Independent Set Problem. J. Comb. Optim. 23(1), 94–117 (2012)MATHMathSciNetCrossRef

Broersma, H., Golovach, P.A., Patel, V.: Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width. In: Proceedings of the 6th international conference on Parameterized and Exact Computation, pp. 207–218 (2012)

Bshouty, N., Burroughs, L.: Massaging a Linear Programming Solution to Give a 2-Approximation for a Generalization of the Vertex Cover Problem. In: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, pp. 298–308 (1998)

Leizhen Cai.: Parameterized Complexity of Cardinality Constrained Optimization Problems. Comput. J. 51(1), 102–121 (2008)

Chen, D., Fleischer, R., Li, J.: Densest k-Subgraph Approximation on Intersection Graphs. In: Proceedings of the 8th international Conference on Approximation and Online Algorithms, pp. 83–93 (2011)

10.

Corneil, D.G., Perl, Y.: Clustering and Domination in Perfect Graphs. Discret. Appl. Math. 9(1), 27–39 (1984)MATHMathSciNetCrossRef

11.

Fulkerson, D., Gross, O.: Incidence Matrices and Interval Graphs. Pac. J. Math. 15, 835–855 (1965)MATHMathSciNetCrossRef

12.

Goldschmidt, O., Hochbaum, D.S.: k-Edge Subgraph Problems. Discret. Appl. Math. 74(2), 159–169 (1997)MATHMathSciNetCrossRef

13.

Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of vertex cover variants. Theory Comput. Syst. 41(3), 501–520 (2007)MATHMathSciNetCrossRef

14.

Joret, G., Vetta, A.: Reducing the rank of a matroid, CoRR. arXiv: 1211.4853 (2012)

15.

Kneis, J., Langer, A., Rossmanith, P.: Improved Upper Bounds for Partial Vertex Cover. In: Proceedings of the 34th Workshop of Graph Theoretic Concepts in Computer Science, pp. 240–251 (2008)

16.

Liazi, M., Milis, I., Zissimopoulos, V.: A constant approximation algorithm for the densest k-Subgraph problem on chordal graphs. Inf. Process. Lett. 108(1), 29–32 (2008)MATHMathSciNetCrossRef

17.

Nonner, T.: PTAS for Densest k-Subgraph in Interval Graphs. In: Proceedings of the 12th International Conference on Algorithms and Data Structures, pp. 631–641 (2011)

18.

Watrigant, R., Bougeret, M., Giroudeau, R.: The k-Sparsest Subgraph Problem, Technical Report RR-12019. LIRMM (2012)

Titel: Approximating the Sparsest k-Subgraph in Chordal Graphs
verfasst von: Rémi Watrigant
Marin Bougeret
Rodolphe Giroudeau
Publikationsdatum: 01.01.2016
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 1/2016
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-014-9568-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2016

Low Dimensional Embeddings of Doubling Metrics

On Fixed Cost k-Flow Problems

Approximately Counting Approximately-Shortest Paths in Directed Acyclic Graphs

On Two Continuum Armed Bandit Problems in High Dimensions

Foreword of the Special Issue Dedicated to the 2013 Workshop on Approximation and Online Algorithms

Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation

Premium Partner