5 citations · 17 across the 24 of their papers we have counts for
9 papers · 1 filter
Parameterized Complexity of Submodular Minimization under Uncertainty
Naonori Kakimura, Ildikó Schlotter
This paper studies the computational complexity of a robust variant of a two-stage submodular minimization problem that we call Robust Submodular Minimizer. In this problem, we are…
Arborescences, Colorful Forests, and Popularity
Telikepalli Kavitha, Kazuhisa Makino, Ildikó Schlotter +1
Our input is a directed, rooted graph where each vertex in has a partial order preference over its incoming edges. The preferences of a vertex extend nat…
Shortest Odd Paths in Undirected Graphs with Conservative Weight Functions
Alpár Jüttner, Csaba Király, Lydia Mirabel Mendoza-Cadena +3
We consider the Shortest Odd Path problem, where given an undirected graph , a weight function on its edges, and two vertices and in , the aim is to find an -p…
Shortest two disjoint paths in conservative graphs
Ildikó Schlotter
We consider the following problem that we call the Shortest Two Disjoint Paths problem: given an undirected graph with edge weights , two term…
The popular assignment problem: when cardinality is more important than popularity
Telikepalli Kavitha, Tamás Király, Jannik Matuschke +2
We consider a matching problem in a bipartite graph where nodes in are agents having preferences in partial order over their neighbors, while nodes in are o…
Popular Branchings and Their Dual Certificates
Telikepalli Kavitha, Tamás Király, Jannik Matuschke +2
Let be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings, i.e., directed forests; a…
Stable Marriage with Covering Constraints: A Complete Computational Trichotomy
Matthias Mnich, Ildikó Schlotter
We consider Stable Marriage with Covering Constraints (SMC): in this variant of Stable Marriage, we distinguish a subset of women as well as a subset of men, and we seek a matching…
Cleaning Interval Graphs
Dániel Marx, Ildikó Schlotter
We investigate a special case of the Induced Subgraph Isomorphism problem, where both input graphs are interval graphs. We show the NP-hardness of this problem, and we prove fixed-…
Obtaining a Planar Graph by Vertex Deletion
Dániel Marx, Ildikó Schlotter
In the k-Apex problem the task is to find at most k vertices whose deletion makes the given graph planar. The graphs for which there exists a solution form a minor closed class of…