Weighted independent sets in a subclass of P₆-free graphs

DOI10.1016/J.DISC.2015.12.008zbMATH Open1329.05140arXiv1504.05401OpenAlexW2963527469MaRDI QIDQ906493FDOQ906493

Authors: T. Karthick 

Publication date: 21 January 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for $P_6$-free graphs is unknown. In this note, we show that the MWIS problem can be solved in time $O(n^{3}m)$ for ($P_6$, banner)-free graphs by analyzing the structure of subclasses of these class of graphs. This extends the existing results for ($P_5$, banner)-free graphs, and ($P_6$, $C_4$)-free graphs. Here, $P_t$ denotes the chordless path on $t$ vertices, and a banner is the graph obtained from a chordless cycle on four vertices by adding a vertex that has exactly one neighbor on the cycle.

Full work available at URL: https://arxiv.org/abs/1504.05401

Recommendations

• Maximum weight independent sets in (\(P_6\), co-banner)-free graphs
• Weighted independent sets in classes of \(P_6\)-free graphs
• Maximum weight independent sets in classes related to claw-free graphs
• Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs

zbMATH Keywords

graph algorithmsindependent sets\(P_6\)-free graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Cites Work

• Title not available (Why is that?)
• Graph Classes: A Survey
• Decomposition by clique separators
• The ellipsoid method and its consequences in combinatorial optimization
• Modular decomposition and transitive orientation
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Independent set in \(P_5\)-free graphs in polynomial time
• On maximal independent sets of vertices in claw-free graphs
• The complexity of generalized clique packing
• Title not available (Why is that?)
• On diameters and radii of bridged graphs
• Stable sets in two subclasses of banner-free graphs
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• Vertex disjoint paths for dispatching in railways
• Weighted independent sets in classes of \(P_6\)-free graphs
• Maximum weight independent sets in classes related to claw-free graphs
• Data Mining with optimized two-dimensional association rules
• A Linear Recognition Algorithm for Cographs
• On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• Independence and efficient domination on \(P_6\)-free graphs
• Independent sets of maximum weight in apple-free graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Maximum weight independent sets in hole- and dart-free graphs
• The Maximum Independent Set Problem in Planar Graphs
• New sufficient conditions for \(\alpha\)-redundant vertices
• Weighted efficient domination in two subclasses of \(P_6\)-free graphs
• Some classes of perfectly orderable graphs
• On the stable set problem in special \(P_{5}\)-free graphs
• On independent vertex sets in subclasses of apple-free graphs
• Graphs without large apples and the maximum weight independent set problem
• Computing independent sets in graphs with large girth
• On the maximum independent set problem in subclasses of subcubic graphs
• The maximum independent set problem in subclasses of subcubic graphs
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• Stability in \(P_5\)- and banner-free graphs

Cited In (12)

• Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs
• The maximum weight stable set problem in (\(P_6\), bull)-free graphs
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
• Algorithm to find a maximum 2-packing set in a cactus
• Weighted independent sets in classes of \(P_6\)-free graphs
• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
• Structure of squares and efficient domination in graph classes
• Maximum weight independent sets in (\(P_6\), co-banner)-free graphs
• The exact weighted independent set problem in perfect graphs and related classes
• Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
• Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
• Independent Sets in Classes Related to Chair-Free Graphs

This page was built for publication: Weighted independent sets in a subclass of \(P_6\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q906493)