3 citations · 12 across the 26 of their papers we have counts for
7 papers · 1 filter
Induced Matching below Guarantees: Average Paves the Way for Fixed-Parameter Tractability
Tomohiro Koana
In this work, we study the Induced Matching problem: Given an undirected graph and an integer , is there an induced matching of size at least ? An edge subset $…
Correlating Theory and Practice in Finding Clubs and Plexes
Aleksander Figiel, Tomohiro Koana, André Nichterlein +1
Finding large "cliquish" subgraphs is a classic NP-hard graph problem. In this work, we focus on finding maximum -clubs and -plexes, i.e., graphs of diameter and graphs w…
Kernelization for Partial Vertex Cover via (Additive) Expansion Lemma
Tomohiro Koana, André Nichterlein, Niklas Wünsche
Given a graph and two integers and , Partial Vertex Cover asks for a set of at most vertices whose deletion results in a graph with at most edges. Based on the…
The Complexity of Finding Fair Many-to-One Matchings
Niclas Boehmer, Tomohiro Koana
We analyze the (parameterized) computational complexity of "fair" variants of bipartite many-to-one matching, where each vertex from the "left" side is matched to exactly one verte…
Stable Matching with Multilayer Approval Preferences: Approvals can be Harder than Strict Preferences
Matthias Bentert, Niclas Boehmer, Klaus Heeger +1
We study stable matching problems where agents have multilayer preferences: There are layers each consisting of one preference relation for each agent. Recently, Chen et al.…
Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees
Leon Kellerhals, Tomohiro Koana, Pascal Kunz
Vertex Cover parameterized by the solution size k is the quintessential fixed-parameter tractable problem. FPT algorithms are most interesting when the parameter is small. Several…
Covering Many (or Few) Edges with k Vertices in Sparse Graphs
Tomohiro Koana, Christian Komusiewicz, André Nichterlein +1
We study the following two fixed-cardinality optimization problems (a maximization and a minimization variant). For a fixed between zero and one we are given a graph and two nu…