Zobrazeno 1 - 10
of 41
pro vyhledávání: '"Włodarczyk, Michal"'
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
We study an "above guarantee" version of the {\sc Longest Path} problem in directed graphs: We are given a graph $G$, two vertices $s$ and $t$ of $G$, and a non-negative integer $k$, and the objective is to determine whether $G$ contains a path of le
Externí odkaz:
http://arxiv.org/abs/2301.06105
Autor:
Jansen, Bart M. P., Włodarczyk, Michał
In the F-minor-free deletion problem we want to find a minimum vertex set in a given graph that intersects all minor models of graphs from the family F. The Vertex planarization problem is a special case of F-minor-free deletion for the family F = {K
Externí odkaz:
http://arxiv.org/abs/2202.02174
In the $\mathcal{F}$-Minor-Free Deletion problem one is given an undirected graph $G$, an integer $k$, and the task is to determine whether there exists a vertex set $S$ of size at most $k$, so that $G-S$ contains no graph from the finite family $\ma
Externí odkaz:
http://arxiv.org/abs/2110.01868