Parallel Connectivity in Edge-Colored Complete Graphs: Complexity Results

Given an edge-colored graph \(G_c\), a set of p pairs of vertices \((a_i,b_i)\) together with p numbers \(k_1,k_2, \ldots k_p\) associated with the pairs, can we find a set of alternating paths linking the pairs \((a_1,b_1)\), \((a_2,b_2), \ldots \), in their respective numbers \(k_1,k_2,\ldots k_p\)? Such is the question addressed in this paper. The problem being highly intractable, we consider a restricted version of it to edge-colored complete graphs. Even so restricted, the problem remains intractable if the paths/trails must be edge-disjoint, but it ceases to be so if the paths/trails are to be vertex-disjoint, as is proved in this paper. An approximation algorithm is presented in the end, with a performance ratio asymptotically close to 3/4 for a restricted version of the problem.

Data Sharing is not applicable to this article as no datasets were generated or analysed during the current studey

The author declares that no funds, grants or other support were received during the preparation of this manuscript.

Authors and Affiliations

1. Dawson College, 3040 Sherbrooke St. W, Montreal, QC, H3Z 1A4, Canada

   Rachid Saad

Corresponding author

Correspondence to Rachid Saad.

Competing interests

The author has no relevant financial or non-financial interests to disclose.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix

The 3-Factor Partition Problem: Instance: a graph G(V, E) of order n.

Question: Is there a partition of E into three edge-disjoint factors in G?

The 2-Factor Problem:

Instance: a graph G(V, E) of order n.

Question: Find two edge-disjoint factors in G, or else decide that no such two factors exist.

We will first prove that 3-Factor Partition is NP-complete.

Lemma 7.1

3-Factor Partition is NP-complete.

Proof

We will first prove the result for multigraphs. The reduction is from the well-known Chromatic Index Problem (CIP), which we present for completeness’ sake. Given in CIP are: a graph G(V, E) of order and size n and m respectively, and an integer k. What is sought then is a partition of E into k edge-disjoint matchings. It is known that CIP is NP-complete even for \(k=3\) and for regular graphs of degree 3. Let then \(G=(V,E)\) be such an instance of CIP. An instance I of 3-Factor Partition is constructed from G as follows:

1. 1)

   Construct a copy \(G^\prime \) of G

2. 2)

   For every vertex x of G, consider its counterpart \(x^\prime \) in \(G^\prime \) and link the pair \(x,x^\prime \) with the local component described below. The colors in the graph are intended to show how the component itself can be partitioned into 2-matchings. The square dots shown in the component will be referred to as the square vertices. Every pair in a triple of square vertices is linked by a double edge, as shown.

We claim that the resulting graph I has a partition of its edges into three factors if and only if G has a partition of its edges into 3 perfect matchings. Before proceeding with the proof of the claim, let us observe that the component of Fig. 7 in the construction is so designed that any partition of it into three 2-matchings \(D_1,D_2,D_3\) has one (single) path from x to \(x^\prime \) in each of its 2-matchings \(D_1,D_2,D_3\), the other edges forming cycles internal to the component. The observation follows from these two facts:

1. (a)

   the 3-partition will split the five multiple edges between \(x_i\) and \(x^\prime _i\) (for all \(i\in \{1,2,3\}\)) into two pairs of double edges and one single edge,

2. (b)

   no two single edges \(x_ix^\prime _i\) and \(x_jx^\prime _j\), with \(i\ne j\), will be in the same 2-matching of the partition, since that would destroy the unique (monochromatic) cycle of length four through \(c_i\) and \(c_j\), leaving a triple of square vertices uncoverable by the partition \(D_1, D_2, D_3\). Now for the proof of the claim.

For the if part of the proof, suppose that G has a partition into three perfect matchings \(M_1,M_2,M_3\). Consider the counterparts \(M^\prime _1,M^\prime _2,M^\prime _3\) of those matchings in \(G^\prime \). We will color \(M_1\) and \(M^\prime _1\) blue, \(M_2\) and \(M^\prime _2\) red, and \(M_3\) and \(M^\prime _3\) green. We form a factor \(F_i\) of I (for \(i\in \{1,2,3\}\) by adding to \(M_i\) and \(M^\prime _i\) (from \(i:=1\) to \(i=3\)) the 2-factor of the same color in each component representaing a vertex. We will thus have 3 factors partitioning I.

Conversely, suppose that \(F_1,F_2,F_3\) is a partition of I into 3 factors. From the above observations, each of \(F_1,F_2,F_3\), is incident to x (for every vertex x in G) with precisely one edge from G, since it contains one path from x to \(x^\prime \) inside the local component associated to x. It follows that the restriction of \(F_1,F_2,F_3\) to G is a partition of G into 3 perfect matchings, which proves the lemma for multigraphs.

To prove the lemma for graphs rather than multigraphs, we will use simple local transformations. First, we will replace the five multiple edges between \(x_i\) and \(x^\prime _i\) in the component of Fig. 7 (for every x and every \(i\in \{1,2,3\}\)) with the subcomponent constructed as follows:

1. 1)

   Make a copyA of \(K_7\), the complete graph of order 7

2. 2)

   remove one edge from A between any two arbitrarily chosen vertices, say, a, b of A

3. 3)

   embed A into the component of Fig. 7, mapping a onto \(x_i\) and b onto \(x^\prime _i\)

The subcomponent has the property that every partition of it into three 2-matchings \(D_1\), \(D_2\), \(D_3\) will be made up of two factors and one 2-matching including a path from \(x_i\) to \(x^\prime _i\), which makes the subcomponent perform the same function as the set of 5 multiple edges between \(x_i\) and \(x^\prime _i\): the path from \(x_i\) to \(x^\prime _i\) plays the part of the (single) edge involved in the partition of the 5 multiple edges into 2-matchings, while the factors act like the double edges. \(\square \)

Representation of a vertex x

Full size image

Lemma 7.2

The 2-Factor Problem is NP-hard

Proof

If we can find two edge-disjoint factors in a graph in polynomial time, then we can decide in polynomial time whether a 6-regular graph admits a partition into three edge-disjoint factors, which we know is NP-complete. \(\square \)

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions