Viktor Zamaraev

TCS Journal 2025 Journal Article

Linear Programming complementation

• Maximilien Gadouleau
• George B. Mertzios
• Viktor Zamaraev

In this paper we introduce a new operation for Linear Programming (LP), called LP complementation, which resembles many properties of LP duality. Given a maximisation (resp. minimisation) LP P, we define its complement Q as a specific minimisation (resp. maximisation) LP which has the same objective function as P. Our central result is the LP complementation theorem, that relates the optimal value Image 1 of P and the optimal value Image 2 of its complement by Image 3. The LP complementation operation can be applied if and only if P has an optimum value greater than 1. To illustrate this, we first apply LP complementation to hypergraphs. For any hypergraph H, we review the four classical LPs, namely covering K ( H ), packing P ( H ), matching M ( H ), and transversal T ( H ). For every hypergraph H = ( V, E ), we call Image 4 the complement of H. For each of the above four LPs, we relate the optimal values of the LP for the dual hypergraph Image 5 to that of the complement hypergraph Image 6 (e. g. Image 7 ). We then apply LP complementation to fractional graph theory. We prove that the LP for the fractional in-dominating number of a digraph D is the complement of the LP for the fractional total out-dominating number of the digraph complement Image 8 of D. Furthermore we apply the hypergraph complementation theorem to matroids. We establish that the fractional matching number of a matroid coincide with its edge toughness. As our last application of LP complementation, we introduce the natural problem Vertex Cover with Budget (VCB): for a graph G = ( V, E ) and a positive integer b, what is the maximum number t b of vertex covers S 1, …, S t b of G, such that every vertex v ∈ V appears in at most b vertex covers? The integer b can be viewed as a “budget” that we can spend on each vertex and, given this budget, we aim to cover all edges for as long as possible. We relate VCB with the LP Q G for the fractional chromatic number χ f of a graph G. More specifically, we prove that, as b → ∞, the optimum for VCB satisfies t b ∼ t f ⋅ b, where t f is the optimal solution to the complement LP of Q G. Finally, our results imply that, for any finite budget b, it is NP-hard to decide whether t b ≥ b + c for any 1 ≤ c ≤ b − 1.

SODA Conference 2024 Conference Paper

Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank

• Nathaniel Harms
• Viktor Zamaraev

SODA Conference 2024 Conference Paper

Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes

• Édouard Bonnet
• Julien Duron
• John Sylvester 0001
• Viktor Zamaraev
• Maksim Zhukovskii

We show that for any natural number s, there is a constant γ and a subgraph-closed class having, for any natural n, at most γ n graphs on n vertices up to isomorphism, but no adjacency labeling scheme with labels of size at most s log n. In other words, for every s, there is a small -even tiny - monotone class without universal graphs of size n s. Prior to this result, it was not excluded that every small class has an almost linear universal graph, or equivalently a labeling scheme with labels of size (1 + o (1))log n. The existence of such a labeling scheme, a scaled-down version of the recently disproved Implicit Graph Conjecture, was repeatedly raised [Gavoille and Labourel, ESA ‘07; Dujmović et al. , JACM ‘21; Bonamy et al. , SIDMA ‘22; Bonnet et al. , Comb. Theory ‘22]. Furthermore, our small monotone classes have unbounded twin-width, thus simultaneously disprove the already-refuted Small conjecture; but this time with a self-contained proof, not relying on elaborate group-theoretic constructions. As our main ingredient, we show that with high probability an Erdős-Rényi random graph G ( n, p ) with p = O( 1/ n ) has, for every k ≤ n, at most 2 O ( k ) subgraphs on k vertices, up to isomorphism. As a barrier to our general method of producing even more complex tiny classes, we show that when p = ω(1/n), the latter no longer holds. More concretely, we provide an explicit lower bound on the number of unlabeled k -vertex induced subgraphs of G ( n, p ) when 1/ n ≤ p ≤ 1 — 1/ n. We thereby obtain a threshold for the property of having exponentially many unlabeled induced subgraphs: if min{ p, 1— p } < δ/n with δ < 1, then with high probability even the number of all unlabeled (not necessarily induced) subgraphs is for sufficiently large C, then with high probability the number of unlabeled induced subgraphs is 2 Θ( n ). This result supplements the study of counting unlabeled induced subgraphs that was initiated by Erdős and Rényi with a question on the number of unlabeled induced subgraphs of Ramsey graphs, eventually answered by Shelah.

MFCS Conference 2024 Conference Paper

Symmetric-Difference (Degeneracy) and Signed Tree Models

