Computing well-covered vector spaces of graphs using modular decomposition

DOI10.1007/S40314-023-02502-8MaRDI QIDQ6184796zbMATH OpenOpenAlexFDO

Authors Martin Milanič, Nevena Pivač

Publication date 5 January 2024

Published in Computational and Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Gaussian eliminationmodular decompositioncographweighted well-covered graphfork-free graphwell-covered vector space

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Vector spaces, linear dependence, rank, lineability (15A03)

Abstract: A graph is well-covered if all its maximal independent sets have the same cardinality. This well studied concept was introduced by Plummer in 1970 and naturally generalizes to the weighted case. Given a graph $G$, a real-valued vertex weight function $w$ is said to be a well-covered weighting of $G$ if all its maximal independent sets are of the same weight. The set of all well-covered weightings of a graph $G$ forms a vector space over the field of real numbers, called the well-covered vector space of $G$. Since the problem of recognizing well-covered graphs is $mathsfco$-$mathsfNP$-complete, the problem of computing the well-covered vector space of a given graph is $mathsfco$-$mathsfNP$-hard. Levit and Tankus showed in 2015 that the problem admits a polynomial-time algorithm in the class of claw-free graph. In this paper, we give two general reductions for the problem, one based on anti-neighborhoods and one based on modular decomposition, combined with Gaussian elimination. Building on these results, we develop a polynomial-time algorithm for computing the well-covered vector space of a given fork-free graph, generalizing the result of Levit and Tankus. Our approach implies that well-covered fork-free graphs can be recognized in polynomial time and also generalizes some known results on cographs.

Recommendations

• Well-Covered Vector Spaces of Graphs
• A general algorithmic scheme for modular decompositions of hypergraphs and applications
• An Algorithm for the Modular Decomposition of Hypergraphs
• On well-covered, vertex decomposable and Cohen-Macaulay graphs
• Very well-covered graphs and their h-vectors
• On Module-Composed Graphs
• On graph decompositions modulo \(k\)
• Modular decomposition of graphs and the distance preserving property
• A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs
• From modular invariants to graphs: the modular splitting method

Cites work

• scientific article; zbMATH DE number 434906 (Why is no real title available?)
• scientific article; zbMATH DE number 3614795 (Why is no real title available?)
• scientific article; zbMATH DE number 1286748 (Why is no real title available?)
• A characterization of well covered graphs of girth 5 or greater
• A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
• A class of threshold and domishold graphs: Equistable and equidominating graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• A survey of the algorithmic aspects of modular decomposition
• Complement reducible graphs
• Complexity results for well‐covered graphs
• Counting weighted independent sets beyond the permanent
• Equistable graphs
• FPT algorithms to recognize well covered graphs
• Fast matrix rank algorithms and applications
• Graph Classes: A Survey
• Local Structure When All Maximal Independent Sets Have Equal Weight
• Modular decomposition and transitive orientation
• On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
• On the Levi graph of point-line configurations
• Recognizing Greedy Structures
• Recognizing well covered graphs of families with special \(P _{4}\)-components
• Reducibility among combinatorial problems
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Some covering concepts in graphs
• Stochastic graphs and strongly perfect graphs - a survey
• The structure of well-covered graphs and the complexity of their recognition problems
• The structure of well-covered graphs with no cycles of length 4
• The uniformity space of hypergraphs and its applications
• The well-covered dimension of products of graphs
• Very well covered graphs
• WELL-COVERED GRAPHS: A SURVEY
• Weighted well-covered claw-free graphs
• Well covered simplicial, chordal, and circular arc graphs
• Well-Covered Vector Spaces of Graphs
• Well-covered circulant graphs
• Well-covered claw-free graphs
• Well-covered graphs and extendability
• Well-covered graphs without cycles of lengths 4, 5 and 6

Cited in

(2)

• Generating subgraphs in chordal graphs
• Channel allocation revisited through 1-extendability of graphs

This page was built for publication: Computing well-covered vector spaces of graphs using modular decomposition

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