-
Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound
Authors:
Jonas Lill,
Kalina Petrova,
Simon Weber
Abstract:
MaxCut is a classical NP-complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-Erdős bound states that any connected graph on n vertices with m edges contains a cut of size at least $m/2 + (n-1)/4$. Crowston, Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem on simple connected graphs admits an FPT algorithm, where the parameter k is t…
▽ More
MaxCut is a classical NP-complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-Erdős bound states that any connected graph on n vertices with m edges contains a cut of size at least $m/2 + (n-1)/4$. Crowston, Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem on simple connected graphs admits an FPT algorithm, where the parameter k is the difference between the desired cut size c and the lower bound given by the Edwards-Erdős bound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run in parameterized linear time, i.e., $f(k)\cdot O(m)$. We improve upon this result in two ways: Firstly, we extend the algorithm to work also for multigraphs (alternatively, graphs with positive integer weights). Secondly, we change the parameter; instead of the difference to the Edwards-Erdős bound, we use the difference to the Poljak-Turzík bound. The Poljak-Turzík bound states that any weighted graph G has a cut of size at least $w(G)/2 + w_{MSF}(G)/4$, where w(G) denotes the total weight of G, and $w_{MSF}(G)$ denotes the weight of its minimum spanning forest. In connected simple graphs the two bounds are equivalent, but for multigraphs the Poljak-Turzík bound can be larger and thus yield a smaller parameter k. Our algorithm also runs in parameterized linear time, i.e., $f(k)\cdot O(m+n)$.
△ Less
Submitted 1 July, 2024;
originally announced July 2024.
-
Improved bounds for polylogarithmic graph distances in scale-free percolation and related models
Authors:
Kostas Lakis,
Johannes Lengler,
Kalina Petrova,
Leon Schiller
Abstract:
In this paper, we study graph distances in the geometric random graph models scale-free percolation SFP, geometric inhomogeneous random graphs GIRG, and hyperbolic random graphs HRG. Despite the wide success of the models, the parameter regime in which graph distances are polylogarithmic is poorly understood. We provide new and improved lower bounds. In a certain portion of the parameter regime, t…
▽ More
In this paper, we study graph distances in the geometric random graph models scale-free percolation SFP, geometric inhomogeneous random graphs GIRG, and hyperbolic random graphs HRG. Despite the wide success of the models, the parameter regime in which graph distances are polylogarithmic is poorly understood. We provide new and improved lower bounds. In a certain portion of the parameter regime, those match the known upper bounds.
Compared to the best previous lower bounds by Hao and Heydenreich, our result has several advantages: it gives matching bounds for a larger range of parameters, thus settling the question for a larger portion of the parameter space. It strictly improves the lower bounds by Hao and Heydenreich for all parameters settings in which those bounds were not tight. It gives tail bounds on the probability of having short paths, which imply shape theorems for the $k$-neighbourhood of a vertex whenever our lower bounds are tight, and tight bounds for the size of this $k$-neighbourhood. And last but not least, our proof is much simpler and not much longer than two pages, and we demonstrate that it generalizes well by showing that the same technique also works for first passage percolation.
△ Less
Submitted 14 May, 2024; v1 submitted 12 May, 2024;
originally announced May 2024.
-
Mobile Data Service Adoption and Use from a Service Supply Perspective: An Empirical Investigation
Authors:
Krassie Petrova,
Stephen G. MacDonell,
Dave Parry
Abstract:
The paper presents the findings of an empirical study of the views of a selection of mobile data service (MDS) supply chain participants about anticipated MDS customer requirements and expectations, and about the MDS environment. Applying an inductive thematic analysis approach, the study data are first represented as a thematic map; the thematic map is then used to formulate propositions that con…
▽ More
The paper presents the findings of an empirical study of the views of a selection of mobile data service (MDS) supply chain participants about anticipated MDS customer requirements and expectations, and about the MDS environment. Applying an inductive thematic analysis approach, the study data are first represented as a thematic map; the thematic map is then used to formulate propositions that contribute an MDS supplier perspective to models investigating MDS customer adoption and use.
△ Less
Submitted 25 March, 2021;
originally announced April 2021.
-
Enhancing Data Security in the User Layer of Mobile Cloud Computing Environment: A Novel Approach
Authors:
Noah Oghenfego Ogwara,
Krassie Petrova,
Mee Loong,
Yang,
Stephen G. MacDonell
Abstract:
This paper reviews existing Intrusion Detection Systems (IDS) that target the Mobile Cloud Computing (MCC), Cloud Computing (CC), and Mobile Device (MD) environment. The review identifies the drawbacks in existing solutions and proposes a novel approach towards enhancing the security of the User Layer (UL) in the MCC environment. The approach named MINDPRES (Mobile- Cloud Intrusion Detection and P…
▽ More
This paper reviews existing Intrusion Detection Systems (IDS) that target the Mobile Cloud Computing (MCC), Cloud Computing (CC), and Mobile Device (MD) environment. The review identifies the drawbacks in existing solutions and proposes a novel approach towards enhancing the security of the User Layer (UL) in the MCC environment. The approach named MINDPRES (Mobile- Cloud Intrusion Detection and Prevention System) combines a host-based IDS and network-based IDS using Machine Learning (ML) techniques. It applies dynamic analysis of both device resources and network traffic in order to detect malicious activities at the UL in the MCC environment. Preliminary investigations show that our approach will enhance the security of the UL in the MCC environment. Our future work will include the development and the evaluation of the proposed model across the various mobile platforms in the MCC environment.
△ Less
Submitted 14 December, 2020;
originally announced December 2020.
-
Optimal strategies for patrolling fences
Authors:
Bernhard Haeupler,
Fabian Kuhn,
Anders Martinsson,
Kalina Petrova,
Pascal Pfister
Abstract:
A classical multi-agent fence patrolling problem asks: What is the maximum length $L$ of a line that $k$ agents with maximum speeds $v_1,\ldots,v_k$ can patrol if each point on the line needs to be visited at least once every unit of time. It is easy to see that $L = α\sum_{i=1}^k v_i$ for some efficiency $α\in [\frac{1}{2},1)$. After a series of works giving better and better efficiencies, it was…
▽ More
A classical multi-agent fence patrolling problem asks: What is the maximum length $L$ of a line that $k$ agents with maximum speeds $v_1,\ldots,v_k$ can patrol if each point on the line needs to be visited at least once every unit of time. It is easy to see that $L = α\sum_{i=1}^k v_i$ for some efficiency $α\in [\frac{1}{2},1)$. After a series of works giving better and better efficiencies, it was conjectured that the best possible efficiency approaches $\frac{2}{3}$. No upper bounds on the efficiency below $1$ were known. We prove the first such upper bounds and tightly bound the optimal efficiency in terms of the minimum ratio of speeds $s = {v_{\max}}/{v_{\min}}$ and the number of agents $k$. Guided by our upper bounds, we construct a scheme whose efficiency approaches $1$, disproving the conjecture of Kawamura and Soejima. Our scheme asymptotically matches our upper bounds in terms of the maximal speed difference and the number of agents used, proving them to be asymptotically tight.
A variation of the fence patrolling problem considers a circular fence instead and asks for its circumference to be maximized. We consider the unidirectional case of this variation, where all agents are only allowed to move in one direction, say clockwise. At first, a strategy yielding $L = \max_{r \in [k]} r \cdot v_r$ where $v_1 \geq v_2 \geq \dots \geq v_k$ was conjectured to be optimal by Czyzowicz et al. This was proven not to be the case by giving constructions for only specific numbers of agents with marginal improvements of $L$. We give a general construction that yields $L = \frac{1}{33 \log_e\log_2(k)} \sum_{i=1}^k v_i$ for any set of agents, which in particular for the case $1, 1/2, \dots, 1/k$ diverges as $k \rightarrow \infty$, thus resolving a conjecture by Kawamura and Soejima affirmatively.
△ Less
Submitted 12 June, 2019; v1 submitted 18 September, 2018;
originally announced September 2018.
-
Bridging the Research-Practice Gap in Requirements Engineering through Effective Teaching and Peer Learning
Authors:
Andrew M. Connor,
Jim Buchan,
Krassie Petrova
Abstract:
In this paper, we introduce the concept of the research practice gap as it is perceived in the field of software requirements engineering. An analysis of this gap has shown that two key causes for the research-practice gap are lack of effective communication and the relatively light coverage of requirements engineering material in University programmes. We discuss the design and delivery of a Mast…
▽ More
In this paper, we introduce the concept of the research practice gap as it is perceived in the field of software requirements engineering. An analysis of this gap has shown that two key causes for the research-practice gap are lack of effective communication and the relatively light coverage of requirements engineering material in University programmes. We discuss the design and delivery of a Masters course in Software Requirements Engineering (SRE) that is designed to overcome some of the issues that have caused the research-practice gap. By encouraging students to share their experiences in a peer learning environment, we aim to improve shared understanding between students (many of whom are current industry practitioners) and researchers (including academic staff members) to improve the potential for effective collaborations, whilst simultaneously developing the requirements engineering skill sets of the enrolled students. Feedback from students in the course is discussed and directions for the future development of the curriculum and learning strategies are given.
△ Less
Submitted 15 July, 2014;
originally announced July 2014.