• Édouard Bonnet
• Julien Duron
• John Sylvester 0001
• Viktor Zamaraev

We introduce a dense counterpart of graph degeneracy, which extends the recently-proposed invariant symmetric difference. We say that a graph has sd-degeneracy (for symmetric-difference degeneracy) at most d if it admits an elimination order of its vertices where a vertex u can be removed whenever it has a d-twin, i. e. , another vertex v such that at most d vertices outside {u, v} are neighbors of exactly one of u, v. The family of graph classes of bounded sd-degeneracy is a superset of that of graph classes of bounded degeneracy or of bounded flip-width, and more generally, of bounded symmetric difference. Unlike most graph parameters, sd-degeneracy is not hereditary: it may be strictly smaller on a graph than on some of its induced subgraphs. In particular, every n-vertex graph is an induced subgraph of some O(n²)-vertex graph of sd-degeneracy 1. In spite of this and the breadth of classes of bounded sd-degeneracy, we devise Õ(√n)-bit adjacency labeling schemes for them, which are optimal up to the hidden polylogarithmic factor. This is attained on some even more general classes, consisting of graphs G whose vertices bijectively map to the leaves of a tree T, where transversal edges and anti-edges added to T define the edge set of G. We call such graph representations signed tree models as they extend the so-called tree models (or twin-decompositions) developed in the context of twin-width, by adding transversal anti-edges. While computing the degeneracy of a graph takes linear time, we show that determining its symmetric difference is para-co-NP-complete. This may seem surprising as symmetric difference can serve as a short-sighted first approximation of twin-width, whose computation is para-NP-complete. Indeed, we show that deciding if the symmetric difference of an input graph is at most 8 is co-NP-complete. We also show that deciding if the sd-degeneracy is at most 6 is NP-complete, contrasting with the symmetric difference.

TCS Journal 2022 Journal Article

Distributed minimum vertex coloring and maximum independent set in chordal graphs

• Christian Konrad
• Viktor Zamaraev

We give deterministic distributed ( 1 + ϵ ) -approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in O ( 1 ϵ log ⁡ n ) rounds, and our independent set algorithm has a runtime of O ( 1 ϵ log ⁡ ( 1 ϵ ) log ⁎ ⁡ n ) rounds. For coloring, existing lower bounds imply that the dependencies on 1 ϵ and log ⁡ n are best possible. For independent set, we prove that Ω ( 1 ϵ ) rounds are necessary. Both our algorithms make use of a tree decomposition of the input chordal graph. They iteratively peel off interval subgraphs, which are identified via the tree decomposition of the input graph, thereby partitioning the vertex set into O ( log ⁡ n ) layers. For coloring, each interval graph is colored independently, which results in various coloring conflicts between the layers. These conflicts are then resolved in a separate phase, using the particular structure of our partitioning. For independent set, only the first O ( log ⁡ 1 ϵ ) layers are required as they already contain a large enough independent set. We develop a ( 1 + ϵ ) -approximation maximum independent set algorithm for interval graphs, which we then apply to those layers. While tree decompositions have only played a minor role in distributed computing, our work demonstrates their potential for designing efficient distributed algorithms.

STOC Conference 2022 Conference Paper

Randomized communication and implicit graph representations

• Nathaniel Harms
• Sebastian Wild
• Viktor Zamaraev

FOCS Conference 2021 Conference Paper

Sharp Thresholds in Random Simple Temporal Graphs

• Arnaud Casteigts
• Michael Raskin
• Malte Renken
• Viktor Zamaraev

