1
$\begingroup$

Given B and C operations.

  • B-operation: When two multi-edges connect a pair of vertices, replace the multi-edges with a single edge connecting the pair of vertices.

  • C-operation: When one edge connects vertices $u$ and $v$, another edge connects $v$ and $w$ (where $u \ne w$), and there is no other edge incident to $v$, remove the vertex $v$, and replace the two edges with a new edge connecting $u$ and $w$.

Input a graph with n vertices and m edges, and check whether it can be reduced to a single edge with two vertices. How to make the algorithm be $O(m+n)$ time complexity?

My thought is to record the deg of vertices. But can't figure out what to do next.

$\endgroup$
2
  • $\begingroup$ An idea: I believe that for a normal undirected graph (without multiedges!) not being reduced to a line graph is equivalent to one node having degree $\geq 3$. There is a simple $O(m+n)$ algorithm that removes all multiedges from a graph. $\endgroup$
    – plshelp
    Apr 17, 2022 at 19:19
  • $\begingroup$ @plshelp. Consider the graph with edges AB, BE, AC, CE, AD, DE. $\endgroup$
    – John L.
    Apr 18, 2022 at 8:29

1 Answer 1

1
$\begingroup$

The Simple Idea

Keep the graph without multi-edges by B-operations. Apply C-operation whenever we can, keeping track of possible new opportunities of C-operations in a set of vertices.

A Simple Algorithm

Assume there is no loops in the graph.

  1. Replace all edges between the same pair of vertices by one edge.
    There will be at most $m$ edges left. The graph is a simple graph now.
  2. Put all vertices in a set $S$.
  3. Repeat the following routine until $S$ is empty.
    1. Poll $S$ to get a vertex $v$.
    2. If the degree of $v$ is 2,
      1. apply the C-operation that removes $v$ together with two edges incident to $v$ and adds an edge between vertex $u$ and $w$. If there has been another edge between $u$ and $w$, merge these two edges by a B-operation, so that the graph remains a simple graph.
      2. add $u$ and $w$ to $S$.
  4. Return "Yes" if the graph is a single edge with two vertices. Otherwise, return "No".

Time-Complexity Analysis

Each execution of step 3.2.1 will reduce the number of edges in the graph at least by 1. Hence step 3.2.1 can be executed at most $m$ times. That means step 3.2.2 can be executed at most $m$ times, too.

Hence, the number of times a vertex is added to $S$ by step 3.2.2 is at most $2m$. Since $S$ contains $n$ vertices initially, the total number of times that a vertex is added to $S$ is $n+2m$. So the total number of times the removal of a vertex from $S$ can be done by step 3.1 is at most $n+2m$. That is, step 3.1 can be executed at most $n+2m$ times.

Hence the running time of step 3 is $O(n+m)$. The running time of step 1 and step 2 is $O(n+m)$. So, the time-complexity of the algorithm is $O(n+m)$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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