МЕГАГРАНТЫ

Лаборатория алгоритмических методов

О лаборатории

Наименование проекта Алгоритмы и сложные задачи вне полиноминального времени

Ссылка на сайт лаборатории

№ договора:
14.Z50.31.0030

Наименование ВУЗа:

ФГБУН «Санкт-петербургское отделение Математического института им. В.А. Стеклова Российской Академии Наук»

Области научных исследований:
Компьютерные и информационные науки

Цель проекта: Создание новых подходов разработки и анализа алгоритмов для NP-трудных задач.

Исследование NP-трудных задач интересно как с практической, так и с теоретической точек зрения. Для многих таких задач неизвестны даже алгоритмы, работающие быстрее полного перебора.
Построение эффективных алгоритмов является одной из фундаментальных задач современной информатики.
Алгоритмы находят применение в поисковых системах, биоинформатике, анализе данных, обработке изображений и многих других областях.
К сожалению, для решения ряда практических задач, таких как задачи составления расписаний, сегментации изображений или сборки генома, несмотря на усилия большого числа исследователей, эффективных алгоритмов до сих пор не найдено.
За последние 40 лет сложилась стройная математическая теория вычислительной сложности, объясняющая отсутствие эффективных алгоритмов для подобных задач. Основой этой теории является понятие NP-полноты.
NP-полная задача — это задача из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время. Выяснилось, что многие алгоритмические задачи тесно связаны между собой в следующем смысле: существование эффективного (заканчивающие работу за полиномиальное от длины входа число операций) алгоритма для любой из этих задач влечет за собой существование эффективного алгоритма для всех этих задач.
Таким образом, NP-полные задачи образуют в некотором смысле подмножество «типовых» задач в классе NP: если для какой-то из них найден «полиномиально быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».
Однако ни построить такой алгоритм для хотя бы одной из этих задач, ни доказать отсутствие такого алгоритма ученым пока не удается. Созданием новых подходов к разработке и анализу алгоритмов для NP-трудных задач и занимается коллектив этой уникальной лаборатории.

 

Ведущий учёный

img02 

ФИО:Фомин Федор Владимирович

 

Ученые степень и звание:
Кандидат физико-математических наук

Занимаемая должность:

Профессор Университета Бергена (Норвегия)

Области научных интересов:

Теоретическая информатика: анализ и дизайн алгоритмов, параметризованная сложность и алгоритмы для труднорешаемых задач.

Научные достижения:

Создатель теории биразмерных задач.
Автор метода Measure & Conque для анализа экспоненциальных алгоритмов. Также развивает субэкспоненциальные алгоритмы.
Создатель новых кернелизационных алгоритмов.
Автор (совместно с Д. Кратчем) первого и единственного на данный момент учебника по точным алгоритмам для NP-трудных задач*.

Научное признание: 

Член программных комитетов международных конференций, включая наиболее престижные конференции по алгоритмам SODA, ICALP, ESA.
Председатель программного комитета ведущих конференций по алгоритмам ICALP, SWAT и по параметризованной сложности IPEC.
Редактор журналов SIAM Journal on Discrete Mathematics, Algorithmica и Information and Computation.

1 Journal of the ACM F. V. Fomin, F. Grandoni, and D. Kratsch A Measure & Conquer Approach for the Analysis of Exact Algorithms 2009, 56 (5) article No. 25 2,733
2 Communications of the ACM F. V. Fomin and P. Kaski Exact exponential algorithms 2013, 56 (3) 2,564
3 SIAM Journal on Computing F. V. Fomin, D. Kratsch, I. Todinca, and Y. Villanger Exact algorithms for treewidth and minimum fill-in 2008, 38 (3) 1,318
4 SIAM Journal on Computing F. V. Fomin, P. A. Golovach, D. Lokshtanov, and S. Saurabh Intractability of Clique- width Parameterizations 2010, 39 (5) 1,318
5 Journal of Computer and System Sciences F. V. Fomin, S. Gaspers, S. Saurabh, and S. Thomasse A linear vertex kernel for maximum internal spanning tree 2013, 79 (1) 1,106
6 Journal of Computer and System Sciences F. Dorn, F. V. Fomin, and D. M. Thilikos Catalan structures and dynamic programming in Hminor- free graphs 2012, 78 (3) 1,106
7 Journal of Computer and System Sciences M. Fellows, F. V. Fomin, D. Lokshtanov, F. Rosamond, S. Saurabh, and Y. Villanger Local Search: Is brute-force avoidable? 2012, 78 (3) 1,106
8 Journal of Computer and System Sciences F. V. Fomin, D. Lokshtanov, V. Raman, B. V. R. Rao, and S. Saurabh Faster Algorithms for Finding and Counting Subgraphs 2012, 78 (3) 1,106
9 Journal of Combinatorial Theory Series B F. V. Fomin, P. A. Golovach, and D. M. Thilikos Contraction obstructions for treewidth 2011, 101 1,044
10 Combinatorica F. V. Fomin and Y. Villanger Treewidth computation and extremal combinatorics 2012, 32 (3) 0,903

Результаты исследований

Magnus Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov. A Better-than-3n Lower Bound for the Circuit Complexity of an Explicit Function. Proceedings of 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016). IEEE Computer Society, pp. 89–98, 2016.
Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov. Parameterized Complexity of Secluded Connectivity Problems. Theory of Computing Systems, 2016, pp 1–25
Ivan Bliznets, Marek Cygan, Paweł Komosa, Lukáš Mach, Michał Pilipczuk. Lower bounds for the parameterized complexity of minimum fill-in and other completion problems. SODA '16 Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, 2016, pp. 1132-1151
Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk , Yngve Villanger. Largest Chordal and Interval Subgraphs Faster than 2^n. Algorithmica, Vol. 76 Iss. 2, October 2016, pp. 569-594
Sergey I. Nikolenko, Kirill Kogan, Gábor Rétvári, Erika R. Bérczi-Kovács, Alexander Shalimov. How to represent IPv6 forwarding tables on IPv4 or MPLS dataplanes. 2016 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), 2016
Ivan Bliznets, Marek Cygan, Pawel Komosa, Michal Pilipczuk. Hardness of Approximation for H-Free Edge Modification Problems. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol. 60, 2016, pp. 3:1--3:17
Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov. On the Limits of Gate Elimination. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol. 58, 2016, pp 46:1--46:13
Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki. Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol. 58, 2016, pp 45:1–45:16
Dmitry Itsykson, Vsevolod Oparin, Mikhail Slabodkin, Dmitry Sokolov. Tight Lower Bounds on the Resolution Complexity of Perfect Matching Principles. Fundamenta Informaticae, vol. 145, no. 3, pp. 229-242, 2016
Kirill Kogan, Sergey Nikolenko, Patrick Eugster, Alexander Shalimov, and Ori Rottenstreich. FIB Efficiency in Distributed Platforms. In: The 24th IEEE International Conference on Network Protocols (ICNP 2016), 8-11 November 2016, Singapore
Kirill Kogana, Alejandro López-Ortizb, Sergey I. Nikolenkoc, Gabriel Scalosube, Michael Segale. Large profits or fast gains: A dilemma in maximizing throughput with applications to network processors. Journal of Network and Computer Applications, vol. 74, October 2016, pp 31–43
Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach. Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh. Parameterized complexity of superstring problems. Algorithmica (2016)
Pavel Chuprikov, Sergey I. Nikolenko, Kirill Kogan. On Demand Elastic Capacity Planning for Service Auto-scaling. IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications, 2016, pp. 1–9
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT. ACM Transactions on Algorithms (TALG), Vol. 12 Iss. 3, June 2016
Article No. 35
Petr A. Golovach, George B. Mertzios. Graph Editing to a Given Degree Sequence. Computer Science – Theory and Applications, Volume 9691 of the series Lecture Notes in Computer Science, 2016, pp 177-191
Rajesh Chitnis, Fedor V. Fomin, Petr A. Golovach. Parameterized complexity of the anchored k-core problem for directed graphs. Information and Computation, vol. 247, April 2016, pp 11–22
Kirill Kogan, Danushka Menikkumbura, Gustavo Petri, YoungTae Noh, Sergey Nikolenko, Patrick Eugster. BASEL (Buffer mAnagement SpEcification Language). ANCS '16 Proceedings of the 2016 Symposium on Architectures for Networking and Communications Systems, 2016, pp. 69-74
Alexander Golovnev, Alexander S. Kulikov. Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds. ITCS '16 Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016, pp. 405-411
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socała. Tight bounds for graph homomorphism and subgraph isomorphism. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '16), 2016, pp. 1643-1649
A.V. Pastor. On the Structure of C3-Critical Minimal 6-Connected Graphs. Journal of Mathematical Sciences, vol. 212, iss. 6, February 2016, pp 698–707
Sergey I. Nikolenko. SVD-LDA: Topic Modeling for Full-Text Recommender Systems. Proc. 14th Mexican International Conference on Artificial Intelligence ( MICAI 2015), Lecture Notes in Artificial Intelligence, vol. 9414, Springer, 2015, pp. 67–79.
Patrick Eugster, Alex Kesselman, Kirill Kogan, Sergey I. Nikolenko, Alexander V. Sirotkin. Essential Traffic Parameters for Shared Memory Switch Performance. 22nd International Colloquium on Structural Information and Communication Complexity ( SIROCCO 2015), Lecture Notes in Computer Science, vol. 9439, Springer, 2015, pp. 61–75
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov. Complexity of distributions and average-case hardness. 2015.
Magnus Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov. A better-than-3n lower bound for the circuit complexity of an explicit function.
Edward A. Hirsch, Dmitry Sokolov. On the probabilistic closure of the loose unambiguous hierarchy. Information Processing Letters. vol. 115. pp. 725 - 730. 2015.
Ivan Bliznets, Fedor V. Fomin, Michał Pilipczuk , Yngve Villanger: Largest Chordal and Interval Subgraphs Faster than 2^n. Algorithmica Volume 73 Number 3 November 2015
pp 1-26
Tatjana V. Abramovskaya, Fedor V. Fomin, Petr A. Golovach, Michał Pilipczuk: How to hunt an invisible rabbit on a graph. European Journal of Combinatorics, 52 Part A (2016), pp. 12–26
Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov. Resolution Complexity of Perfect Matching Principles for Sparse Graphs. Computer Science -- Theory and Applications. Lecture Notes in Computer Science. vol. 9139. pp. 219-230, 2015.
Alexadner Knop. Circuit Lower Bounds for Average-Case MA. Computer Science -- Theory and Applications. Lecture Notes in Computer Science Volume 9139, 2015, pp 283-295
Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Lower Bounds for the Graph Homomorphism Problem. Proceedings of 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015). Lecture Notes in Computer Science 9134, Springer, pp. 481-493. 2015.
Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh. Parameterized Complexity of Superstring Problems. Proceeidings of the 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015). Lecture Notes in Computer Science, vol. 9133, pp. 89-99, Springer, 2015
Petr A. Golovach, Editing to a Graph of Given Degrees. Theor. Comp. Sci., 591, pp. 72-84, 2015
Pavel Chuprikov, Sergey Nikolenko, Kirill Kogan: Priority queueing with multiple packet characteristics. 2015 IEEE Conference on Computer Communications (INFOCOM 2015), pp. 1418-1426, 2015
Pablo Saez, Xavier Vidaux, Maxim Vsemirnov. Optimal bounds for Büchi's problem in modular arithmetic. Journal of Number Theory, Volume 149, pp. 368–403, 2015.
Fedor Fomin, Petr Golovach, Nikolay Karpov, Alexander Kulikov. Parameterized Complexity of Secluded Connectivity Problems. Proceedings of the 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015), LIPIcs, Vol. 45, pp. 408-419, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015.
Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk and Michał Pilipczuk: A Subexponential Parameterized Algorithm for Proper Interval Completion. SIAM Journal on Discrete Mathematics 2015, Vol. 29, No. 4, pp. 1961-1987
Ivan Bliznets, Marek Cygan, Pawel Komosa, Lukas Mach. Kernelization lower bound for Permutation Pattern Matching. To appear in Information Processing Letters, 2015.
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov. Heuristic time hierarchies via hierarchies for sampling distributions. ECCC 2014 report.
Petr A. Golovach. Editing to a Graph of Given Degrees. Proceedings of 9th International Symposium on Parameterized and Exact Computation (IPEC 2014), Lecture Notes in Computer Science 8894, Springer, pp. 196–207, 2014.
Alexander Knop. Circuit Lower Bounds for Average MA. ECCC 2014 report.
Dmitry Itsykson, Anna Malova, Vsevolod Oparin, Dmitry Sokolov. Tree-like resolution complexity of two planar problems. CoRR abs/1412.1124
Evgeny Demenkov, Alexander S. Kulikov, Olga Melanich, Ivan Mihajlin. New Lower Bounds on Circuit Size of Multi-output Functions. Theory of Computing Systems, 2014.
Sergey I. Nikolenko, Kirill Kogan. Single and Multiple Buffer Processing. Encyclopedia of Algorithms, pp 1-9, 2014.
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Families with infants: speeding up algorithms for NP-hard problems using FFT. CoRR abs/1410.2209
Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michał Pilipczuk. A Subexponential Parameterized Algorithm for Proper Interval Completion. Proceedings of 22th Annual European Symposium (ESA 2014), Lecture Notes in Computer Science 8737, Springer, pp. 173–184, 2014.
Petr A. Golovach. Editing to a Connected Graph of Given Degrees. Proceedings of 39th Mathematical Foundations of Computer Science (MFCS 2014), Lecture Notes in Computer Science 8635, Springer, pp. 324–335, part 2, 2014.
Dmitry Itsykson, Dmitry Sokolov. Lower Bounds for Splittings by Linear Combinations. Proceedings of 39th Mathematical Foundations of Computer Science (MFCS 2014), Lecture Notes in Computer Science 8635, Springer, pp. 372–383, part 2, 2014.
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Solving SCS for Bounded Length Strings in Fewer than 2^n Steps. Information Processing Letters, Volume 114, Issue 8, pp 421–425, 2014.
Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov. Resolution complexity of perfect mathcing principles for sparse graphs. ECCC 2014 report.
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Families with Infants: A General Approach to Solve Hard Partition Problems. Proceedings of 41st International Colloquium Automata, Languages, and Programming (ICALP 2014), Lecture Notes in Computer Science 8572, Springer, pp. 551–562, 2014.
Fedor V. Fomin, Petr A. Golovach. Long Circuits and Large Euler Subgraphs. SIAM Journal on Discrete Mathematics, 28(2), pp. 878-892, 2014.
Maxim Vsemirnov. On a conjecture of Guo and Krattenthaler. International Journal of Number Theory, Volume 10, Issue 06, 2014.
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Families with infants: a general approach to solve hard partition problems. CoRR abs/1311.2456.
Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin. Solving 3-Superstring in 3^{n/3} Time. Proceedings of 38th International Symposium on Mathematical Foundations of Computer Science (MFCS 2013), Lecture Notes in Computer Science 8087, Springer, pp. 480–491, 2013.
Back to top