Given a connected graph $G$ and a vertex $v$, is it polynomially solvable to find a maximal cardinality set of edges incident to $v$, which deletion (still) leaves vertex $v$ to be connected with all the other vertices in $G$?

  • 9
    $\begingroup$ If I'm not mistaken this is an easy task. Remove $v$ and count the connected components, let $k$ be that number. Then at most $\deg(v)-k$ edges can be removed from $v$. $\endgroup$ – John D. Jul 7 '14 at 11:17
  • $\begingroup$ Sorry for not being completely clear in the question. Can these $\deg (v) -k$ edges be found in a polynomial time? $\endgroup$ – simco Jul 7 '14 at 11:28
  • 7
    $\begingroup$ Just keep a single edge going from $v$ to each connected component... $\endgroup$ – R B Jul 7 '14 at 11:37
  • 1
    $\begingroup$ I think you have been misled, this doesn't seem the right way to formulate the problem stated in the title; I would suggest looking at possible applications of the Gallai-Edmonds decomposition to your question (Thm 2.2.3 in Diestel's textbook). $\endgroup$ – Stephan Krilow Jul 7 '14 at 13:33
  • 2
    $\begingroup$ @user17410 That should be an answer. $\endgroup$ – David Richerby Jul 8 '14 at 7:15

Construct a DFS traversal tree, starting from $v$.

You can remove all edges of v that are not part of the tree.

The tree construction costs $O(|V|+|E|)$.

The identification of the edges that can be removed is $O(deg(v))$.

| cite | improve this answer | |

Your Answer

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