Zobrazeno 1 - 10
of 473
pro vyhledávání: '"PILIPCZUK, MARCIN"'
Autor:
Chang, Hsien-Chih, Cohen-Addad, Vincent, Conroy, Jonathan, Le, Hung, Pilipczuk, Marcin, Pilipczuk, Michał
Cohen-Addad, Le, Pilipczuk, and Pilipczuk [CLPP23] recently constructed a stochastic embedding with expected $1+\varepsilon$ distortion of $n$-vertex planar graphs (with polynomial aspect ratio) into graphs of treewidth $O(\varepsilon^{-1}\log^{13} n
Externí odkaz:
http://arxiv.org/abs/2411.00216
Autor:
Bourneuf, Romain, Pilipczuk, Marcin
A recent work of Abbasi et al. [FOCS 2023] introduced the notion of $\varepsilon$-scatter dimension of a metric space and showed a general framework for efficient parameterized approximation schemes (so-called EPASes) for a wide range of clustering p
Externí odkaz:
http://arxiv.org/abs/2410.10191
Autor:
Cohen-Addad, Vincent, Lolck, David Rasmussen, Pilipczuk, Marcin, Thorup, Mikkel, Yan, Shuyi, Zhang, Hanwen
Correlation Clustering is a classic clustering objective arising in numerous machine learning and data mining applications. Given a graph $G=(V,E)$, the goal is to partition the vertex set into clusters so as to minimize the number of edges between c
Externí odkaz:
http://arxiv.org/abs/2404.05433
Assuming the Exponential Time Hypothesis (ETH), a result of Marx (ToC'10) implies that there is no $f(k)\cdot n^{o(k/\log k)}$ time algorithm that can solve 2-CSPs with $k$ constraints (over a domain of arbitrary large size $n$) for any computable fu
Externí odkaz:
http://arxiv.org/abs/2311.05913
Autor:
Casares, Antonio, Pilipczuk, Marcin, Pilipczuk, Michał, Souza, Uéverton S., Thejaswini, K. S.
We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time $2^{o(k \log k)} \cdot n^{O(1)}$, where $k$ is the number of pairs of vertex subsets involved in the winning con
Externí odkaz:
http://arxiv.org/abs/2310.20433
Autor:
Pilipczuk, Marcin, Rzążewski, Paweł
In this note we show a polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number.
Externí odkaz:
http://arxiv.org/abs/2310.11573
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 $x < y$, $x = y$, $x \leq y$ and $x \neq y$, and a budget $k$. The goal is to check whe
Externí odkaz:
http://arxiv.org/abs/2310.05839
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 is a subdivided claw as an induced subgraph [Abrishami, Dibek, Chudnovs
Externí odkaz:
http://arxiv.org/abs/2309.16995
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 Set, are polynomial-time solvable in the class of $P_6$-free graphs. Thi
Externí odkaz:
http://arxiv.org/abs/2307.07330
Autor:
Gartland, Peter, Lokshtanov, Daniel, Masařík, Tomáš, Pilipczuk, Marcin, Pilipczuk, Michał, Rzążewski, Paweł
We show that the \textsc{Maximum Weight Independent Set} problem (\textsc{MWIS}) can be solved in quasi-polynomial time on $H$-free graphs (graphs excluding a fixed graph $H$ as an induced subgraph) for every $H$ whose every connected component is a
Externí odkaz:
http://arxiv.org/abs/2305.15738