Graph decomposition based algorithms for maximum path coloring and connected subgraph problems

Many application problems in networks can be modeled as optimization problems in a graph G. For example, the maximum path coloring (Max-PC) problem, described next is an abstract model for many routing problems: Given a set P of paths in G and k colors,find a maximum subset of P and assign a color to each path of the subset such that the paths with the same color are edge-disjoint. One approach for solving an optimization problem in G is to decompose G into subgraphs, find partial solutions in each subgraph and combine the partial solutions into a solution of the problem. A carving-decomposition (branch-decomposition) of G is a system of edge-cuts (vertex-cuts) which decomposes G into subgraphs with each edge (vertex) a minimal subgraph. We give a carving-decomposition based exact algorithm and 1.58-approximation algorithm for the Max-PC problem. Let L be the maximum number of paths in P on any edge of G and let γ be the maximum cardinality of any edge-cut in a given carving-decomposition. Our exact algorithm and approximation algorithm run in O((L + 1)1.5kγ n2 ) and O((L + 1)1.5γ kn2 ) time, respectively. Our computational study shows that the exact algorithm can solve the Max-PC problem for small k and γ in a practical time and the approximation algorithm gives solutions close to optimal ones for practical values of k and L, and small γ. We also conduct a computational study on a branch-decomposition based exact algorithm for the maximum edge degree-bounded connected subgraph (MEDBCS) problem. Our result shows that the MEDBCS problem of vertex-degree bounded by 3 can be solved for graphs with small branchwidth in a practical time.