- Оптимальное разделение между двумя моделями проверки свойств для ориентированных графов с ограниченной степенью (arXiv)
Аннотация: Мы пересматриваем связь между двумя моделями проверки фундаментальных свойств ориентированных графов с ограниченной степенью: двунаправленной моделью, в которой алгоритмы могут запрашивать как исходящие, так и входящие ребра вершины, и однонаправленной моделью, в которой запрашиваются только исходящие ребра разрешены. Czumaj, Peng and Sohler [STOC 2016] показали, что для ориентированных графов с максимальной степенью вхождения и максимальной степенью исхода, ограниченными сверху d, любое свойство, которое можно проверить со сложностью запроса Oε,d(1) в двунаправленной модели, можно проверить с помощью n1 −Ωε,d(1) запросы в однонаправленной модели. В частности, если параметр близости ε приближается к 0, то сложность запроса преобразованного тестера в однонаправленной модели приближается к n. Оставался открытым вопрос, можно ли еще улучшить это преобразование или существует ли какое-либо свойство, демонстрирующее такое крайнее разделение. Мы доказываем, что проверка свободы от подграфов, при которой подграф содержит k исходных компонентов, требует Ω(n1−1k) запросов в однонаправленной модели. Это напрямую дает первые явные свойства, демонстрирующие Oε,d(1) и Ω(n1−f(ε,d)) разделение сложности запросов между двунаправленной моделью и однонаправленной моделью, где f(ε,d) — это функция, которая приближается к 0, когда ε приближается к 0. Кроме того, наша нижняя граница также разрешает гипотезу Хеллвега и Солера [ESA 2012] о сложности запроса проверки отсутствия k-звезд.
2. Иммерсии ориентированных графов в турнирах (arXiv)
Автор: : Антонио Жирао, Роберт Хэнкок
Аннотация: Недавно Драганич, Мунха Коррейя, Судаков и Юстер показали, что каждый турнир на (2+o(1))k2 вершинах содержит 1-подразделение транзитивного турнира на k вершинах, тесное с точностью до постоянного множителя. Мы докажем аналог их результата для погружений. Пусть f(k) — наименьшее целое число такое, что любой турнир по крайней мере по f(k) вершинам должен содержать 1-погружение транзитивного турнира по k вершинам. Мы показываем, что f(k)=O(k), что очевидно с точностью до мультипликативного множителя. Если настаивать на поиске погружения полного ориентированного графа на k вершинах, то необходимо дополнительное условие на турнир. Действительно, мы показываем, что любой турнир с минимальной исходящей степенью не менее Ck должен содержать 2-погружение полного орграфа на k вершинах. Это снова жестко до значения C и тесно на порядке путей в погружении.
