ACAC '26

Abstract:
In Facility Location problems there are agents that should be connected to facilities and locations where facilities may be opened so that agents can connect to them. We depart from Uncapacitated Facility Location and by assuming that the connection costs of agents to facilities are congestion dependent, we define a novel problem, namely, Facility Location for Congesting (Selfish) Commuters. The connection costs of agents to facilities come as a result of how the agents commute to reach the facilities in an underlying network with cost functions on the edges. Inapproximability results follow from the related literature and thus approximate solutions is all we can hope for. For when the cost functions are nondecreasing we employ in a novel way an approximate version of Caratheodory's Theorem to show how approximate solutions for different versions of the problem can be derived. For when the cost functions are nonincreasing we show how this problem generalizes the Cost-Distance problem and provide an algorithm that for this more general case achieves the same approximation guarantees.

Abstract:
The study of repeated interactions between a learner and a utility-maximizing optimizer has yielded deep insights into the manipulability of learning algorithms. However, existing literature primarily focuses on independent, unlinked rounds, largely ignoring the ubiquitous practical reality of budget constraints. In this paper, we study this interaction in repeated second-price auctions in a Bayesian setting between a learning agent and a strategic agent, both subject to strict budget constraints, showing that such cross-round constraints fundamentally alter the strategic landscape.

First, we generalize the classic Stackelberg equilibrium to the Budgeted Stackelberg Equilibrium. We prove that an optimizer's optimal strategy in a budgeted setting requires time-multiplexing; for a $k$-dimensional budget constraint, the optimal strategy strictly decomposes into up to $k+1$ distinct phases, with each phase employing a possibly unique mixed strategy (the case of $k=0$ recovers the classic Stackelberg equilibrium where the optimizer repeatedly uses a single mixed strategy). Second, we address the intriguing question of non-manipulability. We prove that when the learner employs a standard Proportional controller (the "P" of the PID-controller) to pace their bids, the optimizer's utility is upper bounded by their objective value in the Budgeted Stackelberg Equilibrium baseline. By bounding the dynamics of the PID controller via a novel analysis, our results establish that this widely used control-theoretic heuristic is actually strategically robust.

Short bio:
Giannis Fikioris recently completed his PhD at the Computer Science Department of Cornell University, advised by Éva Tardos. He will soon start working as a Research Scientist at Google Research, Mountain View. Before that, he completed his diploma at NTUA, advised by Dimitris Fotakis.

Abstract:
We study truthful and non-truthful protocols for combinatorial auctions in which every item can be allocated to one of two agents (multigraphs), or more generally to a fixed number of agents (hypergraphs). We show some tight - both positive and impossibility - results for the communication complexity of approximating the optimal social welfare for general monotone, subadditive, or XOS valuations.

Short bio:
Ioannis Vlachos is a Ph.D. student under the guidance of George Christodoulou at Archimedes/RC Athena and Alkmini Sgouritsa at the Athens University of Economics and Business. His research interests lie primarily in Mechanism Design and Learning-Augmented Algorithms.

Abstract:
We study the online fair division of indivisible mixed goods and chores among agents with additive valuations. At each time step, an item arrives. Each agent may value it positively, negatively, or at zero, and it must be allocated before the next item arrives. We focus on envy-freeness (EF) and envy-freeness up to one item (EF1).

Because strong fairness guarantees are difficult to achieve in the standard online setting, we allow algorithms to use a buffer that can temporarily store and rearrange a limited number of items. This model lies between the fully online case, with no buffer, and the fully offline case, where all items can be stored.

We show that reasonably sized buffers provide strong fairness guarantees for personalized k-value instances, where each agent assigns at most k distinct values to the items. In particular, using a buffer whose size is linear in k and the number of agents, we construct allocations that are EF1 at every time step and EF at most time steps. Our approach uses new combinatorial arguments and a sequence of envy-free matchings that allocate most of the items.

