Search

A resolving set S of a graph G is a subset of its vertices such that no two vertices of G have the same distance vector to S. The Metric Dimension problem asks for a resolving set of minimum size, and in its decision form, a resolving set of size at most some specified integer. This problem is NP-complete, and remains so in very restricted classes of graphs. It is also W[2]-complete with respect to the size of the solution. Metric Dimension has proven elusive on graphs of bounded treewidth. On the algorithmic side, a polynomial time algorithm is known for trees, and even for outerplanar graphs, but the general case of treewidth at most two is open. On the complexity side, no parameterized hardness is known. This has led several papers on the topic to ask for the parameterized complexity of Metric Dimension with respect to treewidth. We provide a first answer to the question. We show that Metric Dimension parameterized by the treewidth of the input graph is W[1]-hard. More refinedly we prove that, unless the Exponential Time Hypothesis fails, there is no algorithm solving Metric Dimension in time f (pw) n o (pw) on n-vertex graphs of constant degree, with pw the pathwidth of the input graph, and f any computable function. This is in stark contrast with an FPT algorithm of Belmonte et al. (SIAM J Discrete Math 31(2):1217–1243, 2017) with respect to the combined parameter tl + Δ , where tl is the tree-length and Δ the maximum-degree of the input graph. [ABSTRACT FROM AUTHOR]

In the Categorical Clustering problem, we are given a set of vectors (matrix) A = { a 1 , ... , a n } over Σ m , where Σ is a finite alphabet, and integers k and B. The task is to partition A into k clusters such that the median objective of the clustering in the Hamming norm is at most B. Fomin, Golovach, and Panolan [ICALP 2018] proved that the problem is fixed-parameter tractable for the binary case Σ = { 0 , 1 }. We extend this algorithmic result to a popular capacitated clustering model, where in addition the sizes of the clusters are lower and upper bounded by integer parameters p and q , respectively. Our main theorem is that the problem is solvable in time 2 O (B log ⁡ B) | Σ | B ⋅ (m n) O (1). [ABSTRACT FROM AUTHOR]

In this work, we study the k-median clustering problem with an additional equal-size constraint on the clusters from the perspective of parameterized preprocessing. Our main result is the first lossy (2-approximate) polynomial kernel for this problem parameterized by the cost of clustering. We complement this result by establishing lower bounds for the problem that eliminate the existence of an (exact) kernel of polynomial size and a PTAS. [ABSTRACT FROM AUTHOR]

A digraph D is singly connected if for all ordered pairs of vertices u , v ∈ V (D) , there is at most one path in D from u to v. In this paper, we study the Singly Connected Vertex Deletion (SCVD) problem: Given an n -vertex digraph D and a positive integer k , does there exist a set S ⊆ V (D) such that | S | ≤ k and D − S is singly connected? This problem may be seen as a directed counterpart of the (Undirected) Feedback Vertex Set problem, as an undirected graph is singly connected if and only if it is acyclic. SCVD is known to be NP -hard on general digraphs. We study the complexity of SCVD on various classes of digraphs such as tournaments, and various generalisations of tournaments such as digraphs of bounded independence number, in- and out-tournaments and local tournaments. We show that unlike the Feedback Vertex Set on Tournaments (FVST) problem, SCVD is polynomial-time solvable on tournaments. In addition, we show that SCVD is polynomial-time solvable on digraphs of bounded independence number, and on the class of acyclic local tournaments. We also study the parameterized complexity of SCVD, with k as the parameter, on the class of in-tournaments. And we show that on in-tournaments, SCVD admits a fixed-parameter tractable algorithm and a quadratic vertex kernel. We also show that on the class of local tournaments, which is a sub-class of in-tournaments, SCVD admits a linear vertex kernel. [ABSTRACT FROM AUTHOR]

k -means and k -median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependencies on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, Dasgupta, Rashtchian, and Frost proposed an elegant model of explainable k -means and k -median clustering in ICML 2020. In this model, a decision tree with k leaves provides a straightforward characterization of the data set into clusters. We study two natural algorithmic questions about explainable clustering. (1) For a given clustering, how to find the "best explanation" by using a decision tree with k leaves? (2) For a given set of points, how to find a decision tree with k leaves minimizing the k -means/median objective of the resulting explainable clustering? To address the first question, we introduce a new model of explainable clustering. Our model, inspired by the notion of outliers in robust statistics, is the following. We are seeking a small number of points (outliers) whose removal makes the existing clustering well-explainable. For addressing the second question, we initiate the study of the model of Moshkovitz et al. from the perspective of multivariate complexity. Our rigorous algorithmic analysis sheds some light on the influence of parameters like the input size, dimension of the data, the number of outliers, the number of clusters, and the approximation ratio, on the computational complexity of explainable clustering. [ABSTRACT FROM AUTHOR]

The widespread availability of energy-dense, rewarding foods is correlated with the increased incidence of obesity across the globe. Overeating during mealtimes and unscheduled snacking disrupts timed metabolic processes, which further contribute to weight gain. The neuronal mechanism by which the consumption of energy-dense food restructures the timing of feeding is poorly understood. Here, we demonstrate that dopaminergic signaling within the suprachiasmatic nucleus (SCN), the central circadian pacemaker, disrupts the timing of feeding, resulting in overconsumption of food. D1 dopamine receptor (Drd1)-null mice are resistant to diet-induced obesity, metabolic disease, and circadian disruption associated with energy-dense diets. Conversely, genetic rescue of Drd1 expression within the SCN restores diet-induced overconsumption, weight gain, and obesogenic symptoms. Access to rewarding food increases SCN dopamine turnover, and elevated Drd1-signaling decreases SCN neuronal activity, which we posit disinhibits downstream orexigenic responses. These findings define a connection between the reward and circadian pathways in the regulation of pathological calorie consumption. • Diet-induced obesity (DIO) requires dopamine (DA)-Drd1 signaling • DA-Drd1 signaling in the central circadian clock (SCN) instigates DIO • SCN DA-Drd1 signaling disinhibits hedonic food consumption in between meals • Diet drives dysbiosis and peripheral circadian desynchrony independent of Drd1 Palatable diets rich in fat and sugar incentivize overeating, which leads to obesity. Grippo and Tang et al. discover a unique role for dopamine signaling in the central circadian clock that promotes overconsumption outside of mealtimes. [ABSTRACT FROM AUTHOR]