Задачи оптимизации MSOL на графах ограниченной ширины кликов с предикатами мощности

CMSOL - это подсчет монадической логики второго порядка, т. Е. Логики графов, в которой доменом является множество вершин и ребер, существуют предикаты для смежности вершин и вершин, существует ребро-вершина, существует количественное определение по ребрам, вершинам, наборам ребер и вершинам. множества, и существует предикат , который выражает ли размер является по модулю . $\textrm{Card}_{n,p}(S)$ $S$ $n$ $p$

Знаменитая теорема Курселя гласит, что если является свойством графов, выражаемых в CMSOL, то для каждого графа длины дерева не более можно решить за линейное время, выполняется ли , при условии, что в дана разложение дерева вход. В более поздних версиях теоремы было снято требование, чтобы во входных данных была дана декомпозиция дерева (потому что можно вычислить с помощью алгоритма Бодлендера ), а также была разрешена оптимизация вместо простого решения; то есть, учитывая формулу MSOL мы также можем вычислить наибольшее или наименьшее множество которое удовлетворяет . $\Pi$ $G$ $k$ $\Pi$ $G$ $\phi(S)$ $S$ $\phi(S)$

Мой вопрос касается адаптации теоремы Курселя к графам ограниченной ширины кликов. Существует аналогичная теорема, которая гласит, что если у вас есть MSOL1, который допускает количественное определение по вершинам, ребрам, множествам вершин, но не множествам ребер, то при заданном графе ширины кликов (с заданным выражением клика), для каждого фиксированного можно решить в линейное время удовлетворяет ли граф некоторой формуле MSOL1 ; все ссылки, которые я видел, указывают на $G$ $k$ $k$ $G$ $\phi$

Решаемые задачи оптимизации линейного времени на графах ограниченной ширины клики по Курселю, Маковскому и Ротиксу, Теория вычислительных систем, 2000.

Я попытался прочитать статью, но она не является самостоятельной в отношении точного определения MSOL1, и ее, честно говоря, трудно прочитать. У меня есть два вопроса относительно того, что именно можно оптимизировать в FPT, параметризуемое шириной клика графика, если во входных данных дано выражение клики.

Разрешает ли MSOL1 предикат для проверки размера набора по модулю некоторого числа? $\textrm{Card}_{n,p}(S)$
Можно ли найти набор минимального / максимального размера который удовлетворяет формуле MSOL1 в FPT, параметризованной по ширине клика, когда задано выражение? $S$ $\phi(S)$

По обоим этим вопросам я также хотел бы знать, какие правильные ссылки следует приводить при утверждении этих результатов. Заранее спасибо!

ds.algorithms reference-request graph-algorithms descriptive-complexity cliquewidth Барт Янсен
источник

Я пытался изменить некоторые из вашей статьи, извините за это. Потому что я довольно заинтересован в вашем вопросе, но все же после модификации я не уверен, правильно ли я понимаю ваши идеи. Итак, вы имеете в виду, что вам нужно точное определение MSOL1, а также наличие предиката и FPT задачи оптимизации?

Сянь-Чжи Чан 之之

В идеале я хотел бы услышать, что для каждой фиксированной формулы , где - переменная набора вершин, а формула включает предикаты Card , существует алгоритм, который с учетом графа G и клик-выражения ширины k вычисляет множество минимального размера, которое удовлетворяет в для некоторой произвольной функции (или выводит, что никакое множество удовлетворяет ).

M S O L_{1}

$MSOL_1$

ϕ (S)

$\phi(S)$

S

$S$

ϕ

$\phi$

_{n, p} (S)

$_{n,p}(S)$

S

$S$

ϕ (S)

$\phi(S)$

f (k) | V (G) |^{O (1)}

$f(k) |V(G)|^{O(1)}$

f

$f$

S

$S$

ϕ

$\phi$

Барт Янсен

Черновики книги Бруно Курселя могут быть полезны: см. Labri.fr/perso/courcell/ActSci.html в разделе «Структура графа и монадическая логика второго порядка, подход к теории языка».

Андрас Саламон

Благодарность; это, по крайней мере, решает часть 1) проблемы, так как его теорема 6.4 в первой части книги гласит: Для всех конечных множеств K и L меток вершин и ребер задача проверки модели формулы Counting MSOL1 является фиксированной: параметр кубический по отношению к параметру cliquewidth (G) + размер формулы.

Барт Янсен

Ответы:

После расспросов кажется, что ответы на 1) и 2) - ДА. Оптимизация мощности множества возможна в LinEMSOL (как упомянул Мартин Лакнер); как мне сказали, существование предикатов кардинальности не является проблемой, поскольку они могут эффективно обрабатываться автоматами дерева конечных состояний, которые должны следовать (более явно, чем в первоначально упомянутой статье) из деревьев разбора On и Myhill-Nerode- инструменты типа для обработки графов ограниченной ширины ранга .

Барт Янсен
источник

http://www.labri.fr/perso/courcell/Textes1/BC-Makowsky-Rotics(2000).pdf (упомянутая вами статья, но более удобочитаемая версия) определяет LinEMSOL (определение 10). LinEMSOL допускает задачи оптимизации MSO1, а теорема 4 утверждает, что такие задачи можно трактовать с фиксированными параметрами в зависимости от ширины клика. Таким образом, ответ на ваш второй пункт / вопрос должен быть да.

Относительно первого пункта: В «Минус-вершинах, монадической логике второго порядка и гипотезе Сисе» Бруно Курселя и Санг-Ила авторы пишут, что «Можно доказать, что никакая формула МС φ (X) не может выразить в каждой структуре множество X имеет четную мощность [10] "где [10] =" Courcelle, монадическая логика второго порядка графов "

надеюсь, это поможет

Мартин Лакнер
источник

Спасибо за понимание, но тот факт, что никакая формула MS (в общем) не может выразить, имеет ли набор даже кардинальность, здесь не очень актуален, поскольку вопрос касается языка подсчета MSOL, в который добавлены специальные предикаты, которые явно позволяют проверять мощность множества множества по модулю некоторого фиксированного числа; следовательно, в языке Counting MSOL можно выразить четность набора, и вопрос заключался в том, можем ли мы эффективно найти наименьшее / наибольшее множество, удовлетворяющее предложению в Counting MSOL, параметризованном cliquewidth. Спасибо, в любом случае!

Барт Янсен

Вы конечно правы. Я просто хотел подчеркнуть, что упомянутая вами статья не охватывает CMSOL. (Я не знаю результата, который это делает.)

Мартин Лакнер,