We also extend our results to general additive valuations, with guarantees depending on the largest ratio between two same-sign values assigned by an agent. Finally, we establish impossibility results showing the limitations of smaller buffers.

Short bio:
Nicos Protopapas is a researcher in theoretical computer science, specializing in algorithmic game theory, mechanism design, and fair division. He has held postdoctoral research positions at the Archimedes Unit in the Athena Research Center, the University of Southampton, and the University of Patras, and has taught at the University of the Aegean and the National Technical University of Athens. He received his PhD in Computer Science from the University of Liverpool.

Abstract:
In this talk, we revisit the Capacitated Vertex Cover problem under the perspective of parameterized complexity. We answer several open questions from the literature regarding both its natural and structural parameterizations considering well-studied width measures such as treewidth and clique-width. Furthermore, we present an improved algorithm for the parameterization by vertex cover number, while also showing that any further improvements would imply corresponding progress for a broader class of integer-programming-type problems.

Short bio:
Manolis Vasilakis recently received his PhD in computer science from Universite Paris Dauphine - PSL, where he was supervised by Michael Lampis. He will soon join the University of Southern Denmark as a postdoctoral researcher working with Lars Rohwedder. His research lies at the intersection of parameterized complexity, approximation algorithms, and fine-grained complexity.

Abstract:
The concept of fair orientations in graphs was introduced by Christodoulou, Fiat, Koutsoupias, and Sgouritsa in 2023, naturally modeling fair division scenarios in which resources are only contested by neighbors. In this model, vertices represent agents and undirected edges represent goods; edges have to be oriented towards one of their endpoints, i.e., allocated to one of their adjacent agents. Although EFX orientations (envy-free up to any good) have been extensively studied in this setting, EF orientations (envy-free) remain unexplored. In this work, we initiate their study, mostly under the lens of parameterized complexity, presenting various tractable cases, hardness results, and parameterizations. Our results concern both simple graphs and multigraphs. Interestingly, many of our results transfer to EFX orientations, thus complementing and improving upon previous work; notably, we answer an open question regarding the structural parameterized complexity of the latter problem on graphs of polynomially-bounded valuations. We also show that EF orientations are tractable in cases in which EFX orientations are not, particularly for binary valuations. Lastly, we consider charity in the orientation setting, establishing algorithms for finding the minimum amount of edges that have to be removed from a graph in order for EF(X) orientations to exist.

Short bio:
Sotiris Kanellopoulos is a final-year PhD student at the National Technical University of Athens, advised by prof. Aris Pagourtzis. His research is supported by a PhD fellowship from the Archimedes Research Unit. Sotiris' research interests include Computational Complexity, Algorithmic Game Theory, Algorithmic Graph Theory, Approximation Algorithms, and Scheduling. During his PhD Sotiris has worked on Periodic Scheduling problems, Fair Division, approximation schemes for variants of Subset Sum, Temporal Path and Cover problems, as well as Descriptive and Counting Complexity.

