Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.01.2014 | Ausgabe 1/2014

Journal of Combinatorial Optimization 1/2014

Distance-\(d\) independent set problems for bipartite and chordal graphs

Zeitschrift:
Journal of Combinatorial Optimization > Ausgabe 1/2014
Autoren:
Hiroshi Eto, Fengrui Guo, Eiji Miyano
Wichtige Hinweise
A preliminary version of this paper appeared in Proceedings of COCOA 2012 Eto et al. (2012).

Abstract

The paper studies a generalization of the Independent Set problem (IS for short). A distance-\(d\) independent set for an integer \(d\ge 2\) in an unweighted graph \(G = (V, E)\) is a subset \(S\subseteq V\) of vertices such that for any pair of vertices \(u, v \in S\), the distance between \(u\) and \(v\) is at least \(d\) in \(G\). Given an unweighted graph \(G\) and a positive integer \(k\), the Distance-\(d\) Independent Set problem (D \(d\) IS for short) is to decide whether \(G\) contains a distance-\(d\) independent set \(S\) such that \(|S| \ge k\). D2IS is identical to the original IS. Thus D2IS is \(\mathcal{NP}\)-complete even for planar graphs, but it is in \(\mathcal{P}\) for bipartite graphs and chordal graphs. In this paper we investigate the computational complexity of D \(d\) IS, its maximization version MaxD \(d\) IS, and its parameterized version ParaD \(d\) IS(\(k\)), where the parameter is the size of the distance-\(d\) independent set: (1) We first prove that for any \(\varepsilon >0\) and any fixed integer \(d\ge 3\), it is \(\mathcal{NP}\)-hard to approximate MaxD \(d\) IS to within a factor of \(n^{1/2-\varepsilon }\) for bipartite graphs of \(n\) vertices, and for any fixed integer \(d\ge 3\), ParaD \(d\) IS(\(k\)) is \(\mathcal{W}[1]\)-hard for bipartite graphs. Then, (2) we prove that for every fixed integer \(d\ge 3\), D \(d\) IS remains \(\mathcal{NP}\)-complete even for planar bipartite graphs of maximum degree three. Furthermore, (3) we show that if the input graph is restricted to chordal graphs, then D \(d\) IS can be solved in polynomial time for any even \(d\ge 2\), whereas D \(d\) IS is \(\mathcal{NP}\)-complete for any odd \(d\ge 3\). Also, we show the hardness of approximation of MaxD \(d\) IS and the \(\mathcal{W}[1]\)-hardness of ParaD \(d\) IS(\(k\)) on chordal graphs for any odd \(d\ge 3\).

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 1/2014

Journal of Combinatorial Optimization 1/2014 Zur Ausgabe

EditorialNotes

Preface

Premium Partner

    Bildnachweise