Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems. / Bliznets, Ivan; Cygan, Marek; Komosa, Pawel; Mach, Lukáš; Pilipczuk, Michal.
27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016. ред. / Robert Krauthgamer. Association for Computing Machinery, 2016. стр. 1132-1151 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Том 2).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems
AU - Bliznets, Ivan
AU - Cygan, Marek
AU - Komosa, Pawel
AU - Mach, Lukáš
AU - Pilipczuk, Michal
PY - 2016/1/1
Y1 - 2016/1/1
N2 - In this work, we focus on several completion problems for subclasses of chordal graphs: minimum Fill-In, Interval Completion, Proper Interval Completion, Threshold Completion, and Trivially Perfect Completion. In these problems, the task is to add at most k edges to a given graph in order to obtain a chordal, interval, proper interval, threshold, or trivially perfect graph, respectively. We prove the following lower bounds for all these problems, as well as for the related Chain Completion problem: Assuming the Exponential Time Hypothesis, none of these problems can be solved in time 2σ(n1/2/logcn) or 2σ (kl/4/logck). nσ (1), for some integer c. Assuming the non-existence of a subexponential-time approximation scheme for Min Bisection on d-regular graphs, for some constant d, none of these problems can be solved in time 2°(n) or 2° (√nk). nσ(1). The second result is an evidence, that a significant improvement of the best known algorithms for parameterized completion problems would lead to a surprising breakthrough in the design of approximation algorithms for MlN bisection.
AB - In this work, we focus on several completion problems for subclasses of chordal graphs: minimum Fill-In, Interval Completion, Proper Interval Completion, Threshold Completion, and Trivially Perfect Completion. In these problems, the task is to add at most k edges to a given graph in order to obtain a chordal, interval, proper interval, threshold, or trivially perfect graph, respectively. We prove the following lower bounds for all these problems, as well as for the related Chain Completion problem: Assuming the Exponential Time Hypothesis, none of these problems can be solved in time 2σ(n1/2/logcn) or 2σ (kl/4/logck). nσ (1), for some integer c. Assuming the non-existence of a subexponential-time approximation scheme for Min Bisection on d-regular graphs, for some constant d, none of these problems can be solved in time 2°(n) or 2° (√nk). nσ(1). The second result is an evidence, that a significant improvement of the best known algorithms for parameterized completion problems would lead to a surprising breakthrough in the design of approximation algorithms for MlN bisection.
UR - http://www.scopus.com/inward/record.url?scp=84963686450&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84963686450
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1132
EP - 1151
BT - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
A2 - Krauthgamer, Robert
PB - Association for Computing Machinery
T2 - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
Y2 - 10 January 2016 through 12 January 2016
ER -
ID: 49787517