Abstract:
A classic result of Alon, Yuster, and Zwick (AYZ, Algorithmica 1997) shows that all $2k$-cycles in an $m$-edge (directed or undirected) graph can be listed in $O(m^{2-1/k} + t)$ time, where $t$ is the output size. This bound is a starting point for the notion of submodular width due to Marx (JACM, 2013), and then the PANDA framework by Abo Khamis, Ngo, and Suciu (PODS, 2017), which generalize the AYZ result to arbitrary conjunctive queries and input degree constraints. A central open question is whether combinatorial algorithms can beat the submodular-width barrier.
Bringmann and Gorbachev (STOC 2025) gave lower-bound evidence that submodular width may be optimal for general conjunctive queries under combinatorial algorithms. The picture changes, however, for $2k$-cycles on undirected graphs, whose corresponding queries have self-joins and symmetric input EDBs: recent works have improved on AYZ for even-cycle detection and listing. Pinning down the complexity of $C_{2k}$ -detection and listing is thus a natural step toward overcoming the submodular-width barrier for queries with self-joins or symmetric EDBs. With respect to the detection problem (a Boolean conjunctive query), Dahlgaard, Knudsen, and Stockel (STOC 2017) showed that $C_{2k}$ -detection can be solved in $O(m^{2k/(k+1)})$ time, improving on the AYZ bound.
The even-cycle listing problem (a full conjunctive query) is more challenging. Recent works have made progress on small cycles. Jin and Xu (STOC 2023) (and independently Abboud, Khoury, Leibowitz, and Safier, FSTTCS 2023) showed that 4-cycles can be listed in $O(m^{4/3} + t)$ time, and Vassilevska Williams and Westover (ITCS 2025) showed that 6-cycles can be listed in $O(m^{8/5} + t)$ time; both results improve the corresponding AYZ bounds of $O(m^{3/2})$ and $O(m^{5/3})$, respectively. The general case, however, has remained open since the original AYZ paper some 30 years ago.
In this paper, building on the works of Dahlgaard, Knudsen, and Stockel, and of Vassilevska Williams and Westover, we prove that 2k-cycles can be listed in $O(m^{(2k^2-k+1)/(k^2+1)} + t)$ time, improving the AYZ bound for every $k \geq 3$. The key technical ingredient is an asymmetric supersaturation result for even cycles.
Additionally, our algorithms are expressed entirely in terms of join and project operators over multiple tree-decomposition query plans, making them naturally amenable to efficient implementation in database systems. This is in contrast to the breadth-first search (BFS)-based approaches in the prior graph algorithms literature.

Short bio:
Andreas Panayi holds a BSc in Mathematics from the National and Kapodistrian University of Athens (NKUA) and an MSc jointly from NKUA and the National Technical University of Athens (NTUA). He has previously conducted research at the Archimedes Unit of the Athena Research Center, as well as industry research with RINNOCO and the Cyprus Research and Innovation Foundation (RIF). His research interests lie in theoretical computer science, specifically algorithm design (parameterized and fine-grained), data structures (dynamic and geometric), computational complexity, and extremal graph theory.

Abstract:
We study binary classification in Leslie Valiant's Probably Approximately Correct (PAC) model of learning (Valiant, 1984) with the additional requirements of establishing high recall and high precision. We do so when the training examples have been corrupted by random classification noise as in the model by Angluin and Laird (1987). Under the assumption that a hypothesis space $\mathcal{H}$ is at least as expressive as the concept class $\mathcal{C}$ (that is, $\mathcal{C} \subseteq \mathcal{H}$) we show that with a polynomial increase in the sample complexity of learning one can apply the empirical risk minimization (ERM) principle and learn a hypothesis that satisfies the PAC criterion with high recall and high precision. In order to establish this result we develop a subdivision algorithm for isolating the noise rate in a sufficiently small (user-defined) interval as well as a replicable noise-isolation procedure, both of which may have independent interest. This is work in progress jointly with Keng-Hung Steven Lin and Ting-Hung Yu.

Short bio:
Dr Dimitrios Diochnos is an Associate Professor in the School of Computer Science at the University of Oklahoma. The research of Dr Diochnos focuses on theoretical and practical aspects of trustworthy supervised and semi-supervised learning. Dr Diochnos earned his PhD in Mathematical Computer Science from the University of Illinois at Chicago, his Master's in Mathematics from the University of Athens (Greece) and his B.S. in Informatics and Telecommunications from the University of Athens (Greece).
- Departmental webpage: https://www.ou.edu/coe/cs/people/faculty/dimitrios-diochnos
- Professional webpage: https://www.diochnos.com

