Perfect graphs with polynomially computable kernels

DOI10.1016/J.DAM.2018.09.027MaRDI QIDQ2283107zbMATH OpenOpenAlexWikidataFDO

Authors Adèle Pass-Lanneau, Ayumi Igarashi, Frédéric Meunier

Publication date 30 December 2019

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

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

zbMATH Keywords

kernelchordal graphclique-cutsetBoros-Gurvich theoremclaw-free perfect graphorientation of perfect graph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Perfect graphs (05C17)

Abstract: In a directed graph, a kernel is a subset of vertices that is both stable and absorbing. Not all digraphs have a kernel, but a theorem due to Boros and Gurvich guarantees the existence of a kernel in every clique-acyclic orientation of a perfect graph. However, an open question is the complexity status of the computation of a kernel in such a digraph. Our main contribution is to prove new polynomiality results for subfamilies of perfect graphs, among which are claw-free perfect graphs and chordal graphs. Our results are based on the design of kernel computation methods with respect to two graph operations: clique-cutset decomposition and augmentation of flat edges. We also prove that deciding the existence of a kernel - and computing it if it exists - is polynomial in every orientation of a chordal or a circular-arc graph, even not clique-acyclic.

Recommendations

• On kernels in perfect graphs
• Kernels in perfect line-graphs
• Polynomial algorithms for kernels in comparability, permutation and P₄-free graphs
• Perfect digraphs
• Fractional kernels in digraphs

Cites work

• scientific article; zbMATH DE number 3862930 (Why is no real title available?)
• scientific article; zbMATH DE number 3106184 (Why is no real title available?)
• A description of claw-free perfect graphs
• A note on kernels and Sperner's Lemma
• College Admissions and the Stability of Marriage
• Decomposition by clique separators
• Fractional kernels in digraphs
• Intersection graphs of paths in a tree
• Kernels in graphs with a clique-cutset
• Kernels in perfect line-graphs
• On kernels in i-triangulated graphs
• On weakly ordered systems
• Perfect digraphs
• Perfect graphs are kernel solvable
• Perfect graphs, kernels, and cores of cooperative games
• Planar kernel and Grundy with d 3, dout 2, din 2 are NP- complete
• Polynomial algorithms for kernels in comparability, permutation and P₄-free graphs
• Recognizing claw-free perfect graphs
• Reducibility among Fractional Stability Problems
• Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
• Stable marriage assignment for unequal sets
• The list chromatic index of a bipartite multigraph

Cited in

(5)

• Counting kernels in directed graphs with arbitrary orientations
• Local stability in kidney exchange programs
• Perfect digraphs
• On the kernel and related problems in interval digraphs
• Polynomial algorithms for kernels in comparability, permutation and P₄-free graphs

This page was built for publication: Perfect graphs with polynomially computable kernels

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