Zobrazeno 1 - 10
of 101
pro vyhledávání: '"Włodarczyk, Michał"'
Autor:
Włodarczyk, Michał
In the Weighted Treewidth-$\eta$ Deletion problem we are given a node-weighted graph $G$ and we look for a vertex subset $X$ of minimum weight such that the treewidth of $G-X$ is at most $\eta$. We show that Weighted Treewidth-$\eta$ Deletion admits
Externí odkaz:
http://arxiv.org/abs/2410.06343
Autor:
Włodarczyk, Michał
In the Disjoint Paths problem, one is given a graph with a set of $k$ vertex pairs $(s_i,t_i)$ and the task is to connect each $s_i$ to $t_i$ with a path, so that the $k$ paths are pairwise disjoint. In the optimization variant, Max Disjoint Paths, t
Externí odkaz:
http://arxiv.org/abs/2409.03596
Autor:
Włodarczyk, Michał
We investigate the question whether Subset Sum can be solved by a polynomial-time algorithm with access to a certificate of length poly(k) where k is the maximal number of bits in an input number. In other words, can it be solved using only few nonde
Externí odkaz:
http://arxiv.org/abs/2409.03526
Given an undirected graph $G$ and a multiset of $k$ terminal pairs $\mathcal{X}$, the Vertex-Disjoint Paths (\VDP) and Edge-Disjoint Paths (\EDP) problems ask whether $G$ has $k$ pairwise internally vertex-disjoint paths and $k$ pairwise edge-disjoin
Externí odkaz:
http://arxiv.org/abs/2309.16892
We study the classic {\sc Dominating Set} problem with respect to several prominent parameters. Specifically, we present algorithmic results that sidestep time complexity barriers by the incorporation of either approximation or larger parameterizatio
Externí odkaz:
http://arxiv.org/abs/2309.15645
The celebrated notion of important separators bounds the number of small $(S,T)$-separators in a graph which are 'farthest from $S$' in a technical sense. In this paper, we introduce a generalization of this powerful algorithmic primitive that is phr
Externí odkaz:
http://arxiv.org/abs/2309.11366
We study the parameterized complexity of two classic problems on directed graphs: Hamiltonian Cycle and its generalization {\sc Longest Cycle}. Since 2008, it is known that Hamiltonian Cycle is W[1]-hard when parameterized by directed treewidth [Lamp
Externí odkaz:
http://arxiv.org/abs/2308.06145
Autor:
Włodarczyk, Michał, Zehavi, Meirav
In the Planar Disjoint Paths problem, one is given an undirected planar graph with a set of $k$ vertex pairs $(s_i,t_i)$ and the task is to find $k$ pairwise vertex-disjoint paths such that the $i$-th path connects $s_i$ to $t_i$. We study the proble
Externí odkaz:
http://arxiv.org/abs/2307.06792
The notion of $\mathcal{H}$-treewidth, where $\mathcal{H}$ is a hereditary graph class, was recently introduced as a generalization of the treewidth of an undirected graph. Roughly speaking, a graph of $\mathcal{H}$-treewidth at most $k$ can be decom
Externí odkaz:
http://arxiv.org/abs/2306.17065
Autor:
Wlodarczyk, Michal
In Chordal/Interval Vertex Deletion we ask how many vertices one needs to remove from a graph to make it chordal (respectively: interval). We study these problems under the parameterization by treewidth $tw$ of the input graph $G$. On the one hand, w
Externí odkaz:
http://arxiv.org/abs/2305.03440