Approximability of Connected Factors

Kamiel Cornelissen, R.P. Hoeksma, Bodo Manthey, N.S. Narayanaswamy, C.S. Rahul

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)

Abstract

Finding a d-regular spanning subgraph (or d-factor) of a graph is easy by Tutte’s reduction to the matching problem. By the same reduction, it is easy to find a minimal or maximal d-factor of a graph. However, if we require that the d-factor is connected, these problems become NP-hard – finding a minimal connected 2-factor is just the traveling salesman problem (TSP). Given a complete graph with edge weights that satisfy the triangle inequality, we consider the problem of finding a minimal connected d-factor. We give a 3-approximation for all d and improve this to an (r + 1)-approximation for even d, where r is the approximation ratio of the TSP. This yields a 2.5-approximation for even d. The same algorithm yields an (r + 1)-approximation for the directed version of the problem, where r is the approximation ratio of the asymmetric TSP. We also show that none of these minimization problems can be approximated better than the corresponding TSP. Finally, for the decision problem of deciding whether a given graph contains a connected d-factor, we extend known hardness results.
Original languageUndefined
Title of host publicationProceedings of the 11th Workshop on Approximation and Online Algorithms (WAOA 2013)
EditorsC. Kaklamanis, K. Pruhs
Place of PublicationBerlin, Germany
PublisherSpringer
Pages120-131
Number of pages12
ISBN (Print)978-3-319-08000-0
DOIs
Publication statusPublished - 2014
Event11th Workshop on Approximation and Online Algorithms 2013 - Sophia Antipolis, France
Duration: 5 Sep 20136 Sep 2013
http://algo2013.inria.fr/waoa.shtml

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
Volume8447
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th Workshop on Approximation and Online Algorithms 2013
Abbreviated titleWAOA 2013
CountryFrance
CitySophia Antipolis
Period5/09/136/09/13
Internet address

Keywords

  • EWI-24832
  • Graph factors
  • METIS-305910
  • Approximation algorithms
  • IR-91426

Cite this

Cornelissen, K., Hoeksma, R. P., Manthey, B., Narayanaswamy, N. S., & Rahul, C. S. (2014). Approximability of Connected Factors. In C. Kaklamanis, & K. Pruhs (Eds.), Proceedings of the 11th Workshop on Approximation and Online Algorithms (WAOA 2013) (pp. 120-131). (Lecture Notes in Computer Science; Vol. 8447). Berlin, Germany: Springer. https://doi.org/10.1007/978-3-319-08001-7_11
Cornelissen, Kamiel ; Hoeksma, R.P. ; Manthey, Bodo ; Narayanaswamy, N.S. ; Rahul, C.S. / Approximability of Connected Factors. Proceedings of the 11th Workshop on Approximation and Online Algorithms (WAOA 2013). editor / C. Kaklamanis ; K. Pruhs. Berlin, Germany : Springer, 2014. pp. 120-131 (Lecture Notes in Computer Science).
@inproceedings{6e093f437cb44691a7366e78c713c7fb,
title = "Approximability of Connected Factors",
abstract = "Finding a d-regular spanning subgraph (or d-factor) of a graph is easy by Tutte’s reduction to the matching problem. By the same reduction, it is easy to find a minimal or maximal d-factor of a graph. However, if we require that the d-factor is connected, these problems become NP-hard – finding a minimal connected 2-factor is just the traveling salesman problem (TSP). Given a complete graph with edge weights that satisfy the triangle inequality, we consider the problem of finding a minimal connected d-factor. We give a 3-approximation for all d and improve this to an (r + 1)-approximation for even d, where r is the approximation ratio of the TSP. This yields a 2.5-approximation for even d. The same algorithm yields an (r + 1)-approximation for the directed version of the problem, where r is the approximation ratio of the asymmetric TSP. We also show that none of these minimization problems can be approximated better than the corresponding TSP. Finally, for the decision problem of deciding whether a given graph contains a connected d-factor, we extend known hardness results.",
keywords = "EWI-24832, Graph factors, METIS-305910, Approximation algorithms, IR-91426",
author = "Kamiel Cornelissen and R.P. Hoeksma and Bodo Manthey and N.S. Narayanaswamy and C.S. Rahul",
note = "10.1007/978-3-319-08001-7_11",
year = "2014",
doi = "10.1007/978-3-319-08001-7_11",
language = "Undefined",
isbn = "978-3-319-08000-0",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "120--131",
editor = "C. Kaklamanis and K. Pruhs",
booktitle = "Proceedings of the 11th Workshop on Approximation and Online Algorithms (WAOA 2013)",

}

Cornelissen, K, Hoeksma, RP, Manthey, B, Narayanaswamy, NS & Rahul, CS 2014, Approximability of Connected Factors. in C Kaklamanis & K Pruhs (eds), Proceedings of the 11th Workshop on Approximation and Online Algorithms (WAOA 2013). Lecture Notes in Computer Science, vol. 8447, Springer, Berlin, Germany, pp. 120-131, 11th Workshop on Approximation and Online Algorithms 2013, Sophia Antipolis, France, 5/09/13. https://doi.org/10.1007/978-3-319-08001-7_11

Approximability of Connected Factors. / Cornelissen, Kamiel; Hoeksma, R.P.; Manthey, Bodo; Narayanaswamy, N.S.; Rahul, C.S.

Proceedings of the 11th Workshop on Approximation and Online Algorithms (WAOA 2013). ed. / C. Kaklamanis; K. Pruhs. Berlin, Germany : Springer, 2014. p. 120-131 (Lecture Notes in Computer Science; Vol. 8447).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Approximability of Connected Factors

AU - Cornelissen, Kamiel

AU - Hoeksma, R.P.

AU - Manthey, Bodo

AU - Narayanaswamy, N.S.

AU - Rahul, C.S.

N1 - 10.1007/978-3-319-08001-7_11

PY - 2014

Y1 - 2014

N2 - Finding a d-regular spanning subgraph (or d-factor) of a graph is easy by Tutte’s reduction to the matching problem. By the same reduction, it is easy to find a minimal or maximal d-factor of a graph. However, if we require that the d-factor is connected, these problems become NP-hard – finding a minimal connected 2-factor is just the traveling salesman problem (TSP). Given a complete graph with edge weights that satisfy the triangle inequality, we consider the problem of finding a minimal connected d-factor. We give a 3-approximation for all d and improve this to an (r + 1)-approximation for even d, where r is the approximation ratio of the TSP. This yields a 2.5-approximation for even d. The same algorithm yields an (r + 1)-approximation for the directed version of the problem, where r is the approximation ratio of the asymmetric TSP. We also show that none of these minimization problems can be approximated better than the corresponding TSP. Finally, for the decision problem of deciding whether a given graph contains a connected d-factor, we extend known hardness results.

AB - Finding a d-regular spanning subgraph (or d-factor) of a graph is easy by Tutte’s reduction to the matching problem. By the same reduction, it is easy to find a minimal or maximal d-factor of a graph. However, if we require that the d-factor is connected, these problems become NP-hard – finding a minimal connected 2-factor is just the traveling salesman problem (TSP). Given a complete graph with edge weights that satisfy the triangle inequality, we consider the problem of finding a minimal connected d-factor. We give a 3-approximation for all d and improve this to an (r + 1)-approximation for even d, where r is the approximation ratio of the TSP. This yields a 2.5-approximation for even d. The same algorithm yields an (r + 1)-approximation for the directed version of the problem, where r is the approximation ratio of the asymmetric TSP. We also show that none of these minimization problems can be approximated better than the corresponding TSP. Finally, for the decision problem of deciding whether a given graph contains a connected d-factor, we extend known hardness results.

KW - EWI-24832

KW - Graph factors

KW - METIS-305910

KW - Approximation algorithms

KW - IR-91426

U2 - 10.1007/978-3-319-08001-7_11

DO - 10.1007/978-3-319-08001-7_11

M3 - Conference contribution

SN - 978-3-319-08000-0

T3 - Lecture Notes in Computer Science

SP - 120

EP - 131

BT - Proceedings of the 11th Workshop on Approximation and Online Algorithms (WAOA 2013)

A2 - Kaklamanis, C.

A2 - Pruhs, K.

PB - Springer

CY - Berlin, Germany

ER -

Cornelissen K, Hoeksma RP, Manthey B, Narayanaswamy NS, Rahul CS. Approximability of Connected Factors. In Kaklamanis C, Pruhs K, editors, Proceedings of the 11th Workshop on Approximation and Online Algorithms (WAOA 2013). Berlin, Germany: Springer. 2014. p. 120-131. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-08001-7_11