Pour une propriété fixe (classe de graphe) Π, étant donné un graphe G et un entier k, le problème de Π-délétion consiste à décider si l'on peut transformer G en graphe avec la propriété Π en supprimant au plus k arêtes. Le problème de suppression Π est connu pour être NP-difficile pour la plupart des classes de graphes bien étudiées, telles que les graphes d'accords, d'intervalles, bipartites, planaires, de comparabilité et de permutation, entre autres ; même la suppression des cactus est connue pour être NP-difficile pour les graphes généraux. Cependant, il existe une exception notable : le problème de suppression des arbres est polynomial. Motivés par ce fait, nous étudions le problème de la suppression pour certaines classes similaires aux arbres, abordant ainsi une lacune dans les connaissances de la littérature. Nous prouvons que la suppression aux cactus est difficile même lorsque l'entrée est un graphe bipartite. Du côté positif, nous montrons que le problème devient traitable lorsque l'entrée est corde, et pour le cas particulier des graphes de quasi-seuil, nous donnons un algorithme plus simple et plus rapide. En outre, nous présentons des conditions structurelles suffisantes sur la classe de graphe Π qui impliquent la dureté NP du problème de suppression Π, et montrons que la suppression des graphes généraux à certaines sous-classes bien connues de forêts est NP-dure.

Para una propiedad fija (clase de gráfico) Π, dado un gráfico G y un entero k, el problema de eliminación Π consiste en decidir si podemos convertir G en un gráfico con la propiedad Π eliminando como máximo k aristas. Se sabe que el problema de la deleción Π es NP-duro para la mayoría de las clases de gráficos bien estudiadas, como los gráficos cordales, de intervalos, bipartitos, planos, de comparabilidad y de permutación, entre otros; incluso se sabe que la deleción en los cactus es NP-dura para los gráficos generales. Sin embargo, hay una excepción notable: el problema de eliminación de árboles es polinómico. Motivados por este hecho, estudiamos el problema de eliminación para algunas clases similares a los árboles, abordando de esta manera una brecha de conocimiento en la literatura. Demostramos que la eliminación de cactus es difícil incluso cuando la entrada es un gráfico bipartito. En el lado positivo, mostramos que el problema se vuelve manejable cuando la entrada es cordal, y para el caso especial de los gráficos de cuasi-umbral damos un algoritmo más simple y rápido. Además, presentamos suficientes condiciones estructurales en la clase de gráfico Π que implican la dureza NP del problema de eliminación Π, y mostramos que la eliminación de gráficos generales a algunas subclases bien conocidas de bosques es NP-dura.

For a fixed property (graph class) Π, given a graph G and an integer k, the Π-deletion problem consists in deciding if we can turn G into a graph with the property Π by deleting at most k edges. The Π-deletion problem is known to be NP-hard for most of the well-studied graph classes, such as chordal, interval, bipartite, planar, comparability and permutation graphs, among others; even deletion to cacti is known to be NP-hard for general graphs. However, there is a notable exception: the deletion problem to trees is polynomial. Motivated by this fact, we study the deletion problem for some classes similar to trees, addressing in this way a knowledge gap in the literature. We prove that deletion to cacti is hard even when the input is a bipartite graph. On the positive side, we show that the problem becomes tractable when the input is chordal, and for the special case of quasi-threshold graphs we give a simpler and faster algorithm. In addition, we present sufficient structural conditions on the graph class Π that imply the NP-hardness of the Π-deletion problem, and show that deletion from general graphs to some well-known subclasses of forests is NP-hard.

بالنسبة للخاصية الثابتة (فئة الرسم البياني) Π، بالنظر إلى الرسم البياني G وعدد صحيح k، تتكون مشكلة حذف Π من تحديد ما إذا كان بإمكاننا تحويل G إلى رسم بياني مع الخاصية Π عن طريق حذف حواف k على الأكثر. من المعروف أن مشكلة حذف Π صعبة بالنسبة لمعظم فئات الرسوم البيانية المدروسة جيدًا، مثل الرسوم البيانية الوترية والفاصلية والثنائية والمستوية والقابلية للمقارنة والتبديل، من بين أمور أخرى ؛ حتى حذف الصبار معروف بأنه صعب بالنسبة للرسوم البيانية العامة. ومع ذلك، هناك استثناء ملحوظ: مشكلة حذف الأشجار متعددة الحدود. بدافع من هذه الحقيقة، ندرس مشكلة الحذف لبعض الفئات المشابهة للأشجار، ونتناول بهذه الطريقة فجوة معرفية في الأدبيات. نثبت أن الحذف إلى الصبار صعب حتى عندما يكون الإدخال عبارة عن رسم بياني ثنائي. على الجانب الإيجابي، نوضح أن المشكلة تصبح قابلة للحل عندما يكون الإدخال حبليًا، وبالنسبة للحالة الخاصة للرسوم البيانية شبه العتبة، نقدم خوارزمية أبسط وأسرع. بالإضافة إلى ذلك، نقدم شروطًا هيكلية كافية على فئة الرسم البياني Π التي تشير إلى صلابة NP لمشكلة حذف Π، وتبين أن الحذف من الرسوم البيانية العامة لبعض الفئات الفرعية المعروفة من الغابات أمر صعب NP.