The complexity of dissociation set problems in graphs

DOI10.1016/j.dam.2011.04.023zbMath1223.68058OpenAlexW2131265210WikidataQ57633866 ScholiaQ57633866MaRDI QIDQ2275943

Yury L. Orlovich, Gerd Finke, Frank Werner, Valery S. Gordon, Alexandre Dolgui

Publication date: 10 August 2011

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

Full work available at URL: https://doi.org/10.1016/j.dam.2011.04.023

zbMATH Keywords

computational complexityforbidden induced subgraphapproximabilitydissociation set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (39)

Approximating Bounded Degree Deletion via Matroid Matching ⋮ Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree ⋮ Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs ⋮ Maximal and maximum dissociation sets in general and triangle-free graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ New Results on Directed Edge Dominating Set ⋮ A \(5k\)-vertex kernel for 3-path vertex cover ⋮ A bound on the dissociation number ⋮ The maximum number of maximum dissociation sets in trees ⋮ Relating the independence number and the dissociation number ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Maximum dissociation sets in subcubic trees ⋮ On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number ⋮ A faster FPT algorithm for 3-path vertex cover ⋮ Extremal vertex-degree function index with given order and dissociation number ⋮ On spectral extrema of graphs with given order and dissociation number ⋮ Minimum number of maximal dissociation sets in trees ⋮ On the maximum number of maximum dissociation sets in trees with given dissociation number ⋮ Uniformly dissociated graphs ⋮ Unnamed Item ⋮ On computing the minimum 3-path vertex cover and dissociation number of graphs ⋮ On the vertex \(k\)-path cover ⋮ Kernelization and Parameterized Algorithms for 3-Path Vertex Cover ⋮ Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems ⋮ Approximation algorithm for minimum connected 3-path vertex cover ⋮ Improved approximation algorithms for path vertex covers in regular graphs ⋮ Hitting subgraphs in \(P_4\)-tidy graphs ⋮ Kernels for packing and covering problems ⋮ On a relation between \(k\)-path partition and \(k\)-path vertex cover ⋮ Partitioning a graph into small pieces with applications to path transversal ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs ⋮ Relating dissociation, independence, and matchings ⋮ The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs ⋮ 3-path vertex cover and dissociation number of hexagonal graphs ⋮ The \(k\)-path vertex cover of rooted product graphs ⋮ The \(k\)-separator problem: polyhedra, complexity and approximation results

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Approximating the minimum maximal independence number
• Irredundancy in circular arc graphs
• On approximating the minimum independent dominating set
• Weakly triangulated graphs
• Domination in convex and chordal bipartite graphs
• Approximability results for the maximum and minimum maximal induced matching problems
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
• Some results on graphs without long induced paths
• On a conjecture of Fink and Jacobson concerning k-domination and k- dependence
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• NP-completeness of some generalizations of the maximum matching problem
• Computing independent sets in graphs with large girth
• Stability number of bull- and chair-free graphs
• Induced matchings
• Induced matchings in asteroidal triple-free graphs
• Induced matchings in intersection graphs.
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• On the approximability of the maximum induced matching problem
• Finding a maximum induced matching in weakly chordal graphs
• Optimizing weakly triangulated graphs
• On maximum induced matchings in bipartite graphs
• Algorithms for weakly triangulated graphs
• HAMILTONian circuits in chordal bipartite graphs
• Reductions, completeness and the hardness of approximability
• The graphs with maximum induced matching and maximum matching the same size
• Independent packings in structured graphs
• On the Complexity of General Graph Factor Problems
• Improper coloring of unit disk graphs
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• On graphs with polynomially solvable maximum-weight clique problem
• Node-Deletion Problems on Bipartite Graphs
• The complexity of restricted spanning tree problems
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• A New Algorithm for Generating All the Maximal Independent Sets
• Perfect Elimination and Chordal Bipartite Graphs
• Graph Classes: A Survey
• Independent Sets in Asteroidal Triple-Free Graphs
• Bipartite Domination and Simultaneous Matroid Covers
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• On the completeness of a generalized matching problem
• Algorithms – ESA 2004
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• The complexity of theorem-proving procedures
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

This page was built for publication: The complexity of dissociation set problems in graphs