$K_2$-Node Expansion Problems

Abstract

In this paper, we introduce the concept of node expansion. Node expansion is a generalization of edge subdivision and an inverse of subgraph contraction. A graph $G_1=(V_1,E_1)$ is an $H$-node expansion of $G=(V,E)$ if and only if $G_1$ contains a subgraph $H=(V_H,E_H)$ such that $V=V_1–V_H\cup \{v\}$ and $E=E_1–E_H\cup \{vw|wh\in E_1\text{and}h\in V_H\}\cup \{v\}$. The concept of node expansion is of considerable importance in modernization of networks.

We consider the node expansion problem of transforming a graph to a bipartite graph with a minimum number of node expansions using $K_2$. We show that the $K_2$-node expansion problem is NP-Complete for general graphs and remains so if the input graph has maximum degree 3. However, we present a $O(n^2\log n+mn+p^3)$ algorithm for the case when the input graph is restricted to be planar $3$-connected and output graph is required to be planar bipartite.