Dual graph

In the mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs (graphs that are already embedded in the plane) rather than planar graphs (graphs that may be embedded but for which the embedding is not yet known). For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph. Historically, the first form of graph duality to be recognized was the as

New Results in Integer and Lattice Programming

Christoph Hunkenschröder

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

b \in \Z^m

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem of finding an optimal solution for an integer program is known as integer programming. Integer programming is NP-hard in general, though several algorithms exist: Lenstra provided an algorithm that is polynomial if the dimension

n

is fixed. For variable dimension, the best known algorithm depends linearly on

n

, and exponentially on the number of equalities as well as the largest absolute value of an entry in the matrix

A

. The first part of this thesis considers integer programming for variable dimensions and sparse matrices. We measure the sparsity of a matrix by the tree-depth of the dual graph of

A

. A typical example for these integer programs are

N

-fold IPs, used for scheduling and social choice problems. We obtain the currently fastest fixed-parameter tractable algorithm with parameters tree-depth and the largest absolute value of the entries in

A

. The running time we achieve is near-linear in the dimension. With a slightly worse running time, we are able to show that

N

-fold integer programs of constant block size can be solved in strongly polynomial time. Assuming the exponential time hypothesis, we complement these results with a lower bound on the parameter dependency that almost matches the parameter dependency of the running time. As a consequence, we provide the currently strongest lower bound for

N

-fold integer programs. Another problem closely related to integer programming is the closest vector problem. A lattice is a discrete additive subgroup of

\R^n

. The closest vector problem (CVP) asks for a lattice point closest to a given target vector. An important tool for solving the closest vector problem is the Voronoi cell

\vc

of a lattice

\Lambda \subseteq \R^n

, which is the set of all points for which

0

is a closest lattice point. It is a polytope whose facets are induced by a set of lattice vectors, the Voronoi relevant vectors. A generic lattice has exponentially many Voronoi relevant vectors, leading to exponential space for certain CVP algorithms. In the second part of this thesis, we introduce the notion of a

c

-compact lattice basis

B \in \R^{n \times n}

that facilitates to represent the Voronoi relevant vectors with coefficients bounded by

c

. Such a basis allows to reduce the space requirement of Micciancio's & Voulgaris' algorithm for the closest vector problem from exponential to polynomial, while the running time becomes exponential in

c

. We show that for every lattice an

n^2

-compact basis exists, but there are lattices for which we cannot choose

c \in o (n)

. If the Voronoi cell is a zonotope, we can choose

c=1

, providing a single-exponential time and polynomial space algorithm for CVP, assuming a

1

-compact basis is known. Deciding whether a given lattice has a certain structure that helps to solve the closest vector problem more efficiently is a reappearing and non-trivial problem. The third part of this thesis is concerned with the specific structure of having an orthonormal basis. We show that this problem belongs to NP

\cap

co-NP. Moreover, it can be reduced to solving a single closest vector problem. We also show that if a separation oracle for the Voronoi cell is provided, CVP is solvable in polynomial time.

EPFL2020

New Results in Integer and Lattice Programming

Christoph Hunkenschröder

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

b \in \Z^m

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

n

is fixed. For variable dimension, the best known algorithm depends linearly on

n

, and exponentially on the number of equalities as well as the largest absolute value of an entry in the matrix

A

. The first part of this thesis considers integer programming for variable dimensions and sparse matrices. We measure the sparsity of a matrix by the tree-depth of the dual graph of

A

. A typical example for these integer programs are

N

A

. The running time we achieve is near-linear in the dimension. With a slightly worse running time, we are able to show that

N

N

-fold integer programs. Another problem closely related to integer programming is the closest vector problem. A lattice is a discrete additive subgroup of

\R^n

. The closest vector problem (CVP) asks for a lattice point closest to a given target vector. An important tool for solving the closest vector problem is the Voronoi cell

\vc

of a lattice

\Lambda \subseteq \R^n

, which is the set of all points for which

0

c

-compact lattice basis

B \in \R^{n \times n}

that facilitates to represent the Voronoi relevant vectors with coefficients bounded by

c

c

. We show that for every lattice an

n^2

-compact basis exists, but there are lattices for which we cannot choose

c \in o (n)

. If the Voronoi cell is a zonotope, we can choose

c=1

, providing a single-exponential time and polynomial space algorithm for CVP, assuming a

1

\cap

co-NP. Moreover, it can be reduced to solving a single closest vector problem. We also show that if a separation oracle for the Voronoi cell is provided, CVP is solvable in polynomial time.

EPFL2020

An Maxflow Algorithm for Directed Planar Graphs

New Results in Integer and Lattice Programming

Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs

An Maxflow Algorithm for Directed Planar Graphs

New Results in Integer and Lattice Programming

Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs