{'fraction_non_alphanumeric': 0.03205562327870333, 'fraction_numerical': 0.01182897647749334, 'mean_word_length': 4.521500685529104, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Algorithm Framework for the Exact Solution and Improved Approximation of the Maximum Weighted Independent Set Problem

The Maximum Weighted Independent Set (MWIS) problem, which considers a graph with weights assigned to nodes and seeks to discover the"heaviest"independent set, that is, a set of nodes with maximum total weight so that no two nodes in the set are connected by an edge. The MWIS problem arises in many application domains, including the resource-constrained scheduling, error-correcting coding, complex system analysis and optimization, and communication networks. Since solving the MWIS problem is the core function for finding the optimum solution of our novel graph-based formulation of the resource-constrained Process Planning and Scheduling (PPS) problem, it is essential to have"good-performance"algorithms to solve the MWIS problem. In this paper, we propose a Novel Hybrid Heuristic Algorithm (NHHA) framework in a divide-and-conquer structure that yields optimum feasible solutions to the MWIS problem. The NHHA framework is optimized to minimize the recurrence. Using the NHHA framework, we also solve the All Maximal Independent Sets Listing (AMISL) problem, which can be seen as the subproblem of the MWIS problem. Moreover, building composed MWIS algorithms that utilizing fast approximation algorithms with the NHHA framework is an effective way to improve the accuracy of approximation MWIS algorithms (e.g., GWMIN and GWMIN2 (Sakai et al., 2003)). Eight algorithms for the MWIS problem, the exact MWIS algorithm, the AMISL algorithm, two approximation algorithms from the literature, and four composed algorithms, are applied and tested for solving the graph-based formulation of the resource-constrained PPS problem to evaluate the scalability, accuracy, and robustness.


Introduction
As one of the most challenging problems in graph theory, the problem of finding the Maximum Weighted Independent Set (MWIS) considers a graph with weights assigned to nodes and seeks to identify the "heaviest" independent set, that is, a set of nodes with maximum total weight so that no two nodes in the set are connected by an edge. We name such a graph as a conflicting weighted graph. The statement of the MWIS problem looks relatively simple; however, solving the MWIS problem on general graphs is computationally difficult. It has been shown to be an NP-hard problem (Köhler & Mouatadid, 2016), so it is unlikely to be solved in polynomial time.
Inspired by a simple philosophy understanding, "nothing in the world stands by itself. Every object is connected in an endless chain and is thus connected with all the other links. And this chain unites all objects and processes in a single whole and thus has a universal character," if we can abstract a real-world engineering/optimization problem as a graph with nodes representing subproblems (or possible solutions of subproblems) and edges representing their relationships, then the global optimum solution can be found by solving the MWIS problem on such a graph. This type of formulation arises in many applications, including resource allocation, scheduling and staffing problems, error-correcting coding, complex system analysis and optimization, logistics and transportation, and communication networks. Modeling scheduling problems as such graphs are particularly relevant in the presence of incompatible entities to be scheduled. Our particular interest is focusing on the general type of Process Planning and Scheduling (PPS) problem (Sun et al., preprint). Therefore, in order to utilize the concept of the MWIS in our PPS application, low-complexity algorithms for solving the MWIS problem that yields "good-quality" feasible solutions (guaranteed independent nodes in the set) are desired.
In this paper, we propose a Novel Hybrid Heuristic Algorithm (NHHA) framework in a divide-and-conquer structure that yields optimum feasible solutions to the MWIS problem. The NHHA framework is optimized to minimize the recurrence with a computational complexity that close to the pioneering work (Moon & Moser, 1965) whose complexity is (3 3 ) on an n-vertex general graph. Using the NHHA framework, we also solve the All Maximal Independent Sets listing (AMISL) problem, which can be seen as the subproblem of the MWIS problem. Moreover, based on the NHHA framework, we developed two merging methods to compose the exact MWIS algorithm with fast approximation MWIS algorithms for faster computational speed or improved accuracy. All eight algorithms for the MWIS problem, the exact MWIS algorithm, the AMISL algorithm, two approximation algorithms (GWMIN and GWMIN2 (Sakai et al., 2003)), and four composed algorithms, are applied and tested for solving the graph-based formulation of the PPS problem (Sun et al., preprint). Note that this is a preprint of the paper that is scheduled to submit to Applied Discrete Mathematics.
The remainder of the paper is organized as follows. Section 2 provides a comprehensive literature review on the MWIS problem and its applications in scheduling problems. Section 3 provides the necessary background and definitions of graph theory. Section 4 and Section 5 explain the NHHA framework in detail, and Appendix I illustrates the exact MWIS algorithm with a simple example. Section 6 discusses how to merge the proposed MWIS algorithm with approximation MWIS algorithms to reduce the complexity. Then, Section 7 presents the numerical results to assess the performance of the algorithms. Finally, a few concluding remarks are given in Section 8.

Literature Review
There has been extensive work in the literature proposing a variety of algorithms for solving the MWIS problem exactly or approximately. One brute-force algorithm for exactly solving the MWIS problem amounts to checking all Maximal Independent Sets (MIS) and picking one with the maximum total weight. It follows that the MWIS problem is converted to the All Maximal Independent Sets (AMIS) listing (AMISL) problem (or maximal cliques listing problem in the complement graph). A pioneering work (Moon & Moser, 1965) has shown that any n-vertex graph has at most 3 3 maximum cliques. Many algorithms are now known for the clique (or independent set) listing problem (Bron & Kerbosch, 1973 (Bron & Kerbosch, 1973), Bron-Kerbosch algorithm named after its inventors, has been reported as the most successful clique listing algorithm in practice (Eppstein et al., 2010).
Other than the costly non-polynomial algorithm for the optimum solution on general graphs, people naturally go to three types of solutions: (i) solutions for special cases, it is known to be solvable in polynomial time in many cases including perfect graphs (Grotschel et al., 1993), interval graphs (Grotschel et al., 1993), disk graphs (Matsui, 1998), claw-free graphs (Minty, 1980), fork-free graphs (Alekseev, 2004), trees (Chen et al., 1988), sparse random graphs (Karp & Sipser, 1981;Czygrinow & Hanckowiak, 2006), circle graphs (Valiente, 2003), and growth-bounded graphs (Gfeller & Vicari, 2007). The MWIS problem has been found to be solvable in strongly polynomial time only on perfect graphs and their complements, on t-perfect graphs, and on claw-free graphs (Schrijver, 2003). (ii) approximation algorithms, there has been extensive work on approximating the MWIS (Halldorsson, 2004). The approximation can be achieved by using a greedy strategy (Furer & Kasiviswanathan, 2007). Sakai et al. (Sakai et al., 2003) investigated the performance guarantee of greedy algorithms to solve the MWIS problem. And (iii) there has been extensive work in the literature proposing a variety of heuristics (Kako et al., 2005). These specialized or heuristics algorithms have been developed for computing the exact MWIS (Fomin et al., 2006;Babel, 1994;Ostergard, 2002;Tassiulas & Ephremides, 1992) for limited types of graphs or graphs in general with certain tradeoffs.
The Graph Coloring Problem (GCP), MWIS, and AMISL problems, as well as their extensions, have been proposed to cope with different scheduling environments. The GCP consists of assigning a single color (integer) to each vertex of an undirected graph, such that no two adjacent vertices share the same color, intending to minimize the number of colors (Tucker, 2012). The MWIS problem is a special case of the GCP, when each node is associated with a weight factor with an optimization objective of finding the set maximizing the total weight for each coloring terms of finding the optimum set of nodes for each color. With interests focusing on scheduling problems, we summarize the four typical scheduling problem formulations with the GCP and its variations. Although these formulations are not fitting in the resource-constrained PPS problem considered in our work (Sun et al., preprint), but they are inspiring for us to develop our graph-based formulation.
(1) The Class/Exam Scheduling Problem The class scheduling problem, also named as the timetabling problem, can be stated as follows: schedule a set of classes in a number of time slots such that no professor or student is required at the same time. Constraints can be mapped onto GCP as follows. Let each class be represented by a node. Attach two nodes by an edge if and only if there is a reason that the classes they represent may not be offered at the same time. Initially, there are two such reasons for nodes to be linked: either they are taught by the same instructor, or they are required by the same set of students. Upon adding in the links, color the graph. Each color represents a time slot available on a given timetable, so every node with the same color is offered at the same time. Similar applications of this problem can be the scheduling of classes and exams in a university, the scheduling of flights for an airline, and the scheduling of computing tasks to be run on a multiprocessor machine (Dandashi & Al-Mouhamed, 2010;Miner et al., 1995).
(2) The Interval Graph Scheduling An interval graph is the intersection graph of a set of intervals of a real line, that is, a graph whose nodes correspond to intervals such that two nodes connected by an edge are associated with intersecting intervals, as shown in Figure 1 (Gardi, 2009). The intervals are representing the tasks, and the edges are indicating the incompatible tasks. The graph is then colored to find the mutual exclusion tasks that can be processed by the same resources. The interval graph scheduling and many variants of this problem have been extensively studied due to its numerous applications (Krarup & De Werra, 1982;Blazewicz et al., 2001;Zais & Laguna, 2016). In a wireless network, two wireless nodes that transmit at the same resource (frequency), interfere with each other if they are located close-by. The scheduling problem is to decide which nodes should transmit at the given resource so that there is no interference, and nodes with longer queue length are given priority. If each node is given a weight equal to the queue length, it is optimum to schedule the set of nodes with the highest total weight. If a conflicting weighted graph is made, with an edge between each pair of interfering nodes, the scheduling problem is exactly the MWIS problem. This type of scheduling problem is mostly found in wireless communication applications (Tassiulas & Ephremides, 1992  The graph multi-coloring problem is an extension of the GCP. In this case, a node coloring corresponds to a sequence of colors (from the smallest to the largest). A node stands for a task, and an edge indicates that two tasks represented by the two end nodes of the edge are incompatible. Each color is a time slot, and each node must be assigned with a number of colors as defined by the processing time of the task. The objective is to minimize the number of used colors. Thevenin et al. applied this formulation in a flow production environment (Thevenin et al., 2018). The graph multi-coloring problem formulation is the closest formulation comparable to our PPS problem. Still, it can only be applied in restricted conditions, such as each job requires the resources continuously and no subtasks of each job.

Definitions and Notations
Let = ( , ) be a simple undirected graph with vertex set = {1, … , }, and a set of edges . We denote by | | the cardinality of set , so that the edge number of is | | and the node number of is | |. Let ∈ , the degree (valence) of is the number of edges with as an endpoint. We denote the degree of by ( ). Let ( ) denote the set of neighbors of vertex and In the graph , let ⊂ be any subset of vertices of . Then, the induced subgraph ( ) is the graph whose vertex set is and whose edge set consists of all of the edges in that have both endpoints in (Diestel, 2006). For a vertex ∈ , let the complementary induced subgraph _ ( ) refers to the subgraph induced by all the node in except node , and the complementary neighbor induced subgraph _ _ ( ) refers to the subgraph induced by the non-neighbors of , and is not in _ _ ( ).
In the graph , assume there is a sequence of vertices and edges 0 , 1 , 1 , 2 ,…, , , where, for all = 1, … , , −1 and are the endpoints of is called a walk ( 0 , -walk) in G from 0 to . A walk in which all edges are distinct is called a trail ( 0 , -trail) and a walk in which all vertices are edges are distinct is called a path ( 0 , -path). The length of this walk, trail, or path is . The length of the shortest walk, trail, or path joining the vertex to the vertex is called the distance from to .
A connected, acyclic (no circuits) graph is called a tree. The components of an arbitrary acyclic graph are trees, and an acyclic graph is called a forest.
In the graph , a subset ⊆ is called an independent set (stable set, vertex packing) if the edge set of the subgraph induced by is empty. An independent set is maximal (maximal independent set) if it is not a subset of any largersize independent set, and maximum

The MWIS Algorithm Framework
The proposed NHHA framework has two phases following a divide and conquer structure: it starts by (a) removing nodes to get the induced subgraphs that are simple enough for finding the MWIS; and then by (b) iteratively adding nodes back one at a time, compare and merge to get the output. The first phase recursively partitions the graph into complementary induced subgraphs by removing nodes (and the adjunct edges) one at a time based on node removal heuristics. When induced subgraphs satisfy the desired patterns, these induced subgraphs become simple enough to be solved for MWIS with one comparison. A Preliminary Set (AMISL Preliminary Sets for the AMISL case) is found based on this complementary induced subgraph. The second phase of the algorithm adds back the nodes (and the adjunct edges) removed in the reversed sequence. At each adding, a Compare Set (AMISL sets for the AMISL case) is found to compare with the Preliminary Set (AMISL Preliminary Sets for the AMISL case). For the MWIS problem, the MWIS output set is the set with larger total weights among the Preliminary Set and the Compare Set of the current graph in the node adding process. For the AMISL problem, the AMISL output sets are the union of AMISL Compare Sets and AMISL Preliminary Sets for the graph with the adding node. The algorithm stops when all nodes (and the adjunct edges) are added back to the graph. With this brief understanding of the proposed approach, we are going into the details in the following sections.

Phase I: Dividing
Three types of unit graph structures (shown in Figure 2 No edges between these nodes Isolated Node A pair of two connected nodes The diameter is <= 2 edges Theorem 1 and Corollary 1 show that we are able to find the MWIS and AMIS of an induced subgraph after partitioning it into a specific structure. In order to partition the graph to get an induced subgraph as Γ described in Theorem 1, we need to proceed in two steps: (a) break all the cycles in the graph, and (b) break the paths which are longer than 2 edges. In both steps, we need to remove the nodes (and the adjunct edges) which satisfying specific rules. We denote such a qualified node as a removed node.
Step 1: Break all cycles First, we need to find a cycle basis of the given graph = ( , ). For each node ∈ in , count the number of basic (fundamental) cycles it belongs to, we denote the count for node as ( ). Then, we remove a node ∈ to get the complementary induced subgraph _ ( ), where ( ) is the maximum among all the ( ). This process iterates until no cycle left in the induced subgraph. This induced subgraph left is either a tree or a forest, since all the cycles are broken by removing the node (and adjunct edges) belongs to the most cycles.

Proof of Theorem 1:
(i) For the MWIS problem, the MWIS can be found by one comparison in a CUS, because there are only two maximal independent sets in all the three types of CUSs. Since Γ consists of multiple CUSs, and there are no edges between these CUSs, the MWIS of each CUS does not have a conflict with the MWIS of another CUS in Γ. Because the MWIS of each CUS in Γ is the independent set with the possible maximum total weight, and MWISs of CUSs has no conflict with each other. We can get the union of MWISs of CUSs in Γ as the MWIS of Γ. ∎

(ii)
For the AMISL problem, the AMIS can be found by dividing a CUS into two independent node set. Since Γ consists of multiple CUSs, and there are no edges between these CUSs, the AMIS of each CUS does not have confliction with any node of another CUS in Γ.
Because the AMISs of different CUSs in Γ has no confliction, get the union of the sets by choosing one set from the AMIS of each CUS and find all combinations without repeating of such unions. The union of each combination is one maximal independent set in the AMIS of Γ. ∎

Theorem 1: For Base Cases in Recurrence
Given a graph Γ that consists of different CUSs, 1 , 2 , …, , …, , ∈ {1,2, … , }, and no edge between these CUSs: For the MWIS problem, the S(CUS i ) can be found by one comparison in a . The CUS with an isolated node can be considered as compared with an empty node set. For the Γ that consists of multiple CUSs, the S(Γ) is the union of the MWIS of each CUS in Γ, or formally, For the AMISL problem, the ( ) can be found by dividing the graph into two independent node sets in a . The CUS with an isolated node can be considered as dividing the graph into two node sets (one of the two sets can be an empty set, ). For the Γ that consists of multiple CUSs, each , ∈ {1,2, … , } , in Γ has its ( ). The S(Γ) of graph Γ is all the combinations of the MISs of all the CUSs, note that only picking one of the MISs from each CUS in one combination. For the S(Γ) of graph Γ, ∈ {1, 2, … , }, formally, A basis for cycles of an undirected graph (Cycle Basis) is a minimal collection (a set of fundamental cycles) of cycles such that any cycle in the graph can be written as a sum of cycles in the Cycle Basis set (Diestel, 2012). Here summation of cycles is defined as "exclusive or" of the edges. The algorithm for finding a cycle basis is adapted from algorithm CACM 491, originally developed by K. Paton. For details on the algorithm and the production of the basic cycles, Paton's original paper (Paton, 1969) should be consulted. Paton also discusses two other algorithms for basic cycle generation and contains performance statistics in the paper referred to. The adopted basic (fundamental) cycles algorithm can be depicted as in Algorithm 1 (Paton, 1969).
Step 2: Break the paths which are longer than 2 edges to reduce the diameter of the components of the induced acyclic subgraph from step 1 If any of the connected components of the induced subgraph from step 1 has a diameter that is no less than 3 edges, remove the node in the middle of the longest path in that connected component of the graph. We name this node as the Middle Node of the path. For an odd path, the Middle Node is the midpoint of the path; for an even path, the Middle Node is one of the two nodes in the middle of the path. Algorithms 2 are adopted for checking the diameter, and Algorithms 3 is implemented for finding the Middle Node, respectively.
The diameter is the maximum eccentricity. The eccentricity of a node is the maximum distance from to all other nodes in . If is disconnected, the eccentricity of a node is infinite. A diameter algorithm adapted based on the Proof of Corollary 1: In Corollary 1, the CUS in Γ in Theorem 1 is now a general graph. In other words, the connected components in Γ is a general graph. Similar to the proof of Theorem 1, because the MWISs or AMISs of these connected components in has no conflict with nodes in a different connected component of , so that Corollary 1 holds which means that Theorem 1 also holds when CUS is a general graph. ∎ Corollary 1: The below statements in Theorem 1, "For the Γ that consists of multiple CUSs, For the MWIS problem, the S(Γ) is the union of the MWIS of each CUS in Γ, or formally, For the AMISL problem, the S(Γ) of graph Γ is all the combinations of the MISs of all the CUSs, note that only picking one of the MISs from each CUS in one combination. For the S(Γ) of graph Γ, ∈ {1, 2, … , }, formally, applied here for computing the diameters in step 2. For each connected component of , we utilize a function "single_source_shortest_path_length" from the python module "networkx" to compute the shortest path lengths from each node to all reachable nodes. The maximum value of the lengths found is the diameter of the connected component of . We mark this algorithm as Algorithm 2, the diameter algorithm.
Algorithm 1: The Basic Cycles Algorithm (Paton, 1969) The diameter is the maximum eccentricity. The eccentricity of a node is the maximum distance from to all other nodes in . If is disconnected, the eccentricity of a node is infinite. A diameter algorithm adapted based on the work by F. W. Takes applied here for computing the diameters in step 2. For each connected component of , we utilize a function "single_source_shortest_path_length" from the python module "networkx" to compute the shortest path lengths from each node to all reachable nodes. The maximum value of the lengths found is the diameter of the connected component of . We mark this algorithm as Algorithm 2, the diameter algorithm.
The Algorithm 3: the middle node algorithm is developed in order to find the middle point in a connected component of the induced acyclic subgraph. Since the input graph for finding the middle node is either a tree or a forest, we iteratively remove the nodes (and the adjunct edges) whose degrees satisfy ( ) = 1 or ( ) = 0. The last one node removed is the middle node, if the path is odd. One of the last two nodes removed is one of the two middle nodes, if the path is even. This middle node algorithm is implemented as below.
After the two steps of the node removal process, the induce subgraph satisfies the conditions as described in Theorem 1. We name the node ∈ removed from as a removed node. The complementary induced subgraph _ ( ) is called the induced subgraph at level node " ." All the removed nodes and the associated components are stored in a dictionary named Subgraphs Dictionary (SD) with removed nodes as keys and the associated components as values for recording this process. b. If W is not in the tree, add { , } to the tree, W to STACK, and repeat step 3.

Algorithm 3: The Middle Node Algorithm
The number of removed nodes determines the number of iterations in both node removal and node adding processes so that we want to reduce the number of removed nodes to the greatest extend. By using the Algorithm 1, the basic cycles algorithm, we can break the cycles as many as possible at each removal so that we can reduce the graph to a tree with a minimum number of nodes removed. And by removing the middle node of the trees using the Algorithm 2, the diameter algorithm and Algorithm 3, the middle node algorithm, the diameter of the remaining trees are minimized, which is also minimizing the number of the node removed.

Phase II: Adding Nodes and Conquering
We consider a collection of problems that involve finding a feasible subset of the input of maximum weight. The input contains a collection of distinguished elements, each carrying an associated nonnegative rational weight. Each set of distinguished elements uniquely induces a candidate for a solution, which we assume is efficiently computable from the set. The weight of a solution is the sum of the weights of the distinguished elements in the solution.
Halldorsson defines such a partitioning structure as the hereditary property (Halldorsson, 2000). Let's take an example to explain Theorem 2. Given a weighted graph 3 as Figure 3, the nodes, edges, node indexes, and weights associated is shown in Figure 3. Assuming node '3' is the removed node, according to Theorem 2, the Compare Set at level node '3' is the node set {'0', '3', '6'} circled in red in Figure 3, and the Preliminary Set at level node '3' is the node set {'0', '2', '5', '6'} circled in red in The input graph, a tree or forest, is finite, undirected, and without loops or multiple edges. This input graph has at least ONE connected component whose diameter is greater than 2 edges.

Step 1:
Get a dictionary of the degrees of nodes in the input graph, namely "node_degree_dict", using the node name as keys and the degree value as values.
Step 2: Find the keys which have values as 0 or 1, remove these nodes from the input graph to get the updated induced subgraph.
Step 3: a. If the number of nodes in the updated induced subgraph is ZERO, the middle node is a node in the input graph (from step 1). Return this middle node.
b. If the number of nodes in the updated induced subgraph is not ZERO, clean the dictionary "node_degree_dict" and update the input graph with the updated induced subgraph. Then, start from step 1.
Proof of Theorem 2: by contradiction (Since the MWIS and AMISL algorithms follow the same structure, we only prove the MWIS case here.) As the conditions described in Theorem 2, assuming all three statements always hold: There exists an Assumption Set in . The Assumption Set is a maximal independent set that has a total weight greater than that of either the Preliminary Set or the Compare Set.
In the same graph , since the Assumption Set, a maximal independent set in , has a total weight greater than the total weight of the Compare set, and the Compare Set has the maximum possible total weight of the maximal independent set has node as one element, the Assumption Set cannot contain node as an element. Because the Preliminary Set has the maximum possible total weight of the maximal independent set in the complementary induced subgraph _ ( ), so that the maximum possible total weight of a maximal independent set without node as an element is equal to the total weight of the Preliminary Set. Since the Assumption Set cannot contain node as an element, then it must be a maximal independent set in the complementary induced subgraph _ ( ) and its total weight is no greater than the total weight of the Preliminary Set. It is a Contradiction with statement 3, which implies that such an Assumption Set does not exist. ∎    In order to further understand Theorem 2, suppose we decide to place a node into a given maximum weighted independent set. It then suffices to search only in the non-neighborhood of , _ _ ( ), for the remaining nodes in the set. This suggests a natural heuristic, the greedy method. We can specify its result formally as, This rapid accumulation of an independent set by recursively looking at non-neighborhoods is attractive. remains disconcerting to completely ignore the neighborhoods of the pivot nodes, which may contain much larger weighted independent sets. Indeed, if we make a bad choice of a pivot node, we may be left with a minuscule set of independent vertices where there were plenty; thus, Greedy performs poorly in the worst case.
We are led to another rule for searching for an independent set. As before, choose a vertex and search in the nonneighborhood of that node. But this time also searches in the neighborhood of the pivot node, which makes the search area as _ ( ), and use whichever result has a heavier total weight. More formally, The discussions above are resulting in Algorithm 4, MWIS algorithm structure (MWIS_AS), as below: Algorithm 4: MWIS Algorithm Structure AMISL algorithm follows the same structure, but we need to define a particular function called the Special Union.
Assuming 1 and 2 are two sets of sets, the Special Union, _ ∪ ( 1 , 2 ), which is a set, which is the union of all the sets in 1 and 2 , and no set in _ ∪ ( 1 , 2 ) is a subset of another set. This is resulting in Algorithm 5, AMISL algorithm structure, (AMISL_AS) as below: Algorithm 5: AMISL Algorithm Structure

Construction of the Algorithms
From Theorem 1, we illustrate that the base cases for the divide and conquer algorithm structure. The base cases are constructed by removing nodes and the adjacent edges. We iteratively remove one node at a time by maximizing the number of cycles that the node belongs to in a cycle basis of the input graph or the current induced subgraph.
Subgraphs Dictionary (SD) is used to record this procedure. In SD, each node removed is the key and node sets of the connected components in the induced subgraphs as values of the keys, until the induced subgraphs satisfy the Theorem 1 conditions. The node adding procedures that are illustrated in Figure 5, is based on Algorithm 4 and Algorithm 5. Assume there are removed nodes for computing the MWIS or AMIS of graph , the CSS and the PSS denote the Compare Set Subgraph and the Preliminary Set Subgraph, respectively. The MWIS algorithm or the AMISL algorithm needs to be executed on the CSS at level node , ∈ {1,2, … , , … , }, with removed nodes to find the MWIS or the AMIS, respectively.
For the MWIS case, according to Theorem 2 and Algorithm 4, we can get the desired MWIS set by comparing the Compare Set and the Preliminary Set at each level of the removed node. The MWIS found at each level of the removed node is recorded in the subgraph MWIS dictionary (SMWISD): the current induced subgraph (the PSS plus the removed node at the level) is the key, and the MWIS found is the value. The SMWISD is used for searching the MWIS of the connected components, which is part of the Preliminary Set at the level.
For the AMISL case, according to Theorem 2 and Algorithm 5, we can get AMIS by comparing and merging the AMISL Compare Sets and the AMISL Preliminary Sets at each level of the removed node. The AMIS found at each level of the removed node is recorded in the subgraph AMIS dictionary (SAMISD): the current induced subgraph (the PSS plus the removed node at the level) is the key, and the AMIS found is the value. The SAMISD is used for searching the AMIS of the connected components, which is part of the AMISL Preliminary Set at the level.
Together with Corollary 1, recurrence can be set up by adding the removed nodes back to the graph in the reverse order from the CUSs till getting the whole original graph. At each level of the removed node, the Preliminary Set and the AMISL Preliminary Set can be found as follows. For the MWIS case, we can get the Preliminary Set by aggregating the MWIS of each connected component of the current induced subgraph (without the removed node) according to the key-value pair in the SD. These MWISs are found by searching the SMWISD or computed according to Theorem 1. For the AMISL case, following the Theorem 1 and Corollary 1, we can merge the AMISs of all connected components of the current induced subgraph according to the key-value pair in the SD to get the AMISL Preliminary Set. These AMISs are found by searching the SAMISD or computed according to Theorem 1.
While adding nodes back to get the Compare Set and the AMISL Compare Set, we follow the node adding heuristics for finding the Compare Set as below: 1. Get CSS, which is the induced subgraph by removing all neighbors of the removed node added; the removed node is included in the CSS. For better describing the algorithms we proposed in this section, we provide a walk-through of Algorithm A1 as well as all the terms in detail with a simple example in Appendix I. In the following section, we discuss the complexity of the proposed algorithms, and the means to improve the computational speed. to exponential complexity.

Algorithm A1 MWIS: A hybrid heuristic algorithm for MWIS problem
Let us take the graph 6 in Figure 6 as an example to illustrate the complexity of the proposed algorithm structure, to simplify the problem, assuming weights of the vertices are the same as the vertex index.  Figure 7, it requires to execute Algorithm A1 to get the Compare Set at level node '1', which is {'1', '3', '5', '7'}. Such a linear recurrence leads to exponential complexity (Erickson, 2018). Note that, since Algorithm A2 follows a similar structure, but it is returning the AMIS at each step, the Algorithm A1 and A2 have the same complexity with the same input graph.

Merging Approximation Algorithms with the Proposed MWIS Algorithm
Since calculations for the Compare Set slow down the execution of the proposed Algorithm A1 for the MWIS problem, we can speed up the computation by replacing Algorithm A1 on computing MWIS for Compare Sets with 1 fast MWIS approximation algorithms. To illustrate this idea, we utilize two low complexity approximation algorithms to compute the Compare Set. Sakai et al. (Sakai et al., 2003) discuss greedy algorithms for the MWIS problem (GMIN-type algorithms). Two algorithms are the GMWIN and GMWIN2, which select a node of maximizing a node selection function, then remove it and its neighbors from the graph, and iterates this process on the remaining graph (induced subgraph) until no vertex remains. The set of selected nodes is the desired independent set. Let = ( , , ) be a simple undirected graph with node set , a set of edges , and is a set of weight factors associated with element in . Let , ∈ , for each ∈ (0 ≤ ≤ | | − 1), the two node-selecting functions are: (1) GWMIN: maximizing ( )+1 (2) GWMIN2: maximizing ∑ ∈ + ( ) Where, is the remaining graph. We refer to the two simple greedy algorithms as Algorithm A3 GMWIN and Algorithm A6 GMWIN2, which are using the GWMIN and GWMIN2 node selection functions, respectively.
Let us consider the following framework of GMIN-type algorithms.
Algorithm A3 and A6. The Algorithm GWMIN and Algorithm GMWIN2 As approximation algorithms, we are interested to know the lower bound of their accuracy. Sakai et al. (Sakai et al., 2003) proved Theorem 3 and Theorem 4 as the lower bounds of the accuracy of the two algorithms. With the approximation algorithms ready, we employ two different methods to merge an approximation algorithm with the proposed MWIS algorithm structure. Shown as Figure 8  According to Theorem 2, both composed MWIS approximation algorithms generate results no worse than the lower bound of the original approximation algorithms. In Algorithm A5 and Algorithm A8, the approximation algorithms are used on the _ _ ( ), compare to Algorithm A4 and Algorithm A7, which are the approximation algorithms using the Algorithm A3 GWMIN and Algorithm A6 GWMIN2 on the whole subgraph , respectively. By definition, the complementary neighbor induced subgraph, _ _ ( ), is smaller than the whole induced subgraph , because the node and its neighbors are not included in _ _ ( ). Theoretically, the Algorithm A5 and Algorithm A8 should have better accuracy than the Algorithm A4 and Algorithm A7, respectively. And the Algorithm A5 and Algorithm A8 should have a faster computational speed than the Algorithm A4 and Algorithm A7, respectively. The computational experiments in the following section also justify these conjectures.

Computational Experiment on MWIS Algorithms
According to the proposed approach for the PPS problem discussed in our work (Sun et al., preprint), conflicting weighted graphs (general graphs) are created to test the scalability and accuracy of the algorithms in solving the PPS problem. Forty-three conflicting weighted graphs are created based on randomized PPS problems, from 5 nodes and 6 edges to 161 nodes and 4718 edges. The scalability analysis shows how the algorithms behave on the test graphs. It can be evaluated based on the computation time versus the different sizes of the test graphs, which measures by the node numbers and edge numbers of the different conflicting graphs. The accuracy refers to how likely the proposed approach can get to the optimum solution, MWIS. It can be measured by the average and the maximum error rate of all the test instances. The details of the results are shown in Appendix II. Note that all computational experiments in this work are performed on a virtual server at Syracuse University. The CPU is Intel Xeon E5-2699 with a fixed maximum speed at 2.3 GHz, and the memory is 32 GB. All the implementations mentioned in this work are in single threading.
Before we start the discussion on the scalability and accuracy, let us formally summarize all the MWIS algorithms to be tested as below: • Algorithm A1 MWIS: the proposed exact MWIS algorithm.
• Algorithm A4 MWIS_CS_GWMIN: it is an algorithm composed of Algorithm A1 and Algorithm A3. This algorithm computes Compare Sets based on the whole induced subgraph at each level using Algorithm A3 GWMIN.
• Algorithm A5 MWIS_SubCS_GWMIN: it is an algorithm composed of Algorithm A1 and Algorithm A3.
This algorithm computes Compare Sets based on the induced CSSs, excluding the current removed node, using Algorithm A3 GWMIN.
• Algorithm A7 MWIS_CS_GWMIN2: it is an algorithm composed of Algorithm A1 and Algorithm A6.
This algorithm computes Compare Sets based on the whole induced subgraph at each level using Algorithm A6 GWMIN2.
• Algorithm A8 MWIS_SubCS_GWMIN2: it is an algorithm composed of Algorithm A1 and Algorithm A6.
This algorithm computes Compare Sets based on the induced CSSs, excluding the current removed node, using Algorithm A6 GWMIN2.
The computation time of Algorithms A1 and A2 changing with node number and edge number is shown in Figure 9 and Figure 10, respectively. Algorithms A1 and A2, as discussed in Section 6, can be exponentially slow on certain graphs. The computation time can be hours when there are about 140 nodes and 4000 edges. Although the worst case of the two algorithms can be exponentially slow, the application scenarios of the PPS problem considered here may not always be the worst case. Algorithms A1 and A2 match higher-order (order 4 or higher) polynomial trendlines, but they are faster than the exponential trendline. Figure 11 and Figure 12 show how the computation time changing with node number and edge number on Algorithms A3 and A6, respectively. Algorithms A3 and A6 are the approximation algorithms from literature, and they are the fastest among the 8 algorithms. The computation time is less than one second on the test graphs. Algorithms A3 and A6 are in lower-order polynomial complexity on the test graphs. The difference in the complexity of the two algorithms is due to the different greedy functions of the two algorithms. Figure 13 and Figure 14 show how the computation time is changing with node number and edge number on Algorithms A4, A5, A7, and A8, respectively. Algorithms A4, A5, A7, and A8 are the composed algorithms based on Algorithm A1 structure with MWIS approximation algorithms. They are slower than the approximation algorithms utilized, but they are still much faster than the exact MWIS algorithms. The computation time is less than 45 seconds on the test graphs. Algorithm A5 and A8 are faster than Algorithm A4 and A7, respectively. This result of computational experiments matches the conjectures in Section 6 that is the Compare Set computation is based on a smaller subgraph. And the Algorithm A7 and A8 are faster than Algorithm A4 and A5, respectively. This result also justifies that Algorithms A6 is faster than Algorithms A3 when the graph is relatively small (less than 3500 edges and less than 135 nodes.)  Figure 15. The Average and Maximum Error Rate for All Algorithms Figure 15 shows the average and maximum error rate of the algorithms. Assume is the total weight of the optimum solution of the MWIS problem on the test graph, and is the total weight of the MWIS set found by the algorithm. The weight error rate is calculated using the function below.
Note that the Algorithms A1 and A2 shall return optimum solutions with the same total weight. And the test results justify this conjecture. This value is used as the baseline, for the weight error rate calculation.
The general accuracy of the algorithms can be listed below from the best to the worst: As listed above, merging the approximation algorithms with Algorithm A1 structure can improve the accuracy. And the test results justify the statement that applying the approximation algorithm on smaller subgraphs can achieve better accuracy, e.g., Algorithm A5 and A8 have better accuracy than the Algorithm A4 and A7, respectively.
8 Conclusions Figure 16. Performance of the MWIS Algorithms This paper considers the MWIS problem on general graphs and develops the NHHA framework for solving the MWIS problem. In order to reduce the computational complexity, utility functions are developed or adopted; they are Algorithm 1: the basic cycles algorithm (Paton, 1969)

A1 A2
with two approximation MWIS algorithms from literature, GWMIN and GWMIN2 (Sakai et al., 2003). Composing approximation algorithms with the NHHA framework is an effective way to improve the accuracy of approximation MWIS algorithms or the computational speed of Algorithm A1 MWIS. Composed algorithms, which are using the merging Method#2, are faster and better accuracy.
All eight algorithms for the MWIS problem, the exact MWIS algorithm, the AMISL algorithm, two approximation algorithms, and four composed algorithms, are applied and tested for solving the graph-based formulation of the resource-constrained PPS problem (Sun et al., preprint). The overall performance of the algorithms is illustrated in Figure 16. The general accuracy of the best five algorithms can be listed below from the best to the worst: Algorithm A1 MWIS; Algorithm A2 AMISL (same as Algorithm MWIS); Algorithm A5 MWIS_SubCS_GWMIN; Algorithm A8 MWIS_SubCS_GWMIN2; Algorithm A4 MWIS_CS_GWMIN. Note that all these algorithms considered satisfactory have the average error of less than 1% and the maximum error of less than 13% (The first four algorithms have the maximum error less than 9%) on all test instances.
In future work, it is of interest to investigate how to closely integrate the NHHA framework with application scenarios, in this case, the PPS problem. More specifically, utilizing both analytical and data-driven methods, how to utilize analytical and analytics methods for identifying features of the graph-based formulation of the PPS problem, how to fine-tune and closely-integrate the strategies of removed node selections, specialized approximation algorithms, and weight factor arrangements can efficiently improve MWIS algorithms with applications. Further on, we wish to explore the real-world applications with the NHHA framework and our graph-based problem formulation.

Appendix I: An Example for Algorithm A1 on a Simple Graph
The exact MWIS algorithms described in Section 5 is complex. In Appendix I, we walk through Algorithm A1 in detail with a simple example in Figure A1. A simple weighted graph shown in Figure A1 is given, with the nodes, edges, and weights shown as Figure A1. Note that Algorithm A2 follows a similar process, but it is returning the AMIS at each step.
All the step indexes used below are from Algorithm A1.
In step (1.1), we need to perform step (1.1.1) to (1.1.5) to find and remove nodes and update the subgraphs dictionary (SD) accordingly: : {the : node sets of each } The SD is in the format that each node removed (removed node) is the key, and node sets of each connected component in the induced subgraphs are the value of the key. The node removal process iterates until the induced subgraphs satisfy the Theorem 1 conditions.