Problèmes de graphe NP complet sur les propriétés structurelles

(Cette question est un peu une "enquête".)

Je travaille actuellement sur un problème où j'essaie de partitionner les bords d'un tournoi en deux ensembles, qui sont tous deux nécessaires pour remplir certaines propriétés structurelles. Le problème "semble" assez difficile, et je m'attends à ce que ce soit $\mathcal{NP}$ -complete.For une raison que je vais avoir du mal à même de trouver des problèmes similaires dans la littérature.

Un exemple de problème que je considérerais comme comparable à celui auquel je fais face:

Étant donné un tournoi pondéré , existe-t-il un arc de rétroaction défini dans G dont les bords satisfont l'inégalité du triangle?$G = (V,E,w)$$G$

Notez la différence avec le problème traditionnel de l'ensemble d'arc de rétroaction: je ne me soucie pas de la taille de l'ensemble, mais je m'inquiète de savoir si l'ensemble lui-même a une certaine propriété structurelle.

Avez-vous rencontré des problèmes de décision similaires à ceux-ci? Vous souvenez-vous s'ils étaient terminés ou en P ? Toute aide appréciée.$\mathcal{NP}$$\mathcal{P}$

Je pense qu'il y a beaucoup de problèmes similaires. Voici deux en version vertex et un en version edge:

1) Un graphe donné a-t-il un ensemble de vertex de rétroaction indépendant ? (nous ne nous soucions pas de la taille de l'ensemble). Ce problème est NP-complet; la preuve peut être dérivée de la preuve du Théorème 2.1 dans Garey, Johnson & Stockmeyer .

2) Un graphique donné a-t-il une couverture de sommet qui induit un arbre ? (nous ne nous soucions pas de la taille de l'ensemble). Cet article donne une preuve d'exhaustivité de NP pour ce problème (Théorème 2); même pour les graphiques bipartites.

3) Un graphe donné a-t-il un bord dominant dont les bords forment un sous$1$ - graphe induit 1- régulier ? (également connu sous le nom d'appariement induit dominant ou dominant efficace; la version du sommet est donnée dans la deuxième réponse de Mohammad. Encore une fois, nous ne nous soucions pas de la taille de l'ensemble). Ce problème est NP-complet (bien connu, d'abord prouvé ici ), même pour les graphes bipartites planaires.

Les deux premiers problèmes sont des exemples particuliers de la classe de problèmes appelée stable- : Soit π une propriété de graphe. Un graphe donné a-t-il une couverture de sommets satisfaisant π ? Plus de cas NP-complets ainsi que des cas solvables polynomialement peuvent être trouvés dans ceci et dans cet article (et les références qui y sont données).$\pi$$\pi$$\pi$

Un autre exemple est le problème des ensembles dominants efficaces également connu sous le nom de code 1-parfait dans les graphiques. Le problème est de déterminer l'existence d'un ensemble dominant dans un graphe non orienté de telle sorte que le chemin le plus court entre deux nœuds quelconques de l'ensemble dominant C soit d'au moins 3 (bords). Le problème s'est avéré être N P- complet indépendamment par de nombreux chercheurs. Le problème reste N P -complet même pour les graphes planaires cubiques.$C$$C$$NP$$NP$

DW Bange, AE Barkauskas et PJ Slater. Ensembles dominants efficaces dans les graphiques . Applications des mathématiques discrètes, Proc. 3e SIAM Conf., Clemson / Caroline du Sud 1986, 189-199 (1988)., 1988.

$NP$$NP$

Un trou est un cycle sans corde de longueur supérieure à trois. Un cycle dans un graphe orienté est sans corde si sa longueur est supérieure à 3 et si aucun de ses sommets n'est joint par un bord du graphe orienté qui n'appartient pas au cycle.

$NP$$P$

$NP$

L'importance de détecter la structure des trous impairs dans les graphiques est mise en évidence par la récente percée du théorème de graphique parfait fort . Il montre qu'un graphe est parfait si et seulement si ni lui ni son graphe complémentaire n'ont un trou impair.