Abstract:
This is a chapter of a forthcoming book marking the 35th anniversary of the International Symposium on Artificial Intelligence and Mathematics (ISAIM). We survey fundamental results for binary classification under label noise. Binary classification under label noise involves training models on datasets where class labels are partially incorrect, leading to degraded performance and misclassification. We distinguish poisoning attacks from noise processes and formalize random classification noise, Massart noise, and malicious classification noise within the probably approximately correct (PAC) framework. These models capture different adversarial strengths and data-generation realities. We then highlight some core ideas and representative results. In particular, we explain why random classification noise preserves the expected ordering of hypotheses and thus supports learning using the empirical risk minimization (ERM) principle, how sample complexity depends on the noise rate, and why learning algorithms often require an upper bound on the corruption level, as well as how such a bound may be estimated from data in the case of random classification noise. We also discuss computational aspects of ERM under noise and present a canonical negative result technique---the method of induced distributions---within the malicious noise model where the adversary has more power and may affect not only the label of an example but also the instance. We conclude with pointers to related work and a taxonomy that organizes classical label-noise models using the NCAR/NAR/NNAR lens.

Short bio:
Dr Dimitrios Diochnos is an Associate Professor in the School of Computer Science at the University of Oklahoma. The research of Dr Diochnos focuses on theoretical and practical aspects of trustworthy supervised and semi-supervised learning. Dr Diochnos earned his PhD in Mathematical Computer Science from the University of Illinois at Chicago, his Master's in Mathematics from the University of Athens (Greece) and his B.S. in Informatics and Telecommunications from the University of Athens (Greece).
- Departmental webpage: https://www.ou.edu/coe/cs/people/faculty/dimitrios-diochnos
- Professional webpage: https://www.diochnos.com

Abstract:
The best known deterministic Byzantine Broadcast protocol tolerating any $t<n$ corruptions remains Dolev-Strong. Its multi-signature implementation communicates $O(n^2\kappa+n^3)$ bits for $\kappa$-bit values, where the cubic term is carried by signer bitmaps.
We isolate the certificate primitive suggested by this bottleneck: a digest that a third party can extend using only the digest and one new signature, and that subsequently certifies from the digest alone how many distinct committee members have signed so far.
We prove that, under perfect correctness over the full support of setup, keys, and signing, computational soundness forces such a digest to have length at least
$\log_2\binom{n}{n/2}-o(1)=n-O(\log n)$ bits.
The proof gives a uniform replay-and-test adversary: public updateability turns an instance-dependent collision into an efficiently produced over-counting certificate, overcoming the fresh-instance obstacle in the closest prior information-theoretic bound of Hartung et al. (PKC~2016).
The result assumes neither deterministic signing nor public verifiability; statistical correctness over signature randomness remains open.
We also prove an $\Omega(n)$ bound for constant-factor approximate counting under statistical reachability soundness, while leaving its computational analogue open.
For the standard optimized Dolev-Strong forwarding pattern, an ideal short digest would reduce communication to $O(n^2\kappa)$, whereas the lower bound shows the cubic term is unavoidable under certificate substitution: every Dolev-Strong-skeleton protocol whose certificate scheme satisfies our hypotheses incurs $\Omega(n^3)$ bits in the worst case --- unlike the general relay-update corollary, this statement needs no separate delivery-profile assumption.
More generally, we obtain a conditional cubic bound for relay-update protocols that deliver $\Omega(n^2)$ high-threshold certificates.

Short bio:
Giorgos Tsimos is a research scientist at Pod Network, working on consensus protocols, cryptography, and blockchain systems. He holds a Ph.D. in Electrical Engineering from the University of Maryland (partially completed while a research visitor at Yale), where he was co-advised by Charalampos Papamanthou and Jonathan Katz. His dissertation focused on Byzantine consensus protocols and their efficiency under strong adversarial conditions. His research spans communication-efficient broadcast, lower bounds for authenticated consensus, and the design and formal analysis of high-throughput distributed protocols.

