5 papers
On Circuit Diameter and Straight Line Complexity
Daniel Dadush, Stefan Kober, Zhuan Khye Koh
The circuit diameter of a polyhedron is the maximum length (number of steps) of a shortest circuit walk between any two vertices of the polyhedron. Introduced by Borgwardt, Finhold…
Face covers and rooted minors in bounded genus graphs
Samuel Fiorini, Stefan Kober, Michał T. Seweryn +2
A {\em rooted graph} is a graph together with a designated vertex subset, called the {\em roots}. In this paper, we consider rooted graphs embedded in a fixed surface. A collection…
Totally -modular IPs with two non-zeros in most rows
Stefan Kober
Integer programs (IPs) on constraint matrices with bounded subdeterminants are conjectured to be solvable in polynomial time. We give a strongly polynomial time algorithm to solve…
Integer programs with nearly totally unimodular matrices: the cographic case
Manuel Aprile, Samuel Fiorini, Gwenaël Joret +4
It is a notorious open question whether integer programs (IPs), with an integer coefficient matrix whose subdeterminants are all bounded by a constant in absolute value, ca…
Total Matching and Subdeterminants
Luca Ferrarini, Samuel Fiorini, Stefan Kober +1
In the total matching problem, one is given a graph with weights on the vertices and edges. The goal is to find a maximum weight set of vertices and edges that is the non-incid…