11
$\begingroup$

Let $G=(V,E)$ be an undirected graph with $|V|\geq 4$ such that for any distinct vertices $a_1,a_2,b_1,b_2$, there is a path from $a_1$ to $a_2$ and a (vertex-)disjoint path from $b_1$ to $b_2$ (in other words, the graph is $2$-linked).

Assign a nonnegative real number to each vertex in $V$. Suppose the sum of these numbers is $2s$, and a subset of them has sum exactly $s$. What is the largest constant $c$ for which (regardless of $G$ and $s$) there always exists a subset $V'\subseteq V$ such that both $V'$ and $V\backslash V'$ form connected subgraphs, and the sum of the numbers in $V'$ belongs to $[cs,s]$?

The following example shows that $c\leq 5/6$: a clique $K_5$ with one edge $e$ removed, numbers $3,3$ on the two vertices adjacent to $e$, and $2,2,2$ on the remaining vertices. Another example is to take $K_{3,3}$ with $3,3,3$ on one side and $1,1,1$ on the other. Is $c=5/6$ tight?

(It is easy to see that such a constant $c$ must exist: $c=0$ works since for any connected graph, its vertices can be partitioned into two parts such that both parts are connected.)

$\endgroup$
  • $\begingroup$ Instead of 4,1,1, you could simply use 2,2,2. Also, do you require $a_1,a_2,b_1,b_2$ to be different and $G$ to have at least 4 vertices? $\endgroup$ – domotorp Sep 29 '19 at 21:28
  • $\begingroup$ It helps me to see why such a constant should exist... By considering $c=0$ we see that your conditions are met: there always exists a subset $V'\subseteq V$ such that both $V'$ and $V\backslash V'$ form connected subgraphs, and the sum of the numbers in $V'$ belongs to $[cs, s] = [0,s]$, regardless of $G$ and $s$. This because we can always find two adjacent vertices $a, b$ such that $\rho(a)+\rho(b)\leq s$, and take $V'= \{a,b\}$. Then by the vertex-disjoint path property $V\backslash V'$ is connected. Perhaps you could add this to the question. $\endgroup$ – Franka Waaldijk Oct 21 '19 at 9:41
  • $\begingroup$ Another example with $c=5/6$, is to take $K_{3,3}$ with weights of 3,3,3 on one side and 1,1,1 on the other. $\endgroup$ – Tony Huynh Oct 21 '19 at 15:59
  • $\begingroup$ @nan are you satisfied with the answer below? $\endgroup$ – mathworker21 Oct 26 '19 at 8:57
4
$\begingroup$

Here is an argument that shows a lowerbound of $c \geq \frac{2}{3}$. For this, we only need the weaker assumptions that $G$ is $2$-connected and the weight of each vertex is at most $\frac{W}{2}$, where $W$ is the total weight. Both these assumptions are clearly implied by the hypotheses of the original question.

Theorem. Let $G=(V,E)$ be a $2$-connected graph and $w: V \to \mathbb{R}_{\geq 0}$ be such that $w(v) \leq \frac{1}{2}\sum_{u \in V} w(u):=\frac{W}{2}$ for all $v \in V$. Then there exists a subset $X \subseteq V$ such that $G[X]$ and $G[V \setminus X]$ are both connected and $\frac{W}{3} \leq \sum_{u \in X} w(u) \leq \frac{W}{2}$.

Proof. We proceed by induction on $|E|$. If $|E|=3$, then $G=K_3$. In this case, there is a vertex $x$ with $w(x) \geq \frac{W}{3}$, so we may take $X=\{x\}$. For the inductive step, first note that we may assume $w(u) < \frac{W}{3}$ for all $u \in V$. Otherwise, we can take $X=\{u\}$, since $G-u$ is connected by $2$-connectivity. Choose a spanning tree $T$ of $G$, and let $x$ be a leaf of $T$ and $y$ be the unique neighbour of $x$ in $T$. By assumption, $w(x)+w(y) < \frac{2W}{3}$. If $w(x)+w(y) > \frac{W}{2}$, we may take $X=V \setminus \{x,y\}$. Therefore, we may assume that $w(x)+w(y) \leq \frac{W}{2}$. We use the well-known fact that in a $2$-connected graph, every edge can be either deleted or contracted to maintain $2$-connectivity. Let $e=xy$. If $G \setminus e$ is $2$-connected, we can apply induction. If $G / e$ is $2$-connected, we let the contracted vertex have weight $w(x)+w(y)$ and we apply induction. $\square$

Note that $2$-connectedness is required to prove $c>0$. To see this consider a star with $k$ leaves where each leaf has weight $1$ and the center of the star has weight $k$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.