3 problems

Let MOTJ denote the problem of deciding, for an undirected graph $G=(V,E)$ with rational edge weights $w:E\to\mathbb{Q}$, a set $T\subseteq V$, and $k\in\mathbb{Q}$, whether there…

Let $G$ be a graph, and let $T$ be the set of its odd-degree vertices. A $T$-join is a subgraph whose odd-degree vertices are precisely the vertices in $T$, and a $T$-cut is a cut…

Let $G$ be a plane graph and let $T$ be an even-size subset of its vertices. A $T$-join is a subgraph whose odd-degree vertices are precisely the vertices in $T$, and a $T$-cut is…