Abstract

In this work, we study the natural monotone analogues of various equivalent definitions of : a well studied class (Poizat 2008, Koiran & Perifel 2009, Malod 2011, Mahajan & Rao 2013) that is believed to be larger than . We observe that these monotone analogues are not equivalent unlike their non-monotone counterparts, and propose monotone ( ) to be defined as the monotone analogue of Poizat's definition. With this definition, turns out to be exponentially stronger than and also satisfies several desirable closure properties that the other analogues may not. Our initial goal was to understand the monotone complexity of transparent polynomials, a concept that was recently introduced by Hrubeš & Yehudayoff (2021). In that context, we show that transparent polynomials with large support are hard for the monotone analogues of all the known definitions of , except for the one due to Poizat.

Abstract

Reconfiguring two shortest paths in a graph means modifying one shortest path to the other by changing one vertex at a time so that all the intermediate paths are also shortest paths. This problem has several natural applications, namely: (a) repaving road networks, (b) rerouting data packets in a synchronous multiprocessing setting, (c) the shipping container stowage problem, and (d) the train marshalling problem. When modelled as graph problems, (a) is the most general case while (b), (c), (d) are restrictions to different graph classes. We show that (a) does not admit polynomial-time algorithms (assuming ), even for relaxed variants of the problem (assuming ). For (b), (c), (d), we present polynomial-time algorithms to solve the respective problems. We also generalize the problem to when at most k (for a fixed integer ) contiguous vertices on a shortest path can be changed at a time.

Abstract

The concept of sum labelling was introduced in 1990 by Harary. A graph is a sum graph if its vertices can be labelled by distinct positive integers in such a way that two vertices are connected by an edge if and only if the sum of their labels is the label of another vertex in the graph. It is easy to see that every sum graph has at least one isolated vertex, and every graph can be made a sum graph by adding at most n2 isolated vertices to it. The minimum number of isolated vertices that need to be added to a graph to make it a sum graph is called the sum number of the graph. The sum number of several prominent graph classes (e.g., cycles, trees, complete graphs) is already well known. We examine the effect of taking the disjoint union of graphs on the sum number. In particular, we provide a complete characterisation of the sum number of graphs of maximum degree two, since every such graph is the disjoint union of paths and cycles

Abstract

In this paper, we determine the computational complexity of recognizing two graph classes, grounded 𝖫-graphs and stabbable grid intersection graphs. An 𝖫-shape is made by joining the bottom end-point of a vertical (|) segment to the left end-point of a horizontal (−) segment. The top end- point of the vertical segment is known as the anchor of the 𝖫-shape. Grounded 𝖫-graphs are the intersection graphs of 𝖫-shapes such that all the 𝖫-shapes’ anchors lie on the same horizontal line. We show that recognizing grounded 𝖫-graphs is 𝖭𝖯-complete. This answers an open question asked by Jelínek & Töpfer (Electron. J. Comb., 2019). Grid intersection graphs are the intersection graphs of axis-parallel line segments in which two vertical (similarly, two horizontal) segments cannot intersect. We say that a (not necessarily axis-parallel) straight line 𝓁 stabs a segment 𝑠, if 𝑠 intersects 𝓁. A graph 𝐺 is a stabbable grid intersection graph (S TAB GIG) if there is a grid intersection representation of 𝐺 in which the same line stabs all its segments. We show that recognizing S TAB GIG graphs is 𝖭𝖯-complete, even on a restricted class of graphs. This answers an open question asked by Chaplick et al. (Order, 2018).

Abstract

Parametric path problems arise independently in diverse domains, ranging from transportation to finance, where they are studied under various assumptions. We formulate a general path problem with relaxed assumptions, and describe how this formulation is applicable in these domains. We study the complexity of the general problem, and a variant of it where preprocessing is allowed. We show that when the parametric weights are linear functions, algorithms remain tractable even under our relaxed assumptions. Furthermore, we show that if the weights are allowed to be non-linear, the problem becomes NP-hard. We also study the mutli-dimensional version of the problem where the weight functions are parameterized by multiple parameters. We show that even with two parameters, the problem is NP-hard.