On Algorithms Employing Treewidth for L-bounded Cut Problems
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10384868" target="_blank" >RIV/00216208:11320/18:10384868 - isvavai.cz</a>
Result on the web
<a href="http://jgaa.info/getPaper?id=462" target="_blank" >http://jgaa.info/getPaper?id=462</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.7155/jgaa.00462" target="_blank" >10.7155/jgaa.00462</a>
Alternative languages
Result language
angličtina
Original language name
On Algorithms Employing Treewidth for L-bounded Cut Problems
Original language description
Given a graph G = (V, E) with two distinguished vertices s, t ELEMENT OF V and an integer parameter L > 0, an L-bounded cut is a subset F of edges (vertices) such that the every path between s and t in GF has length more than L. The task is to find an L-bounded cut of minimum cardinality. Though the problem is very simple to state and has been studied since the beginning of the 70's, it is not much understood yet. The problem is known to be N P-hard to approximate within a small constant factor even for L GREATER-THAN OR EQUAL TO 4 (for L GREATER-THAN OR EQUAL TO 5 for the vertex-deletion version). On the other hand, the best known approximation algorithm for general graphs has approximation ratio only O(n^{2/3}) in the edge case, and O(sqrt n) in the vertex case, where n denotes the number of vertices. We show that for planar graphs, it is possible to solve both the edge- and the vertex-deletion version of the problem optimally in O((L+2)^{3L} n) time. That is, the problem is fixed-parameter tractable (FPT) with respect to L on planar graphs. Furthermore, we show that the problem remains FPT even for bounded genus graphs, a super class of planar graphs. Our second contribution deals with approximations of the vertex- deletion version of the problem. We describe an algorithm that for a given graph G, its tree decomposition of width τ and vertices s and t computes a τ -approximation of the minimum L-bounded s - t vertex cut; if the decomposition is not given, then the approximation ratio is O(τ sqrt{log τ}). For graphs with treewidth bounded by O(n 1/2-epsilon) for any epsilon > 0, but not by a constant, this is the best approximation in terms of n that we are aware of.
Czech name
—
Czech description
—
Classification
Type
J<sub>SC</sub> - Article in a specialist periodical, which is included in the SCOPUS database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA15-11559S" target="_blank" >GA15-11559S: Extended Formulation of Polytopes</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Journal of Graph Algorithms and Applications
ISSN
1526-1719
e-ISSN
—
Volume of the periodical
22
Issue of the periodical within the volume
2
Country of publishing house
US - UNITED STATES
Number of pages
15
Pages from-to
177-191
UT code for WoS article
—
EID of the result in the Scopus database
2-s2.0-85044206682