- Рандомизированная композиция и минимакс с малой погрешностью (arXiv)
Автор:Шалев Бен-Давид, Эрик Блейс, Мика Гёёс, Гилберт Майстре
Аннотация: мы доказываем два результата о рандомизированной сложности запроса R(f). Во-первых, мы вводим линеаризованную меру сложности LR и показываем, что она удовлетворяет внутренней оптимальной теореме композиции: R(f ◦g) ≥ Ω(R(f)LR(g)) для всех частичных f и g, и, кроме того, LR является наибольшей возможной мерой с этим свойством. В частности, LR может быть полиномиально больше, чем предыдущие меры, удовлетворяющие теореме о внутренней композиции, такие как максимальная конфликтная сложность Гавински, Ли, Санты и Саньяла (ICALP 2019).
Наш второй результат касается вопроса Яо (FOCS 1977). Он спросил, допускает ли ожидаемая сложность запроса ε-ошибки Rε(f) характеристику распределения относительно некоторого жесткого входного распределения. Верещагин (TCS 1998) дал утвердительный ответ на этот вопрос в случае ограниченной ошибки. Мы показываем, что аналогичная теорема неверна в случае малого смещения ε = 1/2 − o(1).
2. О разреженных наборах попаданий: от нормального покрытия вершин к размерности шоссе (arXiv)
Автор:Йоханнес Блюм, Янн Диссер, Андреас Эмиль Фельдманн, Сиддхарт Гупта, Анна Зых-Павлевич
Аннотация:мы рассматриваем проблему разреженного множества попаданий (Sparse-HS), где нам дана система множеств (V, F, B) с двумя семействами F, B подмножеств вселенной V . Задача состоит в том, чтобы найти множество попаданий для F, которое минимизирует максимальное количество элементов в любом из множеств B. Это обобщает несколько проблем, которые изучались в литературе. Наше внимание сосредоточено на определении сложности некоторых из этих особых случаев разреженной HS по отношению к разреженностиk, которая является оптимальным числом совпадений с элементами множества в любом множестве B (т. е. значение целевой функции). Для задачи о покрытии разреженных вершин (Sparse-VC) вселенная задается набором вершин V графа, а F — его набором ребер. Мы доказываем NP-трудность для разреженности k ≥ 2 и разрешимость за полиномиальное время для k = 1. Мы также обеспечиваем 2-аппроксимацию за полиномиальное время для любого k. Частным случаем Sparse-VC является Fair Vertex Cover (Fair-VC), где семейство B задается соседями вершин. Для этой задачи было открыто, является ли это FPT (или даже XP), параметризованным разреженностью k. Мы отвечаем на этот вопрос отрицательно, доказывая NP-трудность для константы k. Мы также предоставляем приближение с полиномиальным временем (2 − k1 ) для Fair-VC, которое лучше, чем любое приближение, возможное для Sparse-VC или задачи вершинного покрытия (в UGC).
Затем мы переключаемся на другой набор проблем, полученных из Sparse-HS, связанных с размером шоссе, который представляет собой параметр графа, моделирующий транспортные сети. В последние годы в литературе появляется все больше интересных алгоритмов для графов малой размерности шоссе. Чтобы использовать структуру таких графов, большинство из них вычисляют решения задачи покрытия r-кратчайших путей (r-SPC), где r > 0, F содержит все кратчайшие пути длины между r и 2r, а B содержит все шары радиуса 2р. Известно, что существует алгоритм XP, который вычисляет решения r-SPC с разреженностью не более h, если входной граф имеет размерность шоссе h. Однако неизвестно, существует ли соответствующий алгоритм FPT. Мы доказываем, что r-SPC, а также родственная проблема r-Highway Dimension (r-HD), которую можно использовать для формального определения дорожной размерности графа, являются W[1]-трудными. Кроме того, по результатам работы Abraham et al. [ICALP 2011] существует полиномиальный алгоритм O(log k)-аппроксимации для r-HD, но для r-SPC такой алгоритм неизвестен. Мы доказываем, что r-SPC допускает O(log n)-аппроксимацию за полиномиальное время.
3.Бинарная CSP параметризованной сложности для графов с малым покрытием вершин и сопутствующие результаты (arXiv)
Автор:Ханс Л. Бодлендер
Аннотация: в этой статье мы показываем, что двоичная CSP с размером вершинного покрытия в качестве параметра является полной для класса W[3]. Это один из первых примеров естественной W[3]-полной задачи, которая не является вариантом выполнимости. Мы получаем ряд связанных результатов с вариациями методов доказательства, в том числе: Двоичный CSP является полным для W[2d+1] с параметром размера вершинного модулятора для графов с глубиной дерева c или лесов с глубиной d для постоянная c ≥ 1, W[t]-жесткая для всех t ∈ N с шириной дерева в качестве параметра и жесткая для W[SAT] с заданной в качестве параметра вершиной обратной связи. Как следствие, мы даем некоторые проблемы сложности и принадлежности для классов в W-иерархии для раскраски списка при различных параметризациях.
