Median graphs form the class of graphs which is the most studied in metric graph theory. Recently, Bénéteau et al. 2019 designed a linear-time algorithm computing both the Θ-classes and the median ...set of median graphs. A natural question emerges: is there a linear-time algorithm computing the diameter for median graphs?
We answer positively to this question for median graphs G with constant dimension d, i.e. the dimension of the largest induced hypercube of G. We propose a combinatorial algorithm computing the diameter of median graphs with running time O(2O(dlogd)n). In particular, since the hypercube Q4 of dimension 4 is not planar, it shows also that the diameter of planar median graphs can be computed in O(n).
Partial cubes are the graphs which can be embedded into hypercubes. The cube polynomial of a graph
G is a counting polynomial of induced hypercubes of
G, which is defined as
C
(
G
,
x
)
≔
∑
i
⩾
0
α
i
...(
G
)
x
i, where
α
i
(
G
) is the number of induced
i‐cubes (hypercubes of dimension
i) of
G. The clique polynomial of
G is defined as
C
l
(
G
,
x
)
≔
∑
i
⩾
0
a
i
(
G
)
x
i, where
a
i
(
G
) (
i
⩾
1) is the number of
i‐cliques in
G and
a
0
(
G
)
=
1. Equivalently,
C
l
(
G
,
x
) is exactly the independence polynomial of the complement
G
¯ of
G. The crossing graph
G
# of a partial cube
G is the graph whose vertices are corresponding to the
Θ‐classes of
G, and two
Θ‐classes are adjacent in
G
# if and only if they cross in
G. In the present paper, we prove that for a partial cube
G,
C
(
G
,
x
)
⩽
C
l
(
G
#
,
x
+
1
) and the equality holds if and only if
G is a median graph. Since every graph can be represented as the crossing graph of a median graph, the above necessary‐and‐sufficient result shows that the study on the cube polynomials of median graphs can be transformed to the one on the clique polynomials of general graphs (equivalently, on the independence polynomials of their complements). In addition, we disprove the conjecture that the cube polynomials of median graphs are unimodal.
We deal with the problem of aggregation of rhombus tilings with the help of a certain natural majority rule. As a 2-dimensional counterpart of the well-known problem of aggregation of linear orders ...and related Condorcet domains, in this paper we introduce a Condorcet super-domain to be a collection of rhombus tilings on a zonogon Z(n;2) satisfying the property that whenever the voting designs (ballots) belong to this collection, then the majority rule produces a rhombus tiling as well. A study of Condorcet super-domains and methods of constructing them form the main subject of this paper.
On sparse graphs, Roditty and Williams 2013 proved that no
O
(
n
2
-
ε
)
-time algorithm achieves an approximation factor smaller than
3
2
for the diameter problem unless SETH fails. In this article, ...we solve an open question formulated in the literature: can we use the structural properties of median graphs to break this global quadratic barrier? We propose the first combinatorial algorithm computing exactly all eccentricities of a median graph in truly subquadratic time. Median graphs constitute the family of graphs which is the most studied in metric graph theory because their structure represents many other discrete and geometric concepts, such as CAT(0) cube complexes. Our result generalizes a recent one, stating that there is a linear-time algorithm for all eccentricities in median graphs with bounded dimension
d
,
i.e.
the dimension of the largest induced hypercube. This prerequisite on
d
is not necessary anymore to determine all eccentricities in subquadratic time. The execution time of our algorithm is
O
(
n
1.6456
log
O
(
1
)
n
)
. We provide also some satellite outcomes related to this general result. In particular, restricted to simplex graphs, this algorithm enumerates all eccentricities with a quasilinear running time. Moreover, an algorithm is proposed to compute exactly all reach centralities in time
O
(
2
3
d
n
log
O
(
1
)
n
)
.
The dominating graph of a graph
G
is a graph whose vertices correspond to the dominating sets of
G
and two vertices are adjacent whenever their corresponding dominating sets differ in exactly one ...vertex. Studying properties of dominating graph has become an increasingly interesting subject in domination theory. On the other hand, median graphs and partial cubes are two fundamental graph classes in graph theory. In this paper, we make some new connections between domination theory and the theory of median graphs and partial cubes. As the main result, we show that the following conditions are equivalent for every graph
G
≄
C
4
with no isolated vertex, and in particular, that the simple third condition completely characterizes first two ones in which three concepts of dominating graphs, median graphs and complement of minimal dominating sets get related:
The dominating graph of
G
is a median graph,
The complement of every minimal dominating set of
G
is a minimal dominating set,
Every vertex of
G
is either of degree 1 or adjacent to a vertex of degree 1.
As another result, we prove that the dominating graph of every graph is a partial cube and also give some examples to show that not all partial cubes or median graphs are isomorphic to the dominating graph of a graph. The above-mentioned results, as another highlight of the paper, provide novel infinite sources of examples of median graphs and partial cubes.
In this paper, we present GMG-BCU—a local search algorithm based on block coordinate update for estimating a generalized median graph for a given collection of labeled or unlabeled input graphs. ...Unlike all competitors, GMG-BCU is designed for both discrete and continuous label spaces and can be configured to run in linear time w.r.t. the size of the graph collection whenever median node and edge labels are computable in linear time. These properties make GMG-BCU usable for applications such as differential microbiome data analysis, graph classification, clustering, and indexing. We also prove theoretical properties of generalized median graphs, namely, that they exist under reasonable assumptions which are met in almost all application scenarios, that they are in general non-unique, that they are NP-hard to compute and APX-hard to approximate, and that no polynomial α-approximation exists for any α unless the graph isomorphism problem is in P. Extensive experiments on six different datasets show that our heuristic GMG-BCU always outperforms the state of the art in terms of runtime or quality (on most datasets, both w.r.t. runtime and quality), that it is the only available heuristic which can cope with collections containing several thousands of graphs, and that it shows very promising potential when used for the aforementioned applications. GMG-BCU is freely available on GitHub: https://github.com/dbblumenthal/gedlib/.
Condorcet domains are sets of linear orders with the property that, whenever the preferences of all voters of a society belong to this set, their majority relation has no cycles. We observe that, ...without loss of generality, every such domain can be assumed to be closed in the sense that it contains the majority relation of every profile with an odd number of voters whose preferences belong to this domain. We show that every closed Condorcet domain can be endowed with the structure of a median graph and that, conversely, every median graph is associated with a closed Condorcet domain (in general, not uniquely). Condorcet domains that have linear graphs (chains) associated with them are exactly the preference domains with the classical single-crossing property. As a corollary, we obtain that a domain with the so-called 'representative voter property' is either a single-crossing domain or a very special domain containing exactly four different preference orders whose associated median graph is a 4-cycle. Maximality of a Condorcet domain imposes additional restrictions on the associated median graph. We prove that among all trees only (some) chains can be associated graphs of maximal Condorcet domains, and we characterize those single-crossing domains which are maximal Condorcet domains. Finally, using the characterization of Nehring and Puppe (J Econ Theory 135:269–305, 2007) of monotone Arrovian aggregation, we show that any closed Condorcet domain admits a rich class of strategy-proof social choice functions.
A projection of a vertex
of a graph
over a subset
of vertices is a vertex of
at minimal distance from
. The study of projections over quasi-intervals gives rise to a new characterization of ...quasi-median graphs.
We provide a counterexample to a conjecture by Thiagarajan (1996, 2002) that regular event structures correspond to event structures obtained as unfoldings of finite 1-safe Petri nets. The same ...counterexample is used to disprove a closely related conjecture by Badouel, Darondeau, and Raoult (1999). Using that domains of events structures are CAT(0) cube complexes, we construct our counterexample from an example by Wise (1996, 2007) of a nonpositively curved square complex whose universal cover contains an aperiodic plane. We prove that other counterexamples to Thiagarajan's conjecture arise from aperiodic 4-way deterministic tile sets of Kari and Papasoglu (1999) and Lukkarila (2009). On the positive side, using breakthrough results by Agol (2013) and Haglund and Wise (2008, 2012) from geometric group theory, we prove that Thiagarajan's conjecture holds for strongly hyperbolic regular event structures.
PDF
