Marcin Pilipczuk

From MaRDI portal
(Redirected from Person:255284)



List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

PublicationDate of PublicationType
Parameterized complexity of MinCSP over the point algebra2026-05-26Paper
Cluster editing parameterized above modification-disjoint P₃-Packings2026-04-21Paper
Flow-augmentation. I: Directed graphs
Journal of the ACM
2026-02-24Paper
Max weight independent set in sparse graphs with no long claws2025-11-10Paper
Parameterized complexity classification for interval constraints2025-09-24Paper
Polynomial-time approximation schemes for facility location on planar graphs
SIAM Journal on Computing
2025-09-16Paper
Flow-augmentation. III: Complexity dichotomy for Boolean CSPS parameterized by the number of unsatisfied constraints
SIAM Journal on Computing
2025-09-16Paper
Planar and minor-free metrics embed into metrics of polylogarithmic treewidth with expected multiplicative distortion arbitrarily close to 12025-08-15Paper
A polynomial-time approximation scheme for facility location on planar graphs2025-08-12Paper
On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs2025-08-12Paper
Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering2025-08-06Paper
Network sparsification for Steiner problems on planar and bounded-genus graphs2025-08-05Paper
Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth2025-08-05Paper
On the complexity of problems on tree-structured graphs2025-06-23Paper
Packing directed cycles quarter- and half-integrally
Combinatorica
2025-06-19Paper
Taming graphs with no large creatures and skinny ladders2025-06-19Paper
The influence of dimensions on the complexity of computing decision trees
Artificial Intelligence
2025-05-30Paper
The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable2025-05-20Paper
A polynomial bound on the number of minimal separators and potential maximal cliques in P₆-free graphs of bounded clique number
Discrete Mathematics and Theoretical Computer Science. DMTCS
2025-05-07Paper
Designing FPT algorithms for cut problems using randomized contractions2025-05-05Paper
Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P₄ (extended abstract)2025-04-08Paper
Max weight independent set in graphs with no long claws: an analog of the Gyárfás' path argument
ACM Transactions on Computation Theory
2025-02-25Paper
Flow-augmentation. II: Undirected graphs
ACM Transactions on Algorithms
2025-02-21Paper
Cluster editing parameterized above modification-disjoint P₃-packings
ACM Transactions on Algorithms
2025-02-21Paper
Taming graphs with no large creatures and skinny ladders
SIAM Journal on Discrete Mathematics
2024-12-18Paper
Sparse induced subgraphs in P₆-free graphs2024-11-28Paper
Max weight independent set in graphs with no long claws: an analog of the Gyárfás' path argument2024-06-24Paper
Induced subgraphs of bounded treewidth and the container method
SIAM Journal on Computing
2024-06-05Paper
Simple and tight complexity lower bounds for solving Rabin games2024-05-29Paper
Conditional lower bounds for sparse parameterized 2-CSP: a streamlined proof2024-05-29Paper
A tight quasi-polynomial bound for \textsc{Global Label Min-Cut}2024-05-14Paper
Flow-augmentation. III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints2024-05-14Paper
Fixed-parameter tractability of \textsc{Directed Multicut} with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation2024-05-14Paper
Quasi-polynomial-time algorithm for independent set in P_t-free graphs via shrinking the space of induced paths2024-05-14Paper
Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs
SIAM Journal on Computing
2024-02-28Paper
Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P₄
The Electronic Journal of Combinatorics
2024-02-23Paper
scientific article; zbMATH DE number 7803599 (Why is no real title available?)
(available as arXiv preprint)
2024-02-12Paper
Hardness of metric dimension in graphs of constant treewidth2024-02-12Paper
scientific article; zbMATH DE number 7788454 (Why is no real title available?)
(available as arXiv preprint)
2024-01-15Paper
scientific article; zbMATH DE number 7788388 (Why is no real title available?)
(available as arXiv preprint)
2024-01-15Paper
scientific article; zbMATH DE number 7788441 (Why is no real title available?)
(available as arXiv preprint)
2024-01-15Paper
Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
2023-12-08Paper
Finding large induced sparse subgraphs in <i> c <sub>&gt;t</sub> </i> -free graphs in quasipolynomial time
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
2023-11-14Paper
scientific article; zbMATH DE number 7765417 (Why is no real title available?)2023-11-14Paper
The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth.2023-11-13Paper
Polynomial-time Algorithm for Maximum Weight Independent Set on <i>P</i> <sub>6</sub> -free Graphs
ACM Transactions on Algorithms
2023-10-31Paper
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
ACM Transactions on Algorithms
2023-10-31Paper
A polynomial bound on the number of minimal separators and potential maximal cliques in P₆-free graphs of bounded clique number2023-10-17Paper
(Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth
Journal of Graph Theory
2023-10-04Paper
Sparse induced subgraphs in P₆-free graphs2023-07-14Paper
Constant Congestion Brambles
Discrete Mathematics & Theoretical Computer Science
2023-05-30Paper
Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
Graph-Theoretic Concepts in Computer Science
2023-05-05Paper
The complexity of routing problems in forbidden-transition graphs and edge-colored graphs
Algorithmica
2023-04-28Paper
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
SIAM Journal on Computing
2023-04-04Paper
Tight bound on treedepth in terms of pathwidth and longest path2023-02-06Paper
Hardness of metric dimension in graphs of constant treewidth
Algorithmica
2022-10-27Paper
Highly unbreakable graph with a fixed excluded minor are almost rigid2022-10-26Paper
Surprising Applications of Treewidth Bounds for Planar Graphs
Treewidth, Kernels, and Algorithms
2022-10-19Paper
A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs2022-07-18Paper
Efficient approximation schemes for uniform-cost clustering problems in planar graphs
(available as arXiv preprint)
2022-05-11Paper
scientific article; zbMATH DE number 7525509 (Why is no real title available?)
(available as arXiv preprint)
2022-05-11Paper
scientific article; zbMATH DE number 7525471 (Why is no real title available?)2022-05-11Paper
Taming graphs with no large creatures and skinny ladders2022-05-02Paper
A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs
SIAM Journal on Computing
2022-04-20Paper
Constant congestion brambles in directed graphs
SIAM Journal on Discrete Mathematics
2022-04-20Paper
Max Weight Independent Set in graphs with no long claws: An analog of the Gy\'arf\'as' path argument2022-03-09Paper
Randomized Contractions Meet Lean Decompositions
ACM Transactions on Algorithms
2022-02-08Paper
A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
SIAM Journal on Discrete Mathematics
2021-11-04Paper
Jones' conjecture in subcubic graphs
The Electronic Journal of Combinatorics
2021-10-26Paper
Multi-budgeted directed cuts2021-08-04Paper
An improved FPT algorithm for independent feedback vertex set
Theory of Computing Systems
2021-06-11Paper
Improved bounds for the excluded-minor approximation of treedepth
SIAM Journal on Discrete Mathematics
2021-05-28Paper
Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
ACM Journal of Experimental Algorithmics
2021-04-21Paper
Finding Hamiltonian cycle in graphs of bounded treewidth. Experimental evaluation
ACM Journal of Experimental Algorithmics
2021-04-21Paper
On the maximum weight independent set problem in graphs without induced cycles of length at least five
SIAM Journal on Discrete Mathematics
2021-03-12Paper
Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs
The Electronic Journal of Combinatorics
2021-02-16Paper
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in <i>H</i>-free graphs
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms
2021-02-02Paper
Polynomial treedepth bounds in linear colorings
Algorithmica
2021-02-01Paper
Two lower bounds for p-centered colorings
(available as arXiv preprint)
2021-01-05Paper
Two lower bounds for p-centered colorings2021-01-05Paper
A double exponential lower bound for the distinct vectors problem
(available as arXiv preprint)
2021-01-05Paper
A double exponential lower bound for the distinct vectors problem2021-01-05Paper
Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
(available as arXiv preprint)
2020-12-16Paper
scientific article; zbMATH DE number 7286685 (Why is no real title available?)
(available as arXiv preprint)
2020-12-16Paper
Finding Hamiltonian cycle in graphs of bounded tree-width: experimental evaluation
(available as arXiv preprint)
2020-12-16Paper
Multi-budgeted directed cuts
Algorithmica
2020-08-12Paper
Subexponential parameterized algorithms for graphs of polynomial growth
(available as arXiv preprint)
2020-05-27Paper
Turing kernelization for finding long paths in graphs excluding a topological minor2020-05-27Paper
An exponential lower bound for cut sparsifiers in planar graphs
(available as arXiv preprint)
2020-05-27Paper
Hardness of approximation for strip packing
ACM Transactions on Computation Theory
2019-12-06Paper
Hardness of approximation for strip packing
ACM Transactions on Computation Theory
2019-12-06Paper
Directed multicut is W[1]-hard, even for four terminal pairs
ACM Transactions on Computation Theory
2019-12-06Paper
Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
2019-10-15Paper
Turing kernelization for finding long paths in graph classes excluding a topological minor
Algorithmica
2019-09-10Paper
An exponential lower bound for cut sparsifiers in planar graphs
Algorithmica
2019-09-10Paper
Deleting vertices to graphs of bounded genus
Algorithmica
2019-08-20Paper
Packing Directed Cycles Quarter- and Half-Integrally
(available as arXiv preprint)
2019-07-04Paper
Caterpillars in Erdős-Hajnal
Journal of Combinatorial Theory. Series B
2019-06-17Paper
Known algorithms for edge clique cover are probably optimal
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
2019-05-15Paper
Minimum bisection is fixed-parameter tractable
SIAM Journal on Computing
2019-05-07Paper
Network sparsification for Steiner problems on planar and bounded-genus graphs
ACM Transactions on Algorithms
2019-03-28Paper
Network sparsification for Steiner problems on planar and bounded-genus graphs
ACM Transactions on Algorithms
2019-03-28Paper
Edge bipartization faster than \(2^k\)
Algorithmica
2019-03-11Paper
Planar Digraphs
Springer Monographs in Mathematics
2019-03-04Paper
Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
Algorithmica
2019-02-14Paper
An improved FPT algorithm for independent feedback vertex set
Graph-Theoretic Concepts in Computer Science
2018-11-22Paper
Subexponential parameterized algorithm for {\textsc{Interval Completion}}
ACM Transactions on Algorithms
2018-11-13Paper
Independence and Efficient Domination on <i>P</i> <sub>6</sub> -free Graphs
ACM Transactions on Algorithms
2018-11-12Paper
Approximation and kernelization for chordal vertex deletion
SIAM Journal on Discrete Mathematics
2018-09-12Paper
Excluding hooks and their complements
The Electronic Journal of Combinatorics
2018-09-07Paper
Excluding hooks and their complements
The Electronic Journal of Combinatorics
2018-09-07Paper
Constant congestion routing of symmetric demands in planar directed graphs
SIAM Journal on Discrete Mathematics
2018-08-22Paper
Independence and efficient domination on \(P_6\)-free graphs
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
2018-07-16Paper
Subexponential parameterized algorithm for interval completion
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
2018-07-16Paper
Approximation and kernelization for chordal vertex deletion
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
2018-07-16Paper
Directed multicut is W[1]-hard, even for four terminal pairs
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
2018-07-16Paper
Edge Bipartization Faster Than 2ᵏ
(available as arXiv preprint)
2018-04-10Paper
scientific article; zbMATH DE number 6820196 (Why is no real title available?)2017-12-19Paper
The Erd\H{o}s-Hajnal conjecture for caterpillars and their complements2017-10-24Paper
Lower bounds for approximation schemes for Closest String
(available as arXiv preprint)
2017-10-17Paper
On routing disjoint paths in bounded treewidth graphs
(available as arXiv preprint)
2017-10-17Paper
The stubborn problem is stubborn no more: a polynomial algorithm for 3-compatible colouring and the stubborn List partition problem2017-09-29Paper
Hitting forbidden subgraphs in graphs of bounded treewidth
Information and Computation
2017-09-28Paper
Hitting forbidden subgraphs in graphs of bounded treewidth
Information and Computation
2017-09-28Paper
A tight lower bound for vertex planarization on graphs of bounded treewidth
Discrete Applied Mathematics
2017-09-12Paper
Polynomial kernelization for removing induced claws and diamonds
Theory of Computing Systems
2017-08-15Paper
Scheduling partially ordered jobs faster than \(2^n\)
Algorithmica
2017-05-17Paper
Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
SIAM Journal on Computing
2017-03-10Paper
Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
SIAM Journal on Computing
2017-03-10Paper
Subexponential-time parameterized algorithm for Steiner tree on planar graphs2017-01-30Paper
Tight bounds for parameterized complexity of Cluster Editing2017-01-30Paper
Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
ACM Transactions on Computation Theory
2016-10-24Paper
Polynomial kernelization for removing induced claws and diamonds
Graph-Theoretic Concepts in Computer Science
2016-10-21Paper
Designing FPT algorithms for cut problems using randomized contractions
SIAM Journal on Computing
2016-08-16Paper
On group feedback vertex set parameterized by the size of the cutset
Algorithmica
2016-03-29Paper
A fast branching algorithm for cluster vertex deletion
Theory of Computing Systems
2016-03-09Paper
Known algorithms for edge clique cover are probably optimal
SIAM Journal on Computing
2016-01-20Paper
Fixed-parameter tractability of multicut in directed acyclic graphs
SIAM Journal on Discrete Mathematics
2015-11-27Paper
A Subexponential Parameterized Algorithm for Proper Interval Completion
SIAM Journal on Discrete Mathematics
2015-10-30Paper
On multiway cut parameterized above lower bounds
ACM Transactions on Computation Theory
2015-09-24Paper
Clique Cover and Graph Separation
ACM Transactions on Computation Theory
2015-09-03Paper
The Power of Dynamic Distance Oracles
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing
2015-08-21Paper
Parameterized algorithms2015-08-17Paper
Minimum bisection is fixed parameter tractable
Proceedings of the forty-sixth annual ACM symposium on Theory of computing
2015-06-26Paper
Minimum bisection is fixed parameter tractable
Proceedings of the forty-sixth annual ACM symposium on Theory of computing
2015-06-26Paper
Faster exponential-time algorithms in graphs of bounded average degree
Information and Computation
2015-06-09Paper
Sitting closer to friends than enemies, revisited
Theory of Computing Systems
2015-05-29Paper
Sitting closer to friends than enemies, revisited
Theory of Computing Systems
2015-05-29Paper
Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
Algorithmica
2015-01-19Paper
On cutwidth parameterized by vertex cover
Algorithmica
2014-12-02Paper
Hitting forbidden subgraphs in graphs of bounded treewidth
Mathematical Foundations of Computer Science 2014
2014-10-14Paper
A subexponential parameterized algorithm for proper interval completion
Algorithms - ESA 2014
2014-10-08Paper
Even faster exact bandwidth
ACM Transactions on Algorithms
2014-09-09Paper
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
2014-07-30Paper
A fast branching algorithm for cluster vertex deletion
Computer Science - Theory and Applications
2014-06-24Paper
Faster deterministic \textsc{Feedback Vertex Set}
Information Processing Letters
2014-06-23Paper
Tight bounds for parameterized complexity of cluster editing with a small number of clusters
Journal of Computer and System Sciences
2014-06-10Paper
On the hardness of losing width
Theory of Computing Systems
2014-03-25Paper
Parameterized complexity of Eulerian deletion problems
Algorithmica
2014-03-25Paper
A bound on the number of perfect matchings in Klee-graphs2014-02-14Paper
Clique cover and graph separation: new incompressibility results
Automata, Languages, and Programming
2013-08-12Paper
Fixed-parameter tractability of multicut in directed acyclic graphs
Lecture Notes in Computer Science
2013-08-12Paper
Faster exponential-time algorithms in graphs of bounded average degree
Automata, Languages, and Programming
2013-08-06Paper
Subset feedback vertex set is fixed-parameter tractable
SIAM Journal on Discrete Mathematics
2013-06-27Paper
Towards optimal kernel for connected vertex cover in planar graphs
Discrete Applied Mathematics
2013-04-25Paper
The planar directed k-Vertex-Disjoint Paths problem is fixed-parameter tractable2013-04-15Paper
Capacitated domination faster than O(2ⁿ)
Information Processing Letters
2013-04-04Paper
\textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
Information Processing Letters
2013-03-21Paper
Finding a maximum induced degenerate subgraph faster than \(2^{n}\)
Parameterized and Exact Computation
2013-01-07Paper
A polynomial algorithm for 3-compatible coloring and the stubborn list partition problem (the stubborn problem is stubborn no more)
SIAM Journal on Computing
2012-11-29Paper
An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
Algorithmica
2012-11-21Paper
On group feedback vertex set parameterized by the size of the cutset
Lecture Notes in Computer Science
2012-11-06Paper
Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
Discrete Applied Mathematics
2012-10-26Paper
Some results on Vizing's conjecture and related problems
Discrete Applied Mathematics
2012-10-19Paper
Sitting closer to friends than enemies, revisited
Mathematical Foundations of Computer Science 2012
2012-09-25Paper
A path-decomposition theorem with applications to pricing and covering on trees
Algorithms – ESA 2012
2012-09-25Paper
Approximation algorithms for union and intersection covering problems2012-08-31Paper
Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
Algorithm Theory – SWAT 2012
2012-08-14Paper
Solving the 2-disjoint connected subgraphs problem faster than \(2^{n }\)
LATIN 2012: Theoretical Informatics
2012-06-29Paper
On cutwidth parameterized by vertex cover
Parameterized and Exact Computation
2012-06-15Paper
On the hardness of losing width
Parameterized and Exact Computation
2012-06-15Paper
On multiway cut parameterized above lower bounds
Lecture Notes in Computer Science
2012-06-15Paper
Bandwidth and distortion revisited
Discrete Applied Mathematics
2012-05-04Paper
Parameterized complexity of Eulerian deletion problems
Graph-Theoretic Concepts in Computer Science
2011-12-16Paper
Dominating set is fixed parameter tractable in claw-free graphs
Theoretical Computer Science
2011-12-07Paper
Scheduling partially ordered jobs faster than \(2^{n }\)
Algorithms – ESA 2011
2011-09-16Paper
Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
Journal of Discrete Algorithms
2011-08-23Paper
Subset feedback vertex set is fixed-parameter tractable
Lecture Notes in Computer Science
2011-07-06Paper
On the Zagreb index inequality of graphs with prescribed vertex degrees
Discrete Applied Mathematics
2011-05-17Paper
Characterization of compact subsets of curves with -continuous derivatives
Fundamenta Mathematicae
2011-01-14Paper
An improved FPT algorithm and quadratic kernel for pathwidth one vertex deletion
Parameterized and Exact Computation
2010-12-07Paper
Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
Graph Theoretic Concepts in Computer Science
2010-11-16Paper
Exact and approximate bandwidth
Theoretical Computer Science
2010-10-11Paper
Fast approximation in subspaces by doubling metric decomposition
Algorithms – ESA 2010
2010-09-06Paper
Capacitated domination faster than \(O(2^{n })\)
Lecture Notes in Computer Science
2010-06-22Paper
Irredundant Set Faster Than O(2 n )
Lecture Notes in Computer Science
2010-05-28Paper
Exact and Approximate Bandwidth
Automata, Languages and Programming
2009-07-14Paper
Faster Exact Bandwidth
Graph-Theoretic Concepts in Computer Science
2009-01-20Paper
A few new facts about the EKG sequence2008-11-21Paper
A few new facts about the EKG sequence2008-11-21Paper
The negative association property for the absolute values of random variables equidistributed on a generalized Orlicz ball
Positivity
2008-09-02Paper


Research outcomes over time


This page was built for person: Marcin Pilipczuk