Eric Brandwein

dblp:333/9219 · DBLP profile ↗
← Back
3ranked-venue papers
0as first author
3since 2021 · last 2026
0009-0003-2559-7173ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 3 since 2021Artificial intelligence and machine learning · 1 · 1 since 2021
YearPublicationVenuePosition
2026 Kernelization Dichotomies for Hitting Minors Under Structural Parameterizations
abstract
For a finite collection of connected graphs $\mathcal{F}$, the $\mathcal{F}$-MINOR-DELETION problem consists in, given a graph $G$ and an integer $\ell$, deciding whether $G$ contains a vertex set of size at most $\ell$ whose removal results in an $\mathcal{F}$-minor-free graph. We lift the existence of (approximate) polynomial kernels for $\mathcal{F}$-MINOR-DELETION by the solution size to (approximate) polynomial kernels parameterized by the vertex-deletion distance to graphs of bounded elimination distance to $\mathcal{F}$-minor-free graphs. This results in exact polynomial kernels for every family $\mathcal{F}$ that contains a planar graph, and an approximate polynomial kernel for PLANAR VERTEX DELETION. Moreover, combining our result with a previous lower bound, we obtain the following infinite set of dichotomies, assuming $NP \not\subseteq coNP/poly$: for any finite set $\mathcal{F}$ of biconnected graphs on at least three vertices containing a planar graph, and any minor-closed class of graphs $\mathcal{C}$, $\mathcal{F}$-MINOR-DELETION admits a polynomial kernel parameterized by the vertex-deletion distance to $\mathcal{C}$ if and only if $\mathcal{C}$ has bounded elimination distance to $\mathcal{F}$-minor-free graphs. For instance, this yields dichotomies for CACTUS VERTEX DELETION, OUTERPLANAR VERTEX DELETION, and TREEWIDTH-$t$ VERTEX DELETION for every integer $t \geq 0$. Prior to our work, such dichotomies were only known for the particular cases of VERTEX COVER and FEEDBACK VERTEX SET. We also provide lower bounds on the size of the kernels.
Marin Bougeret, Eric Brandwein, Ignasi Sau
STACS2
2025 On the thinness of trees
Flavia Bonomo-Braberman, Eric Brandwein, Carolina Lucía Gonzalez, Agustín Sansone
Discret. Appl. Math.2
2022 On the Thinness of Trees
Flavia Bonomo-Braberman, Eric Brandwein, Carolina Lucía Gonzalez, Agustín Sansone
ISCO2