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.
•We add incompatibility constraints to the directed profitable rural postman problem.•We propose and compare two mathematical formulations for the problem.•We propose an effective matheuristic to ...solve the problem.•A new variant of the generalized independent set problem is introduced and a GRASP algorithm for its solution is proposed.
In this paper, we study a variant of the directed rural postman problem (RPP) where profits are associated with arcs to be served, and incompatibility constraints may exist between nodes and profitable arcs leaving them. If convenient, some of the incompatibilities can be removed provided that penalties are paid. The problem looks for a tour starting and ending at the depot that maximizes the difference between collected profits and total cost as sum of traveling costs and paid penalties, while satisfying remaining incompatibilities. The problem finds application in the domain of road transportation service, and in particular in the context of horizontal collaboration among carriers and shippers. We call this problem the directed profitable rural postman problem with incompatibility constraints. We propose two problem formulations and introduce a matheuristic procedure exploiting the presence of a variant of the generalized independent set problem (GISP) and of the directed rural postman problem (DRPP) as subproblems. Computational results show how the matheuristic is effective outperforming in many cases the result obtained in one hour computing time by a straightforward branch-and-cut approach implemented with IBM CPLEX 12.6.2 on instances with up to 500 nodes, 1535 arcs, 1132 profitable arcs, and 10,743 incompatibilities.
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. For a long time, its complexity was an open problem for Pk-free graphs, k≥5.
Recently, Lokshtanov et al. (2014) proved that MWIS can be solved in polynomial time for P5-free graphs, Lokshtanov et al. (2015) proved that MWIS can be solved in quasi-polynomial time for P6-free graphs, and Bacsó et al. (2016), and independently, Brause (2017) extended this to Pk-free graphs for every fixed k. Then very recently, Grzesik et al. (2017) showed that MWIS can be solved in polynomial time for P6-free graphs. It still remains an open problem for Pk-free graphs, k≥7.
In this paper, we show that MWIS can be solved in polynomial time for (P7,triangle)-free graphs. This extends the corresponding result for (P6,triangle)-free graphs and may provide some progress in the study of MWIS for P7-free graphs such as the recent result by Maffray and Pastor (2016) showing that MWIS can be solved in polynomial time for (P7,bull)-free graphs.
The Maximum Weight Independent Set Problem (WIS) is a well-known NP-hard problem. A popular way to study WIS is to detect graph classes for which WIS can be solved in polynomial time, with particular ...reference to hereditary graph classes, i.e., defined by a hereditary graph property or equivalently by forbidding one or more induced subgraphs. Given two graphs
G
and
H
,
G
+
H
denotes the disjoint union of
G
and
H
. This manuscript shows that (i) WIS can be solved for (
P
4
+
P
4
, Triangle)-free graphs in polynomial time, where a
P
4
is an induced path of four vertices and a Triangle is a cycle of three vertices, and that in particular it turns out that (ii) for every (
P
4
+
P
4
, Triangle)-free graph
G
there is a family
S
of subsets of
V
(
G
) inducing (complete) bipartite subgraphs of
G
, which contains polynomially many members and can be computed in polynomial time, such that every maximal independent set of
G
is contained in some member of
S
. These results seem to be harmonic with respect to other polynomial results for WIS on subclasses of certain
S
i
,
j
,
k
-free graphs and to other structure results on subclasses of Triangle-free graphs.
We consider scheduling in wireless networks and formulate it as a Maximum Weighted Independent Set (MWIS) problem on a "conflict" graph that captures interference among simultaneous transmissions. We ...propose a novel, low-complexity, and fully distributed algorithm that yields high-quality feasible solutions. Our proposed algorithm consists of two phases, each of which requires only local information and is based on message-passing. The first phase solves a relaxation of the MWIS problem using a gradient projection method. The relaxation we consider is tighter than the simple linear programming relaxation and incorporates constraints on all cliques in the graph. The second phase of the algorithm starts from the solution of the relaxation and constructs a feasible solution to the MWIS problem. We show that our algorithm always outputs an optimal solution to the MWIS problem for perfect graphs. Simulation results compare our policies against carrier sense multiple access (CSMA) and other alternatives and show excellent performance.
Maximum Independent Sets and Supervised Learning Montemanni, Roberto; Smith, Derek H.; Chou, Xiao-Chen
Journal of the Operations Research Society of China (Internet),
12/2023, Letnik:
11, Številka:
4
Journal Article
Recenzirano
The paper discusses an enhancement to a recently presented supervised learning algorithm to solve the Maximum Independent Set problem. In particular, it is shown that the algorithm can be improved by ...simplifying the task learnt by the neural network adopted, with measurable effects on the quality of the solutions provided on unseen instances. Empirical results are presented to validate the idea..
We consider boolean linear programming formulations of the independent set, the vertex and the edge dominating set problems and prove their polynomial-time solvability for classes of graphs with ...(augmented) constraint matrices having bounded minors in the absolute value.
We describe a binary (17,4,5) constant weight code with 444 codewords, thus improving the lower bound for A(17,4,5) from 441 to 444. The code was discovered by a computer search implementing a new ...stochastic local search algorithm for the maximum independent set problem. The algorithm suggested is based on Generic Scuba Search, which is a known hybrid local search method exploiting neutrality in search landscapes.
Graph decompositions play a crucial role in structural graph theory and in designing efficient graph algorithms. Among them, clique separator decomposition (a decomposition tree of the graph whose ...leaves have no clique separator (so-called atoms)) used by Tarjan for solving various optimization problems recently received much attention. In this note, we first derive the atomic structure of two subclasses of P5-free graphs, where P5 is a chordless path on five vertices. These results enable us to provide efficient solutions for the Maximum Weight Independent Set problem in these classes of graphs.
The Maximum Weight Independent Set Problem (WIS) is a well-known NP-hard problem. A popular way to study WIS is to detect graph classes for which WIS can be solved in polynomial time, with particular ...reference to hereditary graph classes (i.e., defined by a hereditary graph property), or equivalently to F-free graphs for a given graph family F (i.e., graphs which are F-free for all F∈F).
A tool to extend the results which show that for given hereditary graph classes the WIS problem can be solved in polynomial time is given by the following easy proposition: For any graph family F, if WIS can be solved for F-free graphs in polynomial time, then WIS can be solved for K1+F-free graphs (i.e., graphs which are K1+F-free for all F∈F) in polynomial time.
The main result of this paper is the following: A sufficient condition to extend the above proposition to K2+F-free graphs, and more generally to lK2+F-free graphs for any constant l (i.e., graphs which are lK2+F-free for all F∈F), is that F-free graphs are m-plausible for a constant m, i.e., that for any F-free graph G the family of those maximal independent sets I of G such that every vertex of G not in I has more than m neighbors in I can be computed in polynomial time. In this context a section is devoted to show that (for instance) chordal graphs are m-plausible for a constant m.
The proof of the main result is based on the idea/algorithm introduced by Farber to prove that every 2K2-free graph has O(n2) maximal independent sets (Farber, 1989), which directly leads to a polynomial time algorithm to solve WIS for 2K2-free graphs through a dynamic programming approach, and on some extensions of that idea/algorithm.
PDF
