19 citations · 218 across the 100 of their papers we have counts for
10 papers · 1 filter
Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
Karthik C. S., Dániel Marx, Marcin Pilipczuk +1
Assuming the Exponential Time Hypothesis (ETH), a result of Marx (ToC'10) implies that there is no time algorithm that can solve 2-CSPs with constra…
Simple and tight complexity lower bounds for solving Rabin games
Antonio Casares, Marcin Pilipczuk, Michał Pilipczuk +2
We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time , where $k…
A polynomial bound on the number of minimal separators and potential maximal cliques in -free graphs of bounded clique number
Marcin Pilipczuk, Paweł Rzążewski
In this note we show a polynomial bound on the number of minimal separators and potential maximal cliques in -free graphs of bounded clique number.
Parameterized Complexity of MinCSP over the Point Algebra
George Osipov, Marcin Pilipczuk, Magnus Wahlström
The input in the Minimum-Cost Constraint Satisfaction Problem (MinCSP) over the Point Algebra contains a set of variables, a collection of constraints of the form , ,…
Max Weight Independent Set in sparse graphs with no long claws
Tara Abrishami, Maria Chudnovsky, Cemil Dibek +2
We revisit the recent polynomial-time algorithm for the MAX WEIGHT INDEPENDENT SET (MWIS) problem in bounded-degree graphs that do not contain a fixed graph whose every component i…
Sparse induced subgraphs in P_6-free graphs
Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk +2
We prove that a number of computational problems that ask for the largest sparse induced subgraph satisfying some property definable in CMSO2 logic, most notably Feedback Vertex Se…