Бұл мақалада изоморфизм текше метрге және $ 4 $ - тұрақты графикаларға арналған?

This paper gives example of polynomial GI for certain graphs.

Мүмкін қағазды түсінбеймін, бірақ пайда болады маған текше үшін полиномиальды GI, $ 4 $ құрайды және, мүмкін, жоғары дәрежелі тұрақты графиктер болуы мүмкін.

Тұрақты графиктер үшін GI - GI аяқталды.

On p. 7 $ H (a, b, c) $ графалары анықталған. Олар - саңылау $ a + b $ жапырақтары, $ a $ жиектері бөлінеді және $ c $ оқшауланған шыңдар қосылады.

On p. 8 Теорема 4 . $ (H (0, b, c), \ overline {H (0, b ', c'))) $ - еркін графикалар $ P $ болған кезде изоморфизм:

(2) $ c, c '\ le 1 $ және $ b, b' \ ge 1 $.

$ C = c '= 1, b = b' = 5 $ алайық.

$ H = H (0,5,1) $ - $ K_ (1,5) + K_1 $.

Екі $ H $ және $ \ overline {H} $ дәрежесі $ 5 $ шыңы, сондықтан да текше немесе субграф индуцировать болады $ 4 $ тұрақты граф.

Үлкенірек $ b $ тарту арқылы бұл жұмыс жоғары болады дәрежелі тұрақты графиктер.

  1. Қағаз GI-ді текше үшін $ P $ деп есептейді ме? және $ 4 $ - тұрақты графиктер?

  2. Қағаз GI-нің $ P $-нан жоғары екенін білдіреді ме? дәрежелі тұрақты графиктер (жұмыс уақыты мүмкін $ b $-ға тәуелді, сенімді емес)

1
Графтың изоморфизмі шектеулі дәрежелі графиктердің сыныптарында. 4 графика - бұл графиктердің тек жиынтығы.
қосылды автор Saeed, көзі
@Saeed Рақмет. Үлкен $ b $ екінші мәселе туралы не деуге болады?
қосылды автор Salem F, көзі
@DavidRicherby «Полиномиальды Граф Имоморфизміне баламалы проблемаларға» сәйкес, тұрақты графиктер үшін Booth GI GI толық немесе сіздің түсініктемеңізді түсінбеймін бе? Екінші мәселе бойынша үлкен $ b $.
қосылды автор Salem F, көзі
@DavidRicherby бұл қағазға сәйкес GI толық тұрақты графиктер.
қосылды автор Salem F, көзі
Мен сіздің нәтижелеріңізді тексеріп көрмедім, бірақ GI кез келген тіркелген $ d $ үшін $ d $ - тұрақты графиктердің дәрежесі үшін шектелген дәрежелі графиктердің кез келген сыныбы үшін P . Евгений Люкс, «Мөлдір валенттің геометриясының изоморфизмі полиномиальді уақытта тексерілуі мүмкін», Компьютер және жүйелік ғылымдар журналы 25: 1 (42-65), 1982. PDF .
қосылды автор David Richerby, көзі
@joro Мен екінші кезекте all тұрақты графиктердің дәрежесі шектеулі дәрежеге ие болмағандықтан, мен GI-тің P . Түсініктемені редакциялай алмадым, себебі stoopid 5 минуттық ережеден шығып, оны жойып жібердім.
қосылды автор David Richerby, көзі

1 жауаптар

Олардың қағаздары жалпы әдеттегі кестелер туралы ештеңе айтпайды. Назар аударыңыз, $ b $ тұрақты. Іс жүзінде олардың барлық субграфы тұрақты болып табылады. Олардың полиномиальді уақыт алгоритмі бұл жағдайда барлық ықтимал $ K_ {2b + 1} $ қарастырудан тұрады. Бұл $ \ Omega (n ^ {2b + 1}) $ уақытын іске қосады. Алгоритмі $ r $ - тұрақты график үшін пайдаланғымыз келсе, онда $ \ Omega (n ^ {2r + 1}) $ уақытын қолданып, $ r $ олардың алгоритмін түзетпесе, многодинамикалық уақыт емес кіріс өлшемі. Шындығында, бұл мәселені $ b $ параметрімен белгілеген кезде XP-ге тиесілі екенін дәлелдей аламыз. параметрленген күрделілігі әдеттегі полиномиалды уақытты араластырмаңыз алгоритмдер.

1
қосылды
@joro, егер $ t $ деп белгіленген болса, онда yes ($ K_ {1, t} $ - тегін шын мәнінде тривиальды, себебі бұл шектеулі дәрежесі).
қосылды автор Saeed, көзі
@joro, Мен $ t $ тіркелген және $ K_n $ үшін, $ t $ әр $ t \ in [n-1] $ үшін $ K_n {t, $} $ K_n $ ретінде субграф. Бұл тек $ K_ {1, n} $ тегін, бұл $ t $ түзету емес. Олардың алгоритмі негізінен бұл жағдайда жұмыс істемейді. Егер сіз осы терминологияны түсінсеңіз, мұндай жағдайларда шатастырмасаңыз, викиде немесе менің сілтемемедегі параметрлердің күрделілігін оқып шығыңыз.
қосылды автор Saeed, көзі
@joro, Ия, сен дұрыс айтсаңыз, мен сіздің бірінші пікіріңізді дұрыс түсінбеймін. Мен субграфты емес индуцирленген подграфия туралы айтқан деп ойладым (кеше сұраққа жауап бердім, мен сіздің пікіріңізді көргенде, субграфия туралы субграфты емес деп ойладым деп ойладым). Иә, сіз олардың жұмысын көріп отырсыздар, олар $ 2t + 1 $ мөлшерінде изоморфизм эквиваленттігін көрсету үшін тиісті бояуды қамтамасыз ету үшін барлық кликаларды қарастыруда, сондықтан олардың алгоритмі бұрынғыдай жұмыс істейді, бірақ егер $ t $ белгіленсе. Сонымен қатар $ K_ {1, t} $ - олардың теоремасының ерекше жағдайы.
қосылды автор Saeed, көзі
@joro, Шын мәнінде емес, мен үшін. Мен тығыз байланысты аспектілерде жұмыс істеп жатырмын, мен X-free деп айтқан кезде, мен әдетте X-кішігірім тегін дегенді білдіреді және мен оны субграфия үшін де, индуцияланған субграф үшін де қолдануға болмайды.
қосылды автор Saeed, көзі
@joro, иә, және жауапта мен индукция туралы әңгімеледім.
қосылды автор Saeed, көзі
Рақмет сізге. Демек, осы өзгерісті поли үшін $ t $ $ K_ {1, t} $ - шектеулі клик санынан босатады.
қосылды автор Salem F, көзі
Менің ойымша, $ K_n $ - шектеулі деңгейдегі еркін сызбаларға қарсы мысалдар.
қосылды автор Salem F, көзі
Мен $ K_5 $ құрамында индуцирленген $ K_ {1,3} $ aka claw бар деп ойламаймын. Мен жай ғана шектеулі деңгейді көрсетпегендіктім.
қосылды автор Salem F, көзі
Проблема жоқ. Менің пікірімше, $ X $ - $ I $ индуцирленген $ X $ дегенді білдіреді.
қосылды автор Salem F, көзі
Қалай болса да, бұл құжат оны индуцияланған деп анықтайды.
қосылды автор Salem F, көзі