15 citations · 57 across the 24 of their papers we have counts for
30 papers
Tournaments not inducible by five voters
Leonid Chindelevitch, Ararat Harutyunyan
How many members must a committee have before its pairwise majorities can express any collective preference? With enough voters every pattern of pairwise majorities, or tournament,…
Tournaments determined by three and five voters
Leonid Chindelevitch, Ararat Harutyunyan
Pairwise majority has been studied since Ramon Llull in the 13th century and Condorcet in the 18th. A tournament records, for each pair of alternatives, which one a majority of vot…
On the list version of a conjecture of Erdős and Neumann-Lara
Ararat Harutyunyan, Lucas Picasarri-Arrieta, Gil Puig i Surroca
The dichromatic number of a digraph , denoted by , is the smallest number of colours required to colour the vertices of such that each colour class induces an acyc…
Acyclic sets and colorings in digraphs under restrictions on degrees and cycle lengths
Ararat Harutyunyan, Colin McDiarmid, Gil Puig i Surroca
Given a digraph , we denote by the maximum size of an acyclic set of (i.e. a set of vertices which induces a subdigraph with no directed cycles), and by $\vecχ(D)…
-dicolouring of digraphs
Ararat Harutyunyan, Ken-ichi Kawarabayashi, Lucas Picasarri-Arrieta +1
In 1977, Borodin and Kostochka conjectured that every graph with maximum degree is -colourable, unless it contains a clique of size . In 1999, Reed confirmed th…
ACCORD: Autoregressive Constraint-satisfying Generation for COmbinatorial Optimization with Routing and Dynamic attention
Henrik Abgaryan, Tristan Cazenave, Ararat Harutyunyan
Large Language Models (LLMs) have demonstrated impressive reasoning capabilities, yet their direct application to NP-hard combinatorial problems (CPs) remains underexplored. In thi…
Starjob: Dataset for LLM-Driven Job Shop Scheduling
Henrik Abgaryan, Tristan Cazenave, Ararat Harutyunyan
Large Language Models (LLMs) have shown remarkable capabilities across various domains, but their potential for solving combinatorial optimization problems remains largely unexplor…
LLMs can Schedule
Henrik Abgaryan, Ararat Harutyunyan, Tristan Cazenave
The job shop scheduling problem (JSSP) remains a significant hurdle in optimizing production processes. This challenge involves efficiently allocating jobs to a limited number of m…
Colouring Complete Multipartite and Kneser-type Digraphs
Ararat Harutyunyan, Gil Puig i Surroca
The dichromatic number of a digraph is the smallest such that can be partitioned into acyclic subdigraphs, and the dichromatic number of an undirected graph is the…
Odd Chromatic Number of Graph Classes
Rémy Belmonte, Ararat Harutyunyan, Noleen Köhler +1
A graph is called odd (respectively, even) if every vertex has odd (respectively, even) degree. Gallai proved that every graph can be partitioned into two even induced subgraphs, o…
Filling Crosswords is Very Hard
Laurent Gourvès, Ararat Harutyunyan, Michael Lampis +1
We revisit a classical crossword filling puzzle which already appeared in Garey\&Jonhson's book. We are given a grid with vertical and horizontal slots and a dictionary with $m…
Digraph Coloring and Distance to Acyclicity
Ararat Harutyunyan, Michael Lampis, Nikolaos Melissinos
In -Digraph Coloring we are given a digraph and are asked to partition its vertices into at most sets, so that each set induces a DAG. This well-known problem is NP-hard, as…
Average-case complexity of a branch-and-bound algorithm for min dominating set
Tom Denat, Ararat Harutyunyan, Vangelis Th. Paschos
The average-case complexity of a branch-and-bound algorithms for Minimum Dominating Set problem in random graphs in the G(n,p) model is studied. We identify phase transitions betwe…
Maximum Independent Sets in Subcubic Graphs: New Results
Ararat Harutyunyan, Michael Lampis, Vadim Lozin +1
The maximum independent set problem is known to be NP-hard in the class of subcubic graphs, i.e. graphs of vertex degree at most 3. We present a polynomial-time solution in a subcl…
Domination and fractional domination in digraphs
Ararat Harutyunyan, Tien-Nam Le, Alantha Newman +1
In this paper, we investigate the relation between the (fractional) domination number of a digraph and the independence number of its underlying graph, denoted by . More…
Coloring dense digraphs
Ararat Harutyunyan, Tien-Nam Le, Alantha Newman +1
The chromatic number of a digraph is the minimum number of acyclic subgraphs covering the vertex set of . A tournament is a hero if every -free tournament has chr…
Coloring tournaments: from local to global
Ararat Harutyunyan, Tien-Nam Le, Stéphan Thomassé +1
The \emph{chromatic number} of a directed graph is the minimum number of colors needed to color the vertices of such that each color class of induces an acyclic subdigr…
Exact distance coloring in trees
Nicolas Bousquet, Louis Esperet, Ararat Harutyunyan +1
For an integer and an even integer , consider the graph obtained from a large complete -ary tree by connecting with an edge any two vertices at distance exactly …
The complexity of tropical graph homomorphisms
Florent Foucaud, Ararat Harutyunyan, Pavol Hell +3
A tropical graph consists of a graph and a (not necessarily proper) vertex-colouring of . Given two tropical graphs and , a homomorphism of $(G,…
A Proof of the Barát-Thomassen Conjecture
Julien Bensmail, Ararat Harutyunyan, Tien-Nam Le +2
The Barát-Thomassen conjecture asserts that for every tree on edges, there exists a constant such that every -edge-connected graph with size divisible by can…
List coloring digraphs
Julien Bensmail, Ararat Harutyunyan, Ngoc Khang Le
The dichromatic number of a digraph is the least number such that the vertex set of can be partitioned into parts each of which induces an acyclic subdig…
Disjoint cycles of different lengths in graphs and digraphs
Julien Bensmail, Ararat Harutyunyan, Ngoc Khang Le +2
Understanding how the cycles of a graph or digraph behave in general has always been an important point of graph theory. In this paper, we study the question of finding a set of $k…
Disproving the normal graph conjecture
Ararat Harutyunyan, Lucas Pastor, Stéphan Thomassé
A graph is called normal if there exist two coverings, and of its vertex set such that every member of induces a clique in , every mem…
Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture
Julien Bensmail, Ararat Harutyunyan, Tien-Nam Le +1
The Barát-Thomassen conjecture asserts that there is a function such that for every fixed tree with edges, every graph which is -edge-connected with its number of…