Now showing items 1-14 of 14

• #### Balanced judicious bipartition is fixed-parameter tractable ﻿

(Journal article; Peer reviewed, 2019)
The family of judicious partitioning problems, introduced by Bollobás and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view for over two decades. This rich realm of ...
• #### Connecting the Dots (with Minimum Crossings) ﻿

(Journal article; Peer reviewed, 2019)
We study a prototype Crossing Minimization problem, defined as follows. Let F be an infinite family of (possibly vertex-labeled) graphs. Then, given a set P of (possibly labeled) n points in the Euclidean plane, a collection ...
• #### Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals ﻿

(Peer reviewed; Journal article, 2019)
Perturbed graphic matroids are binary matroids that can be obtained from a graphic matroid by adding a noise of small rank. More precisely, an r-rank perturbed graphic matroid M is a binary matroid that can be represented ...
• #### Decomposition of map graphs with applications ﻿

(Peer reviewed; Journal article, 2019)
• #### ETH-tight algorithms for long path and cycle on unit disk graphs ﻿

(Journal article; Peer reviewed, 2020)
We present an algorithm for the extensively studied Long Path and Long Cycle problems on unit disk graphs that runs in time 2O(√k)(n + m). Under the Exponential Time Hypothesis, Long Path and Long Cycle on unit disk graphs ...
• #### Fault tolerant subgraphs with applications in kernelization ﻿

(Journal article; Peer reviewed, 2020)
In the past decade, the design of fault tolerant data structures for networks has become a central topic of research. Particular attention has been given to the construction of a subgraph H of a given digraph D with as ...
• #### Going Far from Degeneracy ﻿

(Journal article; Peer reviewed, 2020)
An undirected graph $G$ is $d$-degenerate if every subgraph of $G$ has a vertex of degree at most $d$. By the classical theorem of Erdös and Gallai from 1959, every graph of degeneracy $d>1$ contains a cycle of length at ...
• #### Going Far From Degeneracy ﻿

(Peer reviewed; Journal article, 2019-09-06)
An undirected graph G is d-degenerate if every subgraph of G has a vertex of degree at most d. By the classical theorem of Erd\H{o}s and Gallai from 1959, every graph of degeneracy d>1 contains a cycle of length at least ...
• #### Packing arc-disjoint cycles in tournaments ﻿

(Journal article; Peer reviewed, 2019)
A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Given a tournament T on n vertices, we explore the classical and parameterized complexity of the problems of determining ...
• #### Packing cycles faster than Erdos-Posa ﻿

(Journal article; Peer reviewed, 2019)
The Cycle Packing problem asks whether a given undirected graph $G=(V,E)$ contains $k$ vertex-disjoint cycles. Since the publication of the classic Erdös--Pósa theorem in 1965, this problem received significant attention ...
• #### Parameterization Above a Multiplicative Guarantee ﻿

(Journal article; Peer reviewed, 2020)
Parameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixed-parameter tractable problems in this paradigm share an additive form defined as follows. Given ...
• #### The Parameterized Complexity of Guarding Almost Convex Polygons ﻿

(Journal article; Peer reviewed, 2020)
The Art Gallery problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide ...
• #### Rank vertex cover as a natural problem for algebraic compression ﻿

(Journal article; Peer reviewed, 2019)
The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem was a long-standing, notorious open problem in parameterized complexity. Some years ago, the breakthrough work by Kratsch and ...
• #### Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems ﻿

(Peer reviewed; Journal article, 2019)
We consider four well-studied NP-complete packing/covering problems on graphs: Feedback Vertex Set in Tournaments (FVST), Cluster Vertex Deletion (CVD), Triangle Packing in Tournaments (TPT) and Induced P3-Packing. For ...