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

DOI10.1007/S00373-021-02340-7MaRDI QIDQ2053685zbMATH OpenOpenAlexFDO

Authors Raffaele Mosca

Publication date 30 November 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

\(S_{i, j, k}\)-free graphsmaximum independent set problempolynomial algorithmstriangle-free graphs

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(4)

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

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)