A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i. e. , a temporal path). In this paper, we consider a simple model of random temporal graph, obtained from an Erdös-Rényi random graph G ~ Gn, p by considering a random permutation π of the edges and interpreting the ranks in π as presence times. We give a thorough study of the temporal connectivity of such graphs and derive implications for the existence of several kinds of sparse spanners. It turns out that temporal reachability in this model exhibits a surprisingly regular sequence of thresholds. In particular, we show that, at p = log $n$ /n, any fixed pair of vertices can a. a. s. reach each other; at 2 log $n$ /n, at least one vertex (and in fact, any fixed vertex) can a. a. s. reach all others; and at 3 log $n$ /n, all the vertices can a. a. s. reach each other, i. e. , the graph is temporally connected. Furthermore, the graph admits a temporal spanner of size 2n + o(n) as soon as it becomes temporally connected, which is nearly optimal as 2n - 4 is a lower bound. This result is quite significant because temporal graphs do not admit spanners of size O(n) in general (Kempe, Kleinberg, Kumar, STOC 2000). In fact, they do not even always admit spanners of size o( $n$ 2 ) (Axiotis, Fotakis, ICALP 2016). Thus, our result implies that the obstructions found in these works, and more generally, any non-negligible obstruction is statistically insignificant: nearly optimal spanners always exist in random temporal graphs. All the above thresholds are sharp. Carrying the study of temporal spanners a step further, we show that pivotal spanners-i. e. , spanners of size 2n - 2 made of two spanning trees glued at a single vertex (one descending in time, the other ascending subsequently)-exist a. a. s. at 4 log $n$ / n, this threshold being also sharp. Finally, we show that optimal spanners (of size 2n - 4) also exist a. a. s. at p = 4 log $n$ /n, Whether this value is a sharp threshold is open, we conjecture that it is. For completeness, we compare the above results to existing results in related areas, including edge-ordered graphs, gossip theory, and population protocols, showing that our results can be interpreted in these settings as well, and that in some cases, they improve known results therein. Finally, we discuss an intriguing connection between our results and Janson's celebrated results on percolation in weighted graphs.

MFCS Conference 2020 Conference Paper

Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle

• Argyrios Deligkas
• George B. Mertzios
• Paul G. Spirakis
• Viktor Zamaraev

In this paper we consider the following total functional problem: Given a cubic Hamiltonian graph G and a Hamiltonian cycle C₀ of G, how can we compute a second Hamiltonian cycle C₁ ≠ C₀ of G? Cedric Smith and William Tutte proved in 1946, using a non-constructive parity argument, that such a second Hamiltonian cycle always exists. Our main result is a deterministic algorithm which computes the second Hamiltonian cycle in O(n⋅2^0. 299862744n) = O(1. 23103ⁿ) time and in linear space, thus improving the state of the art running time of O*(2^0. 3n) = O(1. 2312ⁿ) for solving this problem (among deterministic algorithms running in polynomial space). Whenever the input graph G does not contain any induced cycle C₆ on 6 vertices, the running time becomes O(n⋅ 2^0. 2971925n) = O(1. 22876ⁿ). Our algorithm is based on a fundamental structural property of Thomason’s lollipop algorithm, which we prove here for the first time. In the direction of approximating the length of a second cycle in a (not necessarily cubic) Hamiltonian graph G with a given Hamiltonian cycle C₀ (where we may not have guarantees on the existence of a second Hamiltonian cycle), we provide a linear-time algorithm computing a second cycle with length at least n - 4α (√n+2α)+8, where α = (Δ-2)/(δ-2) and δ, Δ are the minimum and the maximum degree of the graph, respectively. This approximation result also improves the state of the art.

MFCS Conference 2019 Conference Paper

Deleting Edges to Restrict the Size of an Epidemic in Temporal Networks

• Jessica A. Enright
• Kitty Meeks
• George B. Mertzios
• Viktor Zamaraev

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information or behaviour spread over social networks, biological diseases spreading over contact or trade networks, and the potential flow of goods over logistical infrastructure. Often, the networks over which these processes spread are dynamic in nature, and can be modeled with graphs whose structure is subject to discrete changes over time, i. e. with temporal graphs. Here, we consider temporal graphs in which edges are available at specified timesteps, and study the problem of deleting edges from a given temporal graph in order to reduce the number of vertices (temporally) reachable from a given starting point. This could be used to control the spread of a disease, rumour, etc. in a temporal graph. In particular, our aim is to find a temporal subgraph in which a process starting at any single vertex can be transferred to only a limited number of other vertices using a temporally-feasible path (i. e. a path, along which the times of the edge availabilities increase). We introduce a natural deletion problem for temporal graphs and we provide positive and negative results on its computational complexity, both in the traditional and the parameterised sense (subject to various natural parameters), as well as addressing the approximability of this problem.

MFCS Conference 2019 Conference Paper

Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs

• Christian Konrad 0001
• Viktor Zamaraev

We give deterministic distributed (1+epsilon)-approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in O( (1 / epsilon) log n) rounds, and our independent set algorithm has a runtime of O( (1/epsilon) log(1/epsilon)log^* n) rounds. For coloring, existing lower bounds imply that the dependencies on 1/epsilon and log n are best possible. For independent set, we prove that Omega(1/epsilon) rounds are necessary. Both our algorithms make use of the tree decomposition of the input chordal graph. They iteratively peel off interval subgraphs, which are identified via the tree decomposition of the input graph, thereby partitioning the vertex set into O(log n) layers. For coloring, each interval graph is colored independently, which results in various coloring conflicts between the layers. These conflicts are then resolved in a separate phase, using the particular structure of our partitioning. For independent set, only the first O(log (1/epsilon)) layers are required as they already contain a large enough independent set. We develop a (1+epsilon)-approximation maximum independent set algorithm for interval graphs, which we then apply to those layers. This work raises the question as to how useful tree decompositions are for distributed computing.

AAAI Conference 2019 Conference Paper

Sliding Window Temporal Graph Coloring

• George B. Mertzios
• Hendrik Molter
• Viktor Zamaraev

Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matching. So far coloring problems are mostly studied on static graphs, which often stand in stark contrast to practice where data is inherently dynamic and subject to discrete changes over time. A temporal graph is a graph whose edges are assigned a set of integer time labels, indicating at which discrete time steps the edge is active. In this paper we present a natural temporal extension of the classical graph coloring problem. Given a temporal graph and a natural number ∆, we ask for a coloring sequence for each vertex such that (i) in every sliding time window of ∆ consecutive time steps, in which an edge is active, this edge is properly colored (i. e. its endpoints are assigned two different colors) at least once during that time window, and (ii) the total number of different colors is minimized. This sliding window temporal coloring problem abstractly captures many realistic graph coloring scenarios in which the underlying network changes over time, such as dynamically assigning communication channels to moving agents. We present a thorough investigation of the computational complexity of this temporal coloring problem. More specifically, we prove strong computational hardness results, complemented by efficient exact and approximation algorithms. Some of our algorithms are linear-time fixed-parameter tractable with respect to appropriate parameters, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH).

MFCS Conference 2018 Conference Paper

On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal

• Konrad K. Dabrowski
• Matthew Johnson 0002
• Giacomo Paesani
• Daniël Paulusma
• Viktor Zamaraev

Let vc(G), fvs(G) and oct(G) denote, respectively, the size of a minimum vertex cover, minimum feedback vertex set and minimum odd cycle transversal in a graph G. One can ask, when looking for these sets in a graph, how much bigger might they be if we require that they are independent; that is, what is the price of independence? If G has a vertex cover, feedback vertex set or odd cycle transversal that is an independent set, then we let, respectively, ivc(G), ifvs(G) or ioct(G) denote the minimum size of such a set. We investigate for which graphs H the values of ivc(G), ifvs(G) and ioct(G) are bounded in terms of vc(G), fvs(G) and oct(G), respectively, when the graph G belongs to the class of H-free graphs. We find complete classifications for vertex cover and feedback vertex set and an almost complete classification for odd cycle transversal (subject to three non-equivalent open cases).

MFCS Conference 2017 Conference Paper

Clique-Width for Graph Classes Closed under Complementation

• Alexandre Blanché
• Konrad K. Dabrowski
• Matthew Johnson 0002
• Vadim V. Lozin
• Daniël Paulusma
• Viktor Zamaraev

Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class is hereditary if it can be characterized by a (not necessarily finite) set H of forbidden induced subgraphs. We initiate a systematic study into the boundedness of clique-width of hereditary graph classes closed under complementation. First, we extend the known classification for the |H|=1 case by classifying the boundedness of clique-width for every set H of self-complementary graphs. We then completely settle the |H|=2 case. In particular, we determine one new class of (H1, complement of H1)-free graphs of bounded clique-width (as a side effect, this leaves only six classes of (H1, H2)-free graphs, for which it is not known whether their clique-width is bounded). Once we have obtained the classification of the |H|=2 case, we research the effect of forbidding self-complementary graphs on the boundedness of clique-width. Surprisingly, we show that for a set F of self-complementary graphs on at least five vertices, the classification of the boundedness of clique-width for ({H1, complement of H1} + F)-free graphs coincides with the one for the |H|=2 case if and only if F does not include the bull (the only non-empty self-complementary graphs on fewer than five vertices are P_1 and P_4, and P_4-free graphs have clique-width at most 2). Finally, we discuss the consequences of our results for COLOURING.

TCS Journal 2017 Journal Article

More results on weighted independent domination

• Vadim Lozin
• Dmitriy Malyshev
• Raffaele Mosca
• Viktor Zamaraev

Weighted independent domination is an NP-hard graph problem, which remains computationally intractable in many restricted graph classes. In particular, the problem is NP-hard in the classes of sat-graphs and chordal graphs. We strengthen these results by showing that the problem is NP-hard in a proper subclass of the intersection of sat-graphs and chordal graphs. On the other hand, we identify two new classes of graphs where the problem admits polynomial-time solutions.