Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Polynomial-time Algorithmfor Maximum Weight Independent Set on P6-free Graphs

Polynomial-time Algorithmfor Maximum Weight Independent Set on P6-free Graphs In the classic Maximum Weight Independent Set problem, we are given a graph G with a nonnegative weight function on its vertices, and the goal is to find an independent set in G of maximum possible weight. While the problem is NP-hard in general, we give a polynomial-time algorithm working on any P6-free graph, that is, a graph that has no path on 6 vertices as an induced subgraph. This improves the polynomial-time algorithm on P5-free graphs of Lokshtanov et al. [15] and the quasipolynomial-time algorithm on P6-free graphs of Lokshtanov et al. [14]. The main technical contribution leading to our main result is enumeration of a polynomial-size family ℱ of vertex subsets with the following property: For every maximal independent set I in the graph, ℱ contains all maximal cliques of some minimal chordal completion of G that does not add any edge incident to a vertex of I. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Polynomial-time Algorithmfor Maximum Weight Independent Set on P6-free Graphs

Download PDF
57 pages

Loading next page...
 
/lp/association-for-computing-machinery/polynomial-time-algorithmfor-maximum-weight-independent-set-on-p6-free-l1N77DNmzq
Publisher
Association for Computing Machinery
Copyright
Copyright © 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM.
ISSN
1549-6325
eISSN
1549-6333
DOI
10.1145/3414473
Publisher site
See Article on Publisher Site

Abstract

In the classic Maximum Weight Independent Set problem, we are given a graph G with a nonnegative weight function on its vertices, and the goal is to find an independent set in G of maximum possible weight. While the problem is NP-hard in general, we give a polynomial-time algorithm working on any P6-free graph, that is, a graph that has no path on 6 vertices as an induced subgraph. This improves the polynomial-time algorithm on P5-free graphs of Lokshtanov et al. [15] and the quasipolynomial-time algorithm on P6-free graphs of Lokshtanov et al. [14]. The main technical contribution leading to our main result is enumeration of a polynomial-size family ℱ of vertex subsets with the following property: For every maximal independent set I in the graph, ℱ contains all maximal cliques of some minimal chordal completion of G that does not add any edge incident to a vertex of I.

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Jan 22, 2022

Keywords: P6-free graphs

References

  • Solutions to the Second Round Problems
    [,
  • The effect of local constraints on the complexity of determination of the graph independence number
    [,
  • Treewidth and minimum fill-in: Grouping the minimal separators
    [,
  • Listing all potential maximal cliques of a graph
    [,
  • A proof of the Erdős-Sands-Sauer-Woodrow conjecture
    [,
  • Complement reducible graphs
    [,
  • On rigid circuit graphs
    [,
  • Finding induced subgraphs via minimal triangulations
    [,
  • Transitiv orientierbare Graphen
    [,
  • The ellipsoid method and its consequences in combinatorial optimization
    [,
  • Polynomial-time algorithm for maximum weight independent set on {P}_6 -free graphs
    [,
  • A survey of the algorithmic aspects of modular decomposition
    [,
  • Reducibility among combinatorial problems
    [,
  • Independence and efficient domination on {P}_6 -free graphs
    [,
  • Independent set in P_5 -free graphs in polynomial time
    [,
  • A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
    [,
  • On maximal independent sets of vertices in claw-free graphs
    [,
  • How to use the minimal separators of a graph for its chordal triangulation
    [,
  • On monochromatic paths in edge-coloured digraphs
    [,
  • Algorithme de recherche d’un stable de cardinalite maximum dans un graphe sans etoile
    [,