Independent sets in (P₄+P₄,triangle)-free graphs

DOI10.1007/S00373-021-02340-7zbMATH Open1479.05282arXiv2003.08649OpenAlexW3166205065MaRDI QIDQ2053685FDOQ2053685

Authors: Raffaele Mosca 

Publication date: 30 November 2021

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: 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 $calS$ 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 $calS$. These results seem to be harmonic with respect to other polynomial results for WIS on certain [subclasses of] $S_{i,j,k}$-free graphs and to other structure results on [subclasses of] Triangle-free graphs.

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

Recommendations

• Independent sets in \(\{\text{claw}, K_4 \}\)-free 4-regular graphs
• Finding independent sets in \(K_4\)-free 4-regular connected graphs
• Independent dominating sets in triangle-free graphs
• Degree multiplicities and independent sets in \(K_ 4\)-free graphs
• Independent sets in triangle-free cubic planar graphs
• Independent sets in some classes of \(S_{i,j,k}\)-free graphs
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Counting independent sets in triangle-free graphs
• Finding Independent Sets in Triangle-Free Graphs
• scientific article; zbMATH DE number 5761816

zbMATH Keywords

triangle-free graphspolynomial algorithmsmaximum independent set problem\(S_{i, j, k}\)-free graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Cites Work

• Network flows. Theory, algorithms, and applications.
• Title not available (Why is that?)
• Geometric algorithms and combinatorial optimization
• Graph Classes: A Survey
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Title not available (Why is that?)
• A New Algorithm for Generating All the Maximal Independent Sets
• Independent set in \(P_5\)-free graphs in polynomial time
• Maximum regular induced subgraphs in \(2P_3\)-free graphs
• Some simplified NP-complete graph problems
• On maximal independent sets of vertices in claw-free graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Title not available (Why is that?)
• Paw-free graphs
• On diameters and radii of bridged graphs
• A Linear Recognition Algorithm for Cographs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Independence and irredundance in \(k\)-regular graphs
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Title not available (Why is that?)
• Computing independent sets in graphs with large girth
• Title not available (Why is that?)
• An upper bound on the number of cliques in a graph
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
• From matchings to independent sets
• On the closure of triangle-free graphs under substitution
• A note on triangle-free and bipartite graphs
• Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
• Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
• Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time
• An \(\mathcal{O} (n^2 \log{n})\) algorithm for the weighted stable set problem in claw-free graphs

Cited In (3)

• Independent sets in some classes of \(S_{i,j,k}\)-free graphs
• Maximum weight independent sets for (\(S_{1,2,4}\), triangle)-free graphs in polynomial time
• Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs

This page was built for publication: Independent sets in \((P_4+P_4\),triangle)-free graphs

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