-
Article
Open AccessMaximum Matchings in Geometric Intersection Graphs
Let G be an intersection graph of n geometric objects in the plane. We show that a maximum matching in G can be found in $$O\hspace{0.33325pt}...
-
Article
Grundy Coloring and Friends, Half-Graphs, Bicliques
The first-fit coloring is a heuristic that assigns to each vertex, arriving in a specified order \(\sigma \) ...
-
Chapter and Conference Paper
Cutting Barnette Graphs Perfectly is Hard
A perfect matching cut is a perfect matching that is also a cutset, or equivalently a perfect matching containing an even number of edges on every cycle. The corresponding algorithmic problem, Perfect Matching Cu...
-
Article
Twin-width and Polynomial Kernels
We study the existence of polynomial kernels, for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. Our main result is that a polynomial ker...
-
Article
The complexity of mixed-connectivity
We investigate the parameterized complexity in a and b of determining whether a graph G has a subset of a vertices and b edges whose removal disconnects G, or disconnects two prescribed vertices
-
Article
Open AccessMetric Dimension Parameterized By Treewidth
A resolving set S of a graph G is a subset of its vertices such that no two vertices of G have the same distance vector to S. The Metric Dimension problem asks for a resolving set of minimum size, and in its deci...
-
Article
The Inverse Voronoi Problem in Graphs II: Trees
We consider the inverse Voronoi diagram problem in trees: given a tree T with positive edge-lengths and a collection \(\mathbb {U}\) ...
-
Article
The Inverse Voronoi Problem in Graphs I: Hardness
We introduce the inverse Voronoi diagram problem in graphs: given a graph G with positive edge-lengths and a collection \({\mathbb {U}}\) U of subsets of vertices of V(G), decide whether \({\mathbb {U}}\) U
-
Article
Parameterized Complexity of Independent Set in H-Free Graphs
In this paper, we investigate the complexity of Maximum Independent Set (MIS) in the class of H-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem remains NP-hard ...
-
Article
Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality is the Key to Single-Exponential Parameterized Algorithms
It has long been known that Feedback Vertex Set can be solved in time \(2^{{\mathcal {O}}(w\log w)}n^{{\mathcal {O}}(1)}\) ...
-
Article
Open AccessOptimality Program in Segment and String Graphs
Planar graphs are known to allow subexponential algorithms running in time \(2^{O(\sqrt{n})}\)
-
Chapter and Conference Paper
Constraint Generation Algorithm for the Minimum Connectivity Inference Problem
Given a hypergraph H, the Minimum Connectivity Inference problem asks for a graph on the same vertex set as H with the minimum number of edges such that the subgraph induced by every hyperedge of H is connected....
-
Article
Open AccessComplexity of Token Swap** and Its Variants
In the Token Swap** problem we are given a graph with a token placed on each vertex. Each token has exactly one destination vertex, and we try to move all the tokens to their destinations, using the minimum num...
-
Article
Sparsification and subexponential approximation
Instance sparsification is well-known in the world of exact computation since it is very closely linked to the Exponential Time Hypothesis. In this paper, we extend the concept of sparsification in order to captu...
-
Chapter and Conference Paper
Optimality Program in Segment and String Graphs
Planar graphs are known to allow subexponential algorithms running in time \(2^{O(\sqrt{n})}\)
-
Chapter and Conference Paper
A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs
We study the polynomial time approximation of the max k-vertex cover problem in bipartite graphs and propose a purely combinatorial algorithm that beats the only such known algorithm, namely the greedy appro...
-
Chapter and Conference Paper
Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property
For a class of graphs \(\mathcal {P}\) , the Bounded ...
-
Article
Multi-parameter Analysis for Local Graph Partitioning Problems: Using Greediness for Parameterization
We study the parameterized complexity of a broad class of problems called “local graph partitioning problems” that includes the classical fixed cardinality problems as max
-
Chapter and Conference Paper
Complexity of Grundy Coloring and Its Variants
The Grundy number of a graph is the maximum number of colors used by the greedy coloring algorithm over all vertex orderings. In this paper, we study the computational complexity of Grundy Coloring, the problem o...
-
Chapter and Conference Paper
Draws, Zugzwangs, and PSPACE-Completeness in the Slither Connection Game
Two features set Slither apart from other connection games. Previously played stones can be relocated and some stone configurations are forbidden. We show that the interplay of these peculiar mechanics with the s...