Abstract:
We study learning-augmented algorithms for scheduling on multiple parallel machines under the objectives of minimizing the makespan or the total weighted completion time. We assume that the algorithm has access to noisy information (the prediction) about an optimal solution, expressed through a solution encoding that implicitly quantifies both the amount of information provided and the nature of noise (errors in the prediction). Our central question is to determine the maximum level of noise that still allows for efficiently recovering this optimal solution. We observe that information guiding greedy scheduling to optimality or revealing the optimal assignment of tasks to machines is very sensitive to noise, and prove that recovering an optimal solution from solution encodings capturing such information is computationally hard, even for a small (non-constant) number of errors. On the positive side, we show that an order-based encoding, which leads to errors that are dispersed locally, is robust to noise. We present a dynamic programming framework that utilizes this encoding and solves optimally several classical scheduling problems, including makespan and total weighted completion time minimization on identical or unrelated machines.

Short bio:
Giorgos Mitropoulos is a PhD student in the Operations Research team at LIP6, Sorbonne University. Supervised by Evripidis Bampis and Dimitris Fotakis, his research explores combinatorial optimization and learning-augmented algorithms, and currently focuses more on scheduling problems. He previously graduated from the School of Applied Mathematical and Physical Sciences at NTUA and was a research intern at the Archimedes Research Unit, working with Aris Pagourtzis on approximation schemes for selecting closest sum subsets.

Abstract:
While Computational Complexity Theory studies the difficulty of solving computational problems by organising them in different classes, the Metamathematics of Computational Complexity, studies the difficulty of proving results about these complexity classes. Previous barrier results have demonstrated the difficulty of separating these classes, but they tend to be ad-hoc and lack a robust framework for proofs. To address this, recent work has studied provability through mathematical logic, allowing for a deeper look at Complexity Theory by considering not just computational resources, but the feasibility of proving their existence and correctness. The main goal is to find a logical theory that formalizes most known results in Algorithms and Complexity, and to determine whether major open problems in the field are provable within this framework. In this talk, we will introduce Bounded Arithmetic, the primary framework used in this area, and present some recent results working towards this goal.

Short bio:
Dimitrios Tsintsilidas is a third-year PhD student at the Computer Science Department of the University of Warwick, advised by Igor Carboni Oliveira and Christian Ikenmeyer. His academic interests focus on Computational Complexity Theory and its connection with Logic and Algebra. Before his doctoral studies, he completed his undergraduate degree in Electrical and Computer Engineering and his Master's in Pure Mathematics at the Aristotle University of Thessaloniki.

Abstract:
We study the complexity of computing stationary Markov coarse correlated equilibria (CCE) in discounted single-controller stochastic (Markov) games [PR81, FV97], a fundamental subclass of stochastic games in which all players may affect rewards, but only one player controls the state transitions. Prior work [DGZ23, JMS23, HN25] established PPAD-hardness for computing stationary Markov CCE in two-player general-sum stochastic games via turn-based constructions in which each state is controlled by a single player, with control alternating across states. This structure forces every Markov CCE to collapse to a Nash equilibrium (NE), so hardness for NE transfers immediately to CCE. It remained open whether hardness persists when a single player controls all transitions-a setting where no such collapse occurs. We resolve this question: computing an approximate stationary Markov CCE in two-player single-controller stochastic games is PPAD-complete, even with a fixed discount factor and binary actions. For the perfect notion (equilibrium constraints at every state) this holds unconditionally at constant accuracy; for the non-perfect notion, we prove constant-accuracy hardness under the PCP-for-PPAD hypothesis [BPR16, DFHM26] and inverse-polynomial-accuracy hardness unconditionally. To the best of our knowledge, our result is the first to show hardness for computing CCE without relying on equilibrium collapse phenomena or other routes through Nash-like structure [FGK23, AKSZ24, PR24]. Instead, we construct single-controller gadgets whose local incentive constraints force a solution of a Pure-Circuit instance even under strongly correlated stationary policies.

Short bio:
Andreas is a PhD candidate jointly-enrolled at the School of Electrical and Computer Engineering (ECE) of the National Technical University of Athens (NTUA) and Archimedes AI, where he is very fortunate to be co-advised by Prof. Ioannis Panageas (UC Irvine) and Prof. Aris Pagourtzis (NTUA). Prior to pursuing his PhD, Andreas obtained an M.Sc. in Data Science and Machine Learning, as well as a joint B.Sc.-M.Eng. degree in ECE with a major in Computer Science, all from NTUA. During his master's studies, he worked as an Applied Scientist intern (Level 4) at Amazon in Barcelona.

In general, Andreas is interested in the intersection of game theory, online learning, and reinforcement learning. Current research interests include: computing/learning equilibria in structured games (e.g., games with large action spaces, Markov games), the computational complexity of hard problems in game theory and optimization, online learning and bandits (e.g., bandits with combinatorial structure), and multi-agent reinforcement learning.

Abstract:
We study budget feasible procurement auctions, in which n agents, each with a privately held service cost, offer their services to an employer. The employer seeks to maximize a public submodular valuation function over the set of hired agents, while facing a hard budget constraint. We consider an online posted-price setting, in which agents arrive in a uniformly random order (a.k.a. secretary arrivals) and the employer must make irrevocable take-it-or-leave-it offers upon their arrival. The employer does not get any feedback about the agent service costs other than whether they accept the offer or not.
We introduce Repeated Descent (a.k.a. RED), a deterministic framework based on adaptive linear posted pricing. RED enforces budget feasibility by adaptively adjusting its pricing and balancing each pricing level with the number of agents considered in it.
Using RED as the main building block, we obtain a 1046-competitive posted-price mechanism for online budget feasible auctions with secretary agent arrivals and submodular valuations. Combining RED with random subsampling, we obtain the first constant-competitive posted-price budget feasible mechanism for non-monotone submodular valuations.
On the negative side, we show that every online budget feasible mechanism with XOS valuations has a competitive ratio of $\Omega(\tfrac{\log n}{(\log\log n)^2})$.

Short bio:
Thanos Tolias is a PhD candidate at the National Technical University of Athens and a member of the Archimedes Research Unit, Athena RC, under the supervision of Prof. Dimitris Fotakis. He received his integrated Master's degree in Applied Mathematics from the National Technical University of Athens in 2023. His research lies in the area of Theoretical Computer Science, focusing on online algorithms and algorithmic mechanism design.

Abstract:
In the online unweighted knapsack problem, items arrive sequentially and must be accepted or rejected immediately for a bounded-capacity knapsack, aiming to maximize the total size of accepted items. When decisions are irrevocable, no algorithm achieves a constant competitive ratio. An essential relaxation that circumvents this impossibility is to allow previously accepted items to be removed from the knapsack (a.k.a. removal). In this work, we investigate possible further improvements on the competitive ratio with removal by bringing together two other previously proposed model extensions: knowledge of an upper bound on the item sizes (a.k.a. bound awareness) and ability to reinsert previously rejected items (a.k.a. recourse). Our contributions are twofold. First, we establish close upper and lower bounds on the competitive ratio under bound awareness, removal and recourse. We show that significant improvements on the best known competitive ratio are possible when the upper bound on the item sizes is not too restrictive and only few uses of recourse are available. Second, we introduce the notion of adaptive online algorithms which don’t require to know any upper bound on the item sizes but still achieve performance guarantees comparable to the ones obtained under the bound awareness model. Finally, we exploit the architecture of the adaptive algorithm to create a learning-augmented-via-predictions variant.

Short bio:
Panagiotis is a PSL Junior Research Chair (postdoctoral researcher-teacher position), working at LAMSADE, Paris Dauphine-PSL University. Before that, he was a postdoctoral researcher at the Athens University of Economics and Business, hosted by Vangelis Markakis. In 2023, he received his PhD from the National Technical University of Athens, School of Electrical and Computer Engineering, as a member of the Computation and Reasoning Laboratory under the supervision of Professor Dimitris Fotakis. In 2016, he received his Diploma (MEng) in Computer Engineering from the University of Patras, School of Engineering, Computer Engineering and Informatics Department. His interests lie in the areas of algorithm analysis and design, randomized algorithms, algorithmic game theory, mechanism design, learning-augmented mechanism design, approximation and online algorithms, and computational complexity.

Abstract:
Temporal networks describe systems in which the availability of an interaction depends on time, yet standard models often treat interactions as instantaneous. This abstraction can be inadequate in settings such as public transportation, where both departure times and traversal durations determine which journeys are feasible and how long they take. We study the problem of comparing such duration-aware temporal networks. Our approach represents temporal differences through source-specific distance profiles and compares them using optimal transport. Using fastest temporal paths, we examine the behavior of the resulting dissimilarity on real public-transport timetables under controlled delays and several duration-aware randomizations. The experiments show that the measure responds to both the extent and magnitude of schedule perturbations. In particular, altering departure times disrupts network performance far more than simply reassigning travel durations. Furthermore, comparisons across different days demonstrate that temporal performance can change substantially even when the overall network structure remains stable.

Short bio:
Anna Mpanti is a Postdoctoral Researcher at LUISS University in Rome, where she is also involved in teaching courses in Artificial Intelligence and Machine Learning. She received her PhD from the Department of Computer Science and Engineering at the University of Ioannina, Greece, with a research focus on graph algorithms and structural graph theory. Her research interests include algorithmic graph theory, graph modification problems, network analysis, and graph-based methods with applications in areas such as software security.

Abstract:
The Minimum Temporal Path Cover (TPC) and Minimum Temporally Disjoint Path Cover (TDPC) problems were shown to be NP-hard even on temporal DAGs, while all previously known tractable cases satisfy a temporal Dilworth property equating the minimum path-cover size with the maximum antichain size. We show that, under this property, both problems are polynomial-time solvable by proving that their optimum value is exactly the Lovasz number of the associated connectivity graph.
On the negative side, we prove that TPC is W[1]-hard when parameterized by the deletion distance to a linear forest, even on temporal graphs with only two time-steps, ruling out an FPT algorithm parameterized by treewidth and the number of time-steps.
In contrast, we obtain an FPT algorithm when treewidth is replaced by vertex cover number.
Finally, we show that including the number of time-steps in the parameterization is necessary, since both TPC and TDPC remain NP-hard for constant vertex cover number, and we establish further para-NP-hardness results for several structural parameters.

Abstract:
In this work we consider search and evacuation problems defined on the unit disk. Autonomous mobile robots are initially placed at the centre of the unit disk and aim either to locate or to evacuate through an exit positioned at the boundary of the disk, while moving at constant unit speed. We consider two communication models: face-to-face and wireless, as well as fault-tolerant variants involving crash-faulty or byzantine-faulty robots. We develop a generalised lower bound technique and establish lower bounds for the problems Evacuation(2)-F2F, Evacuation(3,1) in the presence of a crash-faulty robot and Search(4,2) in the presence of two byzantine-faulty robots. Finally, we provide the first non-trivial algorithm for the problem Search(4,2) in the presence of two byzantine-faulty robots under the wireless communication model.

Abstract:
In various domination and coverage problems, certain vertices or edges should not be dominated/covered and are designated as vulnerable. Motivated by this, we define the k-Vertex Maximum Domination Ratio with Vulnerable Vertices (k-M ax DRVV) problem, which extends the budgeted dominating set problem to include vulnerability constraints. We propose an approximation algorithm based on an unbudgeted variant of k-M ax DRVV , termed the Maximum Domination Ratio with Vulnerable Vertices (DRVV) problem. For bounded-degree graphs of order n, our algorithm provides an O(k/n)-approximation for the k-M ax DRVV problem. We also introduce the Vertex Cover with Vulnerable Edges (VCVE) problem, which can be naturally expressed as a special case of the Red-Blue Set Cover problem. We develop a 2-approximation algorithm for the VCVE problem

Short bio:
I graduated with honours from the Hellenic Military Academy in 2002. I completed postgraduate studies in the Department of Informatics at the National and Kapodistrian University of Athens (NKUA) from 2010 to 2012. I am currently a PhD candidate, with research focusing on approximation algorithms, domination, and covering problems.