Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Optimality in parameterized complexity

2013/11/D/ST6/03073

Keywords:

parameterized complexity fixed-parameter tractability optimality program Exponential Time Hypothesis

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory

Panel:

ST6 - Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems

Host institution :

Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

woj. mazowieckie

Other projects carried out by the institution 

Principal investigator (from the host institution):

dr Michał Pilipczuk 

Number of co-investigators in the project: 2

Call: SONATA 6 - announced on 2013-09-16

Amount awarded: 386 320 PLN

Project start date (Y-m-d): 2014-10-01

Project end date (Y-m-d): 2017-09-30

Project duration:: 36 months (the same as in the proposal)

Project status: Project settled

Equipment purchased [PL]

  1. Laptop dla drugiego wykonawcy (5 000 PLN)
  2. Laptop dla kierownika projektu (5 000 PLN)
  3. Komputer stacjonarny dla kierownika projektu (4 000 PLN)

Information in the final report

  • Publication in academic press/journals (17)
  • Articles in post-conference publications (20)
  1. Below all subsets for Minimal Connected Dominating Set
    Authors:
    Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh
    Academic press:
    SIAM Journal on Discrete Mathematics (SIDMA) (rok: 2018, tom: 32(3), strony: 2332-2345), Wydawca: Society for Industrial and Applied Mathematics (SIAM)
    Status:
    Published
    DOI:
    10.1137/17M1138753 - link to the publication
  2. Edge Bipartization faster than 2^k
    Authors:
    Marcin Pilipczuk, Michał Pilipczuk, Marcin Wrochna
    Academic press:
    Algorithmica (rok: 2019, tom: 81(3), strony: 917-966), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-017-0319-z - link to the publication
  3. Exploring the complexity of layout parameters in tournaments and semi-complete digraphs
    Authors:
    Florian Barbero, Christophe Paul, Michał Pilipczuk
    Academic press:
    ACM Transactions on Algorithms (TALG) (rok: 2018, tom: 14(3), strony: 38:1-38:31), Wydawca: ACM
    Status:
    Published
    DOI:
    10.1145/3196276 - link to the publication
  4. Polynomial kernelization for removing induced claws and diamonds
    Authors:
    Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna
    Academic press:
    Theory of Computing Systems (rok: 2017, tom: 60(4), strony: 615-636), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00224-016-9689-x - link to the publication
  5. Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna
    Authors:
    Linear kernels for edge deletion problems to immersion-closed graph classes
    Academic press:
    wersja czasopismowa pracy z ICALP 2017, wysłana do recenzji do czasopisma SIAM Journal on Discrete Mathematics (), Wydawca: -
    Status:
    Submitted
    DOI:
    brak - link to the publication
  6. Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs
    Authors:
    Michał Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese
    Academic press:
    wersja czasopismowa pracy z ESA 2018, wysłana do recenzji do czasopisma Algorithmica , Wydawca: -
    Status:
    Submitted
    DOI:
    brak - link to the publication
  7. On space efficiency of algorithms working on structural decompositions of graphs
    Authors:
    Michał Pilipczuk, Marcin Wrochna
    Academic press:
    ACM Transactions on Computation Theory (TOCT) (rok: 2018, tom: 9(4), strony: 18:1-18:36), Wydawca: ACM
    Status:
    Published
    DOI:
    10.1145/3154856 - link to the publication
  8. Turing kernelization for finding long paths in graph classes excluding a topological minor
    Authors:
    Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna
    Academic press:
    Algorithmica (rok: 2019, tom: Online First, strony: 11689), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-019-00614-4 - link to the publication
  9. Cutwidth: obstructions and algorithmic aspects
    Authors:
    Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna
    Academic press:
    Algorithmica (rok: 2019, tom: 81(2), strony: 557-588), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-018-0424-7 - link to the publication
  10. Hardness of approximation for Strip Packing
    Authors:
    Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, Michał Pilipczuk
    Academic press:
    ACM Transactions on Computation Theory (TOCT) (rok: 2017, tom: 9(3), strony: 14:1--14:7), Wydawca: ACM
    Status:
    Published
    DOI:
    10.1145/3092026 - link to the publication
  11. A polynomial kernel for Trivially Perfect Editing
    Authors:
    Pål Grønås Drange, Michał Pilipczuk
    Academic press:
    Algorithmica (rok: 2018, tom: 80(12), strony: 3481-3524), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-017-0401-6 - link to the publication
  12. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
    Authors:
    Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh, Marcin Wrochna
    Academic press:
    ACM Transactions on Algorithms (TALG) (rok: 2018, tom: 14(3), strony: 34:1--34:45), Wydawca: ACM
    Status:
    Published
    DOI:
    10.1145/3186898 - link to the publication
  13. Tight lower bounds for the complexity of Multicoloring
    Authors:
    Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała, Marcin Wrochna
    Academic press:
    ACM Transactions on Computation Theory (TOCT) (rok: 2019, tom: 11(3), strony: 13:1-13:19), Wydawca: ACM
    Status:
    Published
    DOI:
    10.1145/3313906 - link to the publication
  14. Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering
    Authors:
    Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
    Academic press:
    wersja konferencyjna pracy z FOCS 2016, złożona do recenzji w czasopiśmie SIAM Journal on Computing , Wydawca: -
    Status:
    Submitted
    DOI:
    brak - link to the publication
  15. Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems
    Authors:
    Ivan Bliznets, Marek Cygan, Paweł Komosa, Lukáš Mach, Michał Pilipczuk
    Academic press:
    wersja czasopismowa pracy opublikowanej na SODA 2016, złożona do recenzji w czasopiśmie ACM Transactions on Algorithms , Wydawca: -
    Status:
    Submitted
    DOI:
    brak - link to the publication
  16. Hardness of approximation for H-free edge modification problems
    Authors:
    Ivan Bliznets, Marek Cygan, Paweł Komosa, Michał Pilipczuk
    Academic press:
    ACM Transactions on Computation Theory (TOCT) (rok: 2018, tom: 10(2), strony: 9:1-9:32), Wydawca: ACM
    Status:
    Published
    DOI:
    10.1145/3196834 - link to the publication
  17. Strong immersion is a well-quasi-ordering for semi-complete digraphs
    Authors:
    Florian Barbero, Christophe Paul, Michał Pilipczuk
    Academic press:
    Journal of Graph Theory (rok: 2019, tom: 90(4), strony: 484-496), Wydawca: Wiley
    Status:
    Published
    DOI:
    10.1002/jgt.22408 - link to the publication
  1. Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs
    Authors:
    Michał Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese
    Conference:
    26th Annual European Symposium on Algorithms, ESA 2018 (rok: 2018, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 20-22.08.2018
    Status:
    Published
    DOI:
    link to the publication
  2. Tight lower bounds for the complexity of multicoloring
    Authors:
    Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała, Marcin Wrochna
    Conference:
    25th Annual European Symposium on Algorithms, ESA 2017 (rok: 2017, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 4-6.09.2017
    Status:
    Published
    DOI:
    link to the publication
  3. Fast algorithms for parameterized problems with relaxed disjointness constraint
    Authors:
    Ariel Gabizon, Daniel Lokshtanov, Michał Pilipczuk
    Conference:
    23rd Annual European Symposium on Algorithms, ESA 2015 (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 14-16.09.2015
    Status:
    Published
  4. Lower bounds for approximation schemes for Closest String
    Authors:
    Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
    Conference:
    15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016 (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 22-24.06.2016
    Status:
    Published
    DOI:
    link to the publication
  5. On Directed Feedback Vertex Set parameterized by treewidth
    Authors:
    Marthe Bonamy, Łukasz Kowalik, Jesper Nederlof, Michał Pilipczuk, Arkadiusz Socała, Marcin Wrochna
    Conference:
    44th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2018 (rok: 2018, ), Wydawca: Springer
    Data:
    konferencja 27-29.06.2018
    Status:
    Published
    DOI:
    link to the publication
  6. On space efficiency of algorithms working on structural decompositions of graphs
    Authors:
    Michał Pilipczuk, Marcin Wrochna
    Conference:
    33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016 (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 17-20.02.2016
    Status:
    Published
    DOI:
    link to the publication
  7. Turing kernelization for finding long paths in graph classes excluding a topological minor
    Authors:
    Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna
    Conference:
    12th International Symposium on Parameterized and Exact Computation, IPEC 2017 (rok: 2017, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 6-8.09.2017
    Status:
    Published
    DOI:
    link to the publication
  8. Approximation and parameterized algorithms for geometric independent set with shrinking
    Authors:
    Michał Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese
    Conference:
    42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017 (rok: 2017, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 21-25.08.2017
    Status:
    Published
    DOI:
    link to the publication
  9. Edge Bipartization faster than 2^k
    Authors:
    Marcin Pilipczuk, Michał Pilipczuk, Marcin Wrochna
    Conference:
    11th International Symposium on Parameterized and Exact Computation, IPEC 2016 (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 24-26.08.2016
    Status:
    Published
    DOI:
    link to the publication
  10. Exploring the complexity of layout parameters in tournaments and semi-complete digraphs
    Authors:
    Florian Barbero, Christophe Paul, Michał Pilipczuk
    Conference:
    44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 (rok: 2017, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 10-14.07.2017
    Status:
    Published
    DOI:
    link to the publication
  11. Hardness of approximation for H-free edge modification problems
    Authors:
    Ivan Bliznets, Marek Cygan, Paweł Komosa, Michał Pilipczuk
    Conference:
    19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 7-9.09.2016
    Status:
    Published
    DOI:
    link to the publication
  12. Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems
    Authors:
    Ivan Bliznets, Marek Cygan, Paweł Komosa, Lukáš Mach, Michał Pilipczuk
    Conference:
    27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 (rok: 2016, ), Wydawca: SIAM
    Data:
    konferencja 10-12.01.2016
    Status:
    Published
    DOI:
    link to the publication
  13. A polynomial kernel for Trivially Perfect Editing
    Authors:
    Pål Grønås Drange, Michał Pilipczuk
    Conference:
    23rd Annual European Symposium on Algorithms, ESA 2015 (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 14-16.09.2015
    Status:
    Published
  14. Cutwidth: obstructions and algorithmic aspects
    Authors:
    Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna
    Conference:
    11th International Symposium on Parameterized and Exact Computation, IPEC 2016 (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 24-26.08.2016
    Status:
    Published
    DOI:
    link to the publication
  15. Linear kernels for edge deletion problems to immersion-closed graph classes
    Authors:
    Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna
    Conference:
    44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 (rok: 2017, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja 10-14.07.2017
    Status:
    Published
    DOI:
    link to the publication
  16. Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams
    Authors:
    Dániel Marx, Michał Pilipczuk
    Conference:
    23rd Annual European Symposium on Algorithms, ESA 2015 (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 14-16.09.2015
    Status:
    Published
  17. Polynomial kernelization for removing induced claws and diamonds
    Authors:
    Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna
    Conference:
    41st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2015 (rok: 2016, ), Wydawca: Springer
    Data:
    konferencja 17-19.06.2015
    Status:
    Published
  18. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
    Authors:
    Fedor V. Fomin, Daniel Lokshtanov, Michał Pilipczuk, Saket Saurabh, Marcin Wrochna
    Conference:
    28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 (rok: 2017, ), Wydawca: SIAM
    Data:
    konferencja 16-19.01.2017
    Status:
    Published
    DOI:
    link to the publication
  19. On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs
    Authors:
    Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk
    Conference:
    59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 (rok: 2018, ), Wydawca: IEEE Computer Society
    Data:
    konferencja 7-9.10.2018
    Status:
    Published
    DOI:
    link to the publication
  20. Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering
    Authors:
    Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
    Conference:
    IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016 (rok: 2016, ), Wydawca: IEEE Computer Society
    Data:
    konferencja 9-11.10.2016
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy