-
Bounding the chromatic number of dense digraphs by arc neighborhoods
Authors:
Felix Klingelhoefer,
Alantha Newman
Abstract:
The chromatic number of a directed graph is the minimum number of induced acyclic subdigraphs that cover its vertex set, and accordingly, the chromatic number of a tournament is the minimum number of transitive subtournaments that cover its vertex set. The neighborhood of an arc $uv$ in a tournament $T$ is the set of vertices that form a directed triangle with arc $uv$. We show that if the neighbo…
▽ More
The chromatic number of a directed graph is the minimum number of induced acyclic subdigraphs that cover its vertex set, and accordingly, the chromatic number of a tournament is the minimum number of transitive subtournaments that cover its vertex set. The neighborhood of an arc $uv$ in a tournament $T$ is the set of vertices that form a directed triangle with arc $uv$. We show that if the neighborhood of every arc in a tournament has bounded chromatic number, then the whole tournament has bounded chromatic number. This holds more generally for oriented graphs with bounded independence number, and we extend our proof from tournaments to this class of dense digraphs. As an application, we prove the equivalence of a conjecture of El-Zahar and Erdős and a recent conjecture of Nguyen, Scott and Seymour relating the structure of graphs and tournaments with high chromatic number.
△ Less
Submitted 8 April, 2024; v1 submitted 10 July, 2023;
originally announced July 2023.
-
Coloring tournaments with few colors: Algorithms and complexity
Authors:
Felix Klingelhoefer,
Alantha Newman
Abstract:
A $k$-coloring of a tournament is a partition of its vertices into $k$ acyclic sets. Deciding if a tournament is 2-colorable is NP-hard. A natural problem, akin to that of coloring a 3-colorable graph with few colors, is to color a 2-colorable tournament with few colors. This problem does not seem to have been addressed before, although it is a special case of coloring a 2-colorable 3-uniform hype…
▽ More
A $k$-coloring of a tournament is a partition of its vertices into $k$ acyclic sets. Deciding if a tournament is 2-colorable is NP-hard. A natural problem, akin to that of coloring a 3-colorable graph with few colors, is to color a 2-colorable tournament with few colors. This problem does not seem to have been addressed before, although it is a special case of coloring a 2-colorable 3-uniform hypergraph with few colors, which is a well-studied problem with super-constant lower bounds.
We present an efficient decomposition lemma for tournaments and show that it can be used to design polynomial-time algorithms to color various classes of tournaments with few colors, including an algorithm to color a 2-colorable tournament with ten colors. For the classes of tournaments considered, we complement our upper bounds with strengthened lower bounds, painting a comprehensive picture of the algorithmic and complexity aspects of coloring tournaments.
△ Less
Submitted 8 September, 2023; v1 submitted 4 May, 2023;
originally announced May 2023.
-
Problems, proofs, and disproofs on the inversion number
Authors:
Guillaume Aubian,
Frédéric Havet,
Florian Hörsch,
Felix Klingelhoefer,
Nicolas Nisse,
Clément Rambaud,
Quentin Vermande
Abstract:
The {\it inversion} of a set $X$ of vertices in a digraph $D$ consists in reversing the direction of all arcs of $D\langle X\rangle$. The {\it inversion number} of an oriented graph $D$, denoted by ${\rm inv}(D)$, is the minimum number of inversions needed to transform $D$ into an acyclic oriented graph. In this paper, we study a number of problems involving the inversion number of oriented graphs…
▽ More
The {\it inversion} of a set $X$ of vertices in a digraph $D$ consists in reversing the direction of all arcs of $D\langle X\rangle$. The {\it inversion number} of an oriented graph $D$, denoted by ${\rm inv}(D)$, is the minimum number of inversions needed to transform $D$ into an acyclic oriented graph. In this paper, we study a number of problems involving the inversion number of oriented graphs. Firstly, we give bounds on ${\rm inv}(n)$, the maximum of the inversion numbers of the oriented graphs of order $n$. We show $n - \mathcal{O}(\sqrt{n\log n}) \ \leq \ {\rm inv}(n) \ \leq \ n - \lceil \log (n+1) \rceil$. Secondly, we disprove a conjecture of Bang-Jensen et al. asserting that, for every pair of oriented graphs $L$ and $R$, we have ${\rm inv}(L\Rightarrow R) ={\rm inv}(L) + {\rm inv}(R)$, where $L\Rightarrow R$ is the oriented graph obtained from the disjoint union of $L$ and $R$ by adding all arcs from $L$ to $R$. Finally, we investigate whether, for all pairs of positive integers $k_1,k_2$, there exists an integer $f(k_1,k_2)$ such that if $D$ is an oriented graph with ${\rm inv}(D) \geq f(k_1,k_2)$ then there is a partition $(V_1, V_2)$ of $V(D)$ such that ${\rm inv}(D\langle V_i\rangle) \geq k_i$ for $i=1,2$. We show that $f(1,k)$ exists and $f(1,k)\leq k+10$ for all positive integers $k$. Further, we show that $f(k_1,k_2)$ exists for all pairs of positive integers $k_1,k_2$ when the oriented graphs in consideration are restricted to be tournaments.
△ Less
Submitted 23 December, 2022; v1 submitted 18 December, 2022;
originally announced December 2022.
-
Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming
Authors:
Jonathan Allcock,
Yassine Hamoudi,
Antoine Joux,
Felix Klingelhöfer,
Miklos Santha
Abstract:
Subset-Sum is an NP-complete problem where one must decide if a multiset of $n$ integers contains a subset whose elements sum to a target value $m$. The best-known classical and quantum algorithms run in time $\tilde{O}(2^{n/2})$ and $\tilde{O}(2^{n/3})$, respectively, based on the well-known meet-in-the-middle technique. Here we introduce a novel classical dynamic-programming-based data structure…
▽ More
Subset-Sum is an NP-complete problem where one must decide if a multiset of $n$ integers contains a subset whose elements sum to a target value $m$. The best-known classical and quantum algorithms run in time $\tilde{O}(2^{n/2})$ and $\tilde{O}(2^{n/3})$, respectively, based on the well-known meet-in-the-middle technique. Here we introduce a novel classical dynamic-programming-based data structure with applications to Subset-Sum and a number of variants, including Equal-Sums (where one seeks two disjoint subsets with the same sum), 2-Subset-Sum (a relaxed version of Subset-Sum where each item in the input set can be used twice in the summation), and Shifted-Sums, a generalization of both of these variants, where one seeks two disjoint subsets whose sums differ by some specified value.
Given any modulus $p$, our data structure can be constructed in time $O(n^2p)$, after which queries can be made in time $O(n^2)$ to the lists of subsets summing to any value modulo $p$. We use this data structure in combination with variable-time amplitude amplification and a new quantum pair finding algorithm, extending the quantum claw finding algorithm to the multiple solutions case, to give an $O(2^{0.504n})$ quantum algorithm for Shifted-Sums, an improvement on the best-known $O(2^{0.773n})$ classical running time. Incidentally, we obtain new $\tilde{O}(2^{n/2})$ and $\tilde{O}(2^{n/3})$ classical and quantum algorithms for Subset-Sum, not based on the seminal meet-in-the-middle method. We also study Pigeonhole Equal-Sums and Pigeonhole Modular Equal-Sums, where the existence of a solution is guaranteed by the pigeonhole principle. For the former problem, we give faster classical and quantum algorithms with running time $\tilde{O}(2^{n/2})$ and $\tilde{O}(2^{2n/5})$, respectively. For the more general modular problem, we give a classical algorithm that also runs in time $\tilde{O}(2^{n/2})$.
△ Less
Submitted 22 July, 2022; v1 submitted 13 November, 2021;
originally announced November 2021.
-
Limits of the seismogenic zone in the epicentral region of the 26 December 2004 great Sumatra-Andaman earthquake: Results from seismic refraction and wide-angle reflection surveys and thermal modeling
Authors:
Frauke Klingelhoefer,
Marc-André Gutscher,
S. Ladage,
J. -X. Dessa,
David Graindorge,
D. Franke,
C. André,
Haryadi Permana,
T. Yudistira,
Ajay Chauhan
Abstract:
The 26 December 2004 Sumatra earthquake (Mw = 9.1) initiated around 30 km depth and ruptured 1300 km of the Indo-Australian Sunda plate boundary. During the Sumatra OBS (ocean bottom seismometer) survey, a wide angle seismic profile was acquired across the epicentral region. A seismic velocity model was obtained from combined travel time tomography and forward modeling. Together with reflection…
▽ More
The 26 December 2004 Sumatra earthquake (Mw = 9.1) initiated around 30 km depth and ruptured 1300 km of the Indo-Australian Sunda plate boundary. During the Sumatra OBS (ocean bottom seismometer) survey, a wide angle seismic profile was acquired across the epicentral region. A seismic velocity model was obtained from combined travel time tomography and forward modeling. Together with reflection seismic data from the SeaCause II cruise, the deep structure of the source region of the great earthquake is revealed. Four to five kilometers of sediments overlie the oceanic crust at the trench, and the subducting slab can be imaged down to a depth of 35 km. We find a crystalline backstop 120 km from the trench axis, below the fore arc basin. A high velocity zone at the lower landward limit of the raycovered domain, at 22 km depth, marks a shallow continental Moho, 170 km from the trench. The deep structure obtained from the seismic data was used to construct a thermal model of the fore arc in order to predict the limits of the seismogenic zone along the plate boundary fault. Assuming 100C-150C as its updip limit, the seismogenic zone is predicted to begin 530 km from the trench. The downdip limit of the 2004 rupture as inferred from aftershocks is within the 350C 450C temperature range, but this limit is 210-250 km from the trench axis and is much deeper than the fore arc Moho. The deeper part of the rupture occurred along the contact between the mantle wedge and the downgoing plate.
△ Less
Submitted 8 February, 2010;
originally announced February 2010.
