Problem podziału krawędzi na grafach sześciennych

Czy zbadano złożoność następującego problemu?

Dane wejściowe : sześcienny (lub nieregularny) wykres G = ( V , E ) , naturalna górna granica $3$$G=(V,E)$$t$

Pytanie : czy istnieje podział na | E | / 3 części rozmiaru 3, tak że suma rzędów (niepotrzebnie połączonych) odpowiednich podgrup jest co najwyżej t ?$E$$|E|/3$$3$$t$

Powiązana praca W literaturze znalazłem sporo artykułów, które okazują się konieczne i / lub wystarczające warunki istnienia podziału na niektóre wykresy zawierające trzy krawędzie, które są w jakiś sposób powiązane, a niektóre na temat złożoności obliczeniowej zagadnień, które krzyżują się z powyżej (np. podział musi dawać podgrupy izomorficzne do lub P 4 , a żadna waga nie jest powiązana z danym podziałem), ale żadna z nich nie rozwiązała dokładnie powyższego problemu.$K_{1,3}$$P_4$

Wymienienie wszystkich tych dokumentów byłoby trochę nudne, ale większość z nich albo cytuje, albo jest cytowana przez Dor i Tarsi .

20101024: Znalazłem ten artykuł Goldschmidta i in. , którzy dowodzą, że problem dzielenia krawędzi przez wykres na części zawierające AT MOST krawędzi, w taki sposób, że suma rzędów indukowanych podgrafów wynosi co najwyżej t , jest NP-zupełny, nawet gdy k = 3 . Czy jest oczywiste, że problem pozostaje NP-zupełny na wykresach sześciennych, kiedy wymagamy ścisłej równości wrt k ?$k$$t$$k=3$$k$

Dodatkowe informacje

Wypróbowałem kilka strategii, które zawiodły. Dokładniej, znalazłem kilka kontrprzykładów, które dowodzą, że:

• maksymalizacja liczby trójkątów nie prowadzi do optymalnego rozwiązania; co wydaje mi się sprzeczne z intuicją, ponieważ trójkąty to te podgrupy o najniższej kolejności spośród wszystkich możliwych wykresów na trzech krawędziach;

• podzielenie wykresu na połączone komponenty niekoniecznie prowadzi również do optymalnego rozwiązania. Powód, dla którego wydawało się to obiecujące, może być mniej oczywisty, ale w wielu przypadkach widać, że zamiana krawędzi w celu połączenia danego podgrafu prowadzi do rozwiązania o mniejszej wadze (przykład: spróbuj tego na trójkącie z jedną dodatkową krawędzią połączoną z każdą z nich wierzchołek; trójkąt to jedna część, reszta to druga, o łącznej masie 3 + 6 = 9. Następnie wymiana dwóch krawędzi daje ścieżkę i gwiazdkę o łącznej masie 4 + 4 = 8).

Oto sugestia, jak pokazać, że jest to trudne NP. Nie wiem czy to działa czy nie. Najpierw rozważ ten sam problem dotyczący multigrafów. Twardość NP może być łatwiej tam udowodnić. Spróbuj zmniejszyć z sześciennej MAKSYMALNEJ CIĘCIA, która jest NP trudna nawet do przybliżenia (Berman i Karpinski „On Some Tęższe wyniki niedopuszczalności”). Podziel każdą krawędź na dwie części i na każdym z nowych wierzchołków stopnia-2 dołącz wierzchołek z pętlą własną. Czy twoja maksymalna partycja odpowiada maksymalnemu cięciu?

-

Oto trochę więcej wyjaśnień.

(1) Problem maksymalizacji (liczba źródeł + liczba pochłaniaczy) dla wszystkich orientacji wykresu sześciennego jest związany z MAXCUT przez jakąś funkcję liniową. Wymaga to wykazania pewnej podstawowej zależności między maksymalnymi cięciami a maksymalnymi orientacjami źródeł i zlewów. W jednym kierunku, przy maksymalnym cięciu (U, V), możemy zorientować całą krawędź od U do V. Wewnętrzne krawędzie E (U) tworzą pasujące, więc można je zorientować dowolnie i podobnie dla E (V), i całkowita liczba źródeł i pochłaniaczy jest jakąś liniową funkcją wielkości cięcia. W przeciwnym kierunku, biorąc pod uwagę maksymalną orientację na pochodzenie i opadanie, podział U = wierzchołki stopnia 0 lub 1, V = wierzchołki stopnia 2 lub 3 daje cięcie.

(2) W opisanej powyżej transformacji na przecinanie krawędzi, w optymalnej konfiguracji każda pętla jest zabarwiona tak samo jak krawędź obok niej, a wlog ta krawędź jest zabarwiona tak samo jak inna krawędź (nie pętli) obok że. Tak więc każda dwudzielna krawędź ma jeden kolor pochodzący z dołączonej pętli i jeden inny kolor. Odpowiada to orientacji i zastosowanie ma (1).