11/06/2026 - 15:00 - CORE C.035 -
(Université de Rennes)
will give a presentation on
Abstract:
Given a graph G=(V,E), an induced path (resp. tree) is a set of vertices inducing path (resp. tree). We consider the convex hull of 0/1-vector in \mathbb{R}^V \times \mathbb{R}^E encoding induced path (resp. induced trees).
Our first main result is that, for chordal graphs, the incidence vectors of induced paths (respectively, induced trees) form a \emph{Hilbert basis}: every
integer vector in their conic hull can be expressed as a nonnegative integer combination of these incidence vectors. Hilbert bases are of interest in combinatorial optimization due to their close relationship with totally dual integral systems, which are known to yield integer polyhedra when their
right-hand side is integral.
Somewhat surprisingly, we do not exploit this connection directly. Instead, the Hilbert basis property allows us to derive linear descriptions of the
\emph{induced path polytope} and the \emph{induced tree polytope} of chordal graphs, defined as the convex hulls of the corresponding incidence vectors. The description we obtain for the induced tree polytope has polynomial size. For the induced path polytope, our initial system contains exponentially many inequalities; we therefore identify those defining facets and show that their
number is, in fact, polynomial.
These polyhedral characterizations imply that the problems of finding a maximum or minimum-weight induced path or induced tree are polynomially
solvable on chordal graphs.
Finally, we show how this result can be used to find maximum weight \emph{co-3-plexes}, that are sets of vertices inducing subgraphs of maximum degree 2. In fact, we exhibit a polynomial-time algorithm based on column generation solving the latter.