One of graph optimization’s fundamental and most challenging problems is determining the maximum set of unconnected vertices in a graph, called the maximum independent set problem. This problem ...consists of finding the largest independent set in a graph, where an independent set is a set of vertices such that no two vertices are adjacent. This paper presents a new artificially generated algorithm for the maximum independent set problem. The new algorithm is generated by the automatic generation of algorithms, a technique that allows the construction of new hybrid algorithms, taking advantage of existing algorithms. Thus, the automatic generation of algorithms combines basic heuristics for the problem, a tabu search method selected from the literature, and an exact method that solves the problem’s mathematical formulation working for a limited computational time. With these components, the space of possible algorithms is traversed by employing genetic programming. Algorithms of small sizes are generated to study their structure and discover new algorithmic combinations. Then, we select the algorithm that finds solutions with the best computational performance among all the generated algorithms. This best algorithm is compared with three state-of-the-art algorithms for the problem, presenting the best computational performance for the 131 instances in the literature.
•Artificially generated algorithms for solving the maximum independent set problem.•Algorithms are trained with different groups of instances.•Algorithms generated combine basic heuristics, a tabu search, and an exact method.•An artificial algorithm outperforms all generated ones in computational performance.•The best generated algorithm outperforms the state-of-the-art algorithms.
The generalized independent set problem (GIS) is a generalization of the classical maximum independent set problem and has various practical applications, such as forest harvesting and image/video ...processing. In this work, we present highly effective exact and heuristic algorithms for the GIS. In the proposed exact algorithm, a new upper bound on the maximum net benefit of an independent set in a subgraph is derived using a Lagrangian relaxation of a linear integer programming formulation of the GIS problem. This bound is then employed in a combinatorial branch-and-bound (B&B) algorithm. To solve larger instances, we propose an adaptive local search procedure which jointly considers several neighborhoods and selects a neighborhood to explore in an adaptive manner at each iteration. Our proposed exact and heuristic algorithms are evaluated on a set of 216 GIS benchmark instances and compared with several state-of-the-art algorithms. Computational results indicate that our proposed algorithm competes favorably with the best existing approaches for the GIS. In particular, the exact algorithm is able to attain all known optimal solutions and to solve 26 more instances to optimality for the first time.
•We derive a new upper bound using a Lagrangian relaxation of the GIS problem.•We develop an effective exact algorithm based on the branch-and-bound framework for the GIS.•We propose an adaptive local search procedure jointly considering several neighborhoods.•The exact algorithm can solve 26 more instances to optimality for the first time.
The success of machine learning solutions for reasoning about discrete structures has brought attention to its adoption within combinatorial optimization algorithms. Such approaches generally rely on ...supervised learning by leveraging datasets of the combinatorial structures of interest drawn from some distribution of problem instances. Reinforcement learning has also been employed to find such structures. In this paper, we propose a different approach in that no data is required for training the neural networks that produce the solution. In this sense, what we present is not a machine learning solution, but rather one that is dependent on neural networks and where backpropagation is applied to a loss function defined by the structure of the neural network architecture as opposed to a training dataset. In particular, we reduce the popular combinatorial optimization problem of finding a maximum independent set to a neural network and employ a dataless training scheme to refine the parameters of the network such that those parameters yield the structure of interest. Additionally, we propose a universal graph reduction procedure to handle large-scale graphs. The reduction exploits community detection for graph partitioning and is applicable to any graph type and/or density. Experimental results on both real and synthetic graphs demonstrate that our proposed method performs on par or outperforms state-of-the-art learning-based methods in terms of the size of the found set without requiring any training data.
A graph G with n vertices is called an outerstring graph if it has an intersection representation with a set of n curves inside a disk such that one endpoint of every curve is attached to the ...boundary of the disk. Given an outerstring graph representation of G with s segments, a Maximum Independent Set (MIS) of G can be computed in O(s3) time (Keil et al. (2017) 22).
We examine the fine-grained complexity of the MIS problem on some well-known outerstring representations (e.g., line segments, L-shapes, etc.), where the strings are of constant size. We show that computing MIS on grounded segment and grounded square-L representations is at least as hard as computing MIS on circle graph representations. Note that no O(n2−δ)-time algorithm, δ>0, is known for computing MIS on circle graphs. For the grounded string representations, where the strings are y-monotone simple polygonal paths of constant length with segments at integral coordinates, we solve MIS in O(n2) time and show this to be the best possible under the Strong Exponential Time Hypothesis. For the intersection graph of nL-shapes in the plane, we give a (4⋅logOPT)-approximation algorithm for MIS (where OPT denotes the size of an optimal solution), improving the previously best-known (4⋅logn)-approximation algorithm of Biedl and Derka (WADS 2017).
The Maximum Weight Stable Set Problem (MWS) is a well-known NP-hard problem. A popular way to study MWS is to detect graph classes for which MWS can be solved in polynomial time. In this context some ...decomposition approaches have been introduced in the literature, in particular decomposition by homogeneous sets and decomposition by clique separators, which had several applications in the literature. Brandstädt and Hoàng (2007) 6 showed how to combine such two decomposition approaches and stated the following result: If the MWS problem can be solved in polynomial time for every subgraph of a graph G which has no homogeneous set and has no clique separators then so can the problem for G. This result, namely Corollary 9 of 6, was used in various papers.
Unfortunately, it was stated in a successive paper by Brandstädt and Giakoumakis (2015) 5 that “Actually, 6 does not give a proof for this, and it seems that Corollary 9 of 6 promises too much; later attempts for proving it failed, and thus, it is unproven and its use has to be avoided.”
This manuscript introduces a proof of Corollary 9 of 6. Furthermore a third decomposition approach, namely decomposition by anti-neighborhoods of vertices, is combined together with such two decomposition approaches. Then the various papers in which Corollary 9 of 6 was used would be fixed.
For a finite, simple, undirected graph G with a vertex weight function, the Maximum Weight Independent Set (MWIS) problem asks for an independent vertex set of G with maximum weight. MWIS is a ...well-known NP-hard problem of fundamental importance. For claw-free graphs, MWIS can be solved in polynomial time—in 1980, the first two such algorithms were independently found by Minty for MWIS and by Sbihi for the unweighted case. For a constant ℓ≥2, let ℓG denote the disjoint union of ℓ copies of G.
In this paper, using a dynamic programming approach (inspired by Farber’s result about MWIS for 2K2-free graphs), we show that for any fixed ℓ, MWIS can be solved in polynomial time for ℓclaw-free graphs. This solves the open cases for MWIS on (P3+claw)-free graphs and on (2K2+claw)-free graphs and extends known results for claw-free graphs, ℓK2-free graphs, (K2+claw)-free graphs, and ℓP3-free graphs.
The Maximum Weight Independent Set (MWIS) problem on finite undirected graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum weight sum. MWIS is one of the most ...investigated and most important algorithmic graph problems; it is well known to be NP-complete, and it remains NP-complete even under various strong restrictions such as for triangle-free graphs. Its complexity for Pk-free graphs, k≥7, is an open problem. In 7, it is shown that MWIS can be solved in polynomial time for (P7,triangle)-free graphs. This result is extended by Maffray and Pastor 22 showing that MWIS can be solved in polynomial time for (P7,bull)-free graphs. In the same paper, they also showed that MWIS can be solved in polynomial time for (S1,2,3,bull)-free graphs.
In this paper, using a similar approach as in 7, we show that MWIS can be solved in polynomial time for (S1,2,4,triangle)-free graphs which generalizes the result for (P7,triangle)-free graphs.
The maximum independent set problem is NP-hard and particularly difficult to solve in sparse graphs, which typically take exponential time to solve exactly using the best-known exact algorithms. In ...this paper, we present two new novel heuristic algorithms for computing large independent sets on huge sparse graphs, which are intractable in practice. First, we develop an advanced evolutionary algorithm that uses fast graph partitioning with local search algorithms to implement efficient combine operations that exchange whole blocks of given independent sets. Though the evolutionary algorithm itself is highly competitive with existing heuristic algorithms on large social networks, we further show that it can be effectively used as an oracle to guess vertices that are likely to be in large independent sets. We then show how to combine these guesses with kernelization techniques in a branch-and-reduce-like algorithm to compute high-quality independent sets quickly in huge complex networks. Our experiments against a recent (and fast) exact algorithm for large sparse graphs show that our technique always computes an optimal solution when the exact solution is known, and it further computes consistent results on even larger instances where the solution is unknown. Ultimately, we show that identifying and removing vertices likely to be in large independent sets opens up the reduction space—which not only speeds up the computation of large independent sets drastically, but also enables us to compute high-quality independent sets on much larger instances than previously reported in the literature.
This paper studies generalized variants of the MAXIMUM INDEPENDENT SET problem, called the Maximum Distance -d Independent Set problem (MaxDdIS for short). For an integer d≥2, a distance-d ...independent set of an unweighted graph G=(V, E) is a subset S⊆V of vertices such that for any pair of vertices u, v∈S, the number of edges in any path between u and v is at least d in G. Given an unweighted graph G, the goal of MaxDdIS is to find a maximum-cardinality distance-d independent set of G. In this paper, we analyze the (in)approximability of the problem on r-regular graphs (r≥3) and planar graphs, as follows: (1) For every fixed integers d≥3 and r≥3, MaxDdIS on r-regular graphs is APX-hard. (2) We design polynomial-time O(rd-1)-approximation and O(rd-2/d)-approximation algorithms for MaxDdIS on r-regular graphs. (3) We sharpen the above O(rd-2/d)-approximation algorithms when restricted to d=r=3, and give a polynomial-time 2-approximation algorithm for MaxD3IS on cubic graphs. (4) Finally, we show that MaxDdIS admits a polynomial-time approximation scheme (PTAS) for planar graphs.
PDF
