DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2019.12

Computing the Largest Bond of a Graph

Authors: Gabriel L. Duarte, Daniel Lokshtanov, Lehilton L. C. Pedrosa, Rafael C. S. Schouery, and Uéverton S. Souza

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract

A bond of a graph G is an inclusion-wise minimal disconnecting set of G, i.e., bonds are cut-sets that determine cuts [S,V\S] of G such that G[S] and G[V\S] are both connected. Given s,t in V(G), an st-bond of G is a bond whose removal disconnects s and t. Contrasting with the large number of studies related to maximum cuts, there are very few results regarding the largest bond of general graphs. In this paper, we aim to reduce this gap on the complexity of computing the largest bond and the largest st-bond of a graph. Although cuts and bonds are similar, we remark that computing the largest bond of a graph tends to be harder than computing its maximum cut. We show that Largest Bond remains NP-hard even for planar bipartite graphs, and it does not admit a constant-factor approximation algorithm, unless P = NP. We also show that Largest Bond and Largest st-Bond on graphs of clique-width w cannot be solved in time f(w) x n^{o(w)} unless the Exponential Time Hypothesis fails, but they can be solved in time f(w) x n^{O(w)}. In addition, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, but they do not admit polynomial kernels unless NP subseteq coNP/poly.

Cite as

Gabriel L. Duarte, Daniel Lokshtanov, Lehilton L. C. Pedrosa, Rafael C. S. Schouery, and Uéverton S. Souza. Computing the Largest Bond of a Graph. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{duarte_et_al:LIPIcs.IPEC.2019.12,
  author =	{Duarte, Gabriel L. and Lokshtanov, Daniel and Pedrosa, Lehilton L. C. and Schouery, Rafael C. S. and Souza, U\'{e}verton S.},
  title =	{{Computing the Largest Bond of a Graph}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.12},
  URN =		{urn:nbn:de:0030-drops-114732},
  doi =		{10.4230/LIPIcs.IPEC.2019.12},
  annote =	{Keywords: bond, cut, maximum cut, connected cut, FPT, treewidth, clique-width}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2019.14

An Asymptotically Optimal Approximation Algorithm for the Travelling Car Renter Problem

Authors: Lehilton L. C. Pedrosa, Greis Y. O. Quesquén, and Rafael C. S. Schouery

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract

In the classical Travelling Salesman Problem (TSP), one wants to find a route that visits a set of n cities, such that the total travelled distance is minimum. An often considered generalization is the Travelling Car Renter Problem (CaRS), in which the route is travelled by renting a set of cars and the cost to travel between two given cities depends on the car that is used. The car renter may choose to swap vehicles at any city, but must pay a fee to return the car to its pickup location. This problem appears in logistics and urban transportation when the vehicles can be provided by multiple companies, such as in the tourism sector. In this paper, we consider the case in which the return fee is some fixed number g >= 0, which we call the Uniform CaRS (UCaRS). We show that, already for this version, there is no o(log n)-approximation algorithm unless P = NP. The main contribution is an O(log n)-approximation algorithm for the problem, which is based on the randomized rounding of an exponentially large LP-relaxation.

Cite as

Lehilton L. C. Pedrosa, Greis Y. O. Quesquén, and Rafael C. S. Schouery. An Asymptotically Optimal Approximation Algorithm for the Travelling Car Renter Problem. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{pedrosa_et_al:OASIcs.ATMOS.2019.14,
  author =	{Pedrosa, Lehilton L. C. and Quesqu\'{e}n, Greis Y. O. and Schouery, Rafael C. S.},
  title =	{{An Asymptotically Optimal Approximation Algorithm for the Travelling Car Renter Problem}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{14:1--14:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.14},
  URN =		{urn:nbn:de:0030-drops-114263},
  doi =		{10.4230/OASIcs.ATMOS.2019.14},
  annote =	{Keywords: Approximation Algorithm, Travelling Car Renter Problem, LP-rounding, Separation Problem}
}

Search Results

Documents authored by Schouery, Rafael C. S.

Computing the Largest Bond of a Graph

Abstract

Cite as

An Asymptotically Optimal Approximation Algorithm for the Travelling Car Renter Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message