Time-inconsistent behavior, such as procrastination or abandonment of long-term goals, arises when agents evaluate immediate outcomes disproportionately higher than future ones. This leads to globally suboptimal behavior, where plans are frequently revised or abandoned entirely. In the influential model of Kleinberg and Oren (2014) such behavior is modeled by a present-biased agent navigating a task graph toward a goal, making locally optimal decisions at each step based on discounted future costs. As a result, the agent may repeatedly deviate from initially intended plans. Recent work by Belova et al. (2024) introduced a two-agent extension of this model, where a fully-aware principal attempts to guide the present-biased agent through a specific set of critical tasks without causing abandonment. This captures a rich class of principal–agent dynamics in behavioral settings. In this paper, we provide a comprehensive algorithmic characterization of this problem. We analyze its computational complexity through the framework of parameterized algorithms, focusing on graph parameters that naturally emerge in this setting, such as treewidth, vertex cover, and feedback vertex set. Our main result is a fixed-parameter tractable algorithm when parameterized by the treewidth of the task graph and the number of distinct (v,t)-path costs. Our algorithm encaptures several input settings, such as bounded edge costs and restricted task graph structure. We demonstrate that our main result yields efficient algorithms for a number of such configurations. We complement this with tight hardness results, that highlight the extreme difficulty of the problem even on simplest graphs with bounded number of nodes and constant parameter values, and motivate our choice of parameters. We delineate tractable and intractable regions of the problem landscape, which include answers to open questions of Belova et al. (2024).

We study the problem of fairly and efficiently allocating indivisible goods among agents with additive valuations. We focus on envy-freeness up to any good (EFX) — an important fairness notion in fair division of indivisible goods. A central open question in this field is whether EFX allocations always exist for any number of agents. While recent results have established EFX existence for settings with at most three distinct valuations and for two types of goods, the general case remains unresolved. In this paper, we extend the existent knowledge by proving that EFX allocations satisfying Pareto optimality (PO) always exist and can be computed in quasiliniear time when there are two types of goods, given that the valuations are positive. Our findings demonstrate a fairly simple and efficient algorithm constructing an EFX+PO allocation.

We study a Stackelberg variant of the classical Most Vital Links problem, modeled as a one-round adversarial game between an attacker and a defender. The attacker strategically removes up to k edges from a flow network to maximally disrupt flow between a source s and a sink t, after which the defender optimally reroutes the remaining flow. To capture this attacker–defender interaction, we introduce a new mathematical model of discounted cuts, in which the cost of a cut is evaluated by excluding its k most expensive edges. This model generalizes the Most Vital Links problem and uncovers novel algorithmic and complexity-theoretic properties. We develop a unified algorithmic framework for analyzing various forms of discounted cut problems, including minimizing or maximizing the cost of a cut under discount mechanisms that exclude either the k most expensive or the k cheapest edges. While most variants are NP-complete on general graphs, our main result establishes polynomial-time solvability for all discounted cut problems in our framework when the input is restricted to bounded-genus graphs, a relevant class that includes many real-world networks such as transportation and infrastructure networks. With this work, we aim to open collaborative bridges between artificial intelligence, algorithmic game theory, and operations research.

We study the weighted case of the Maximum Acyclic Subgraph (MAS) problem, where each edge of a given directed graph has a positive weight assigned, and the task is to find a maximum-weight acyclic edge set. The famous and well-studied random ordering lower bound guarantees the existence of an acyclic set that gives at least the half of the total edge weight. The maximum spanning tree (MaxST) guarantee, which is the weight of a maximum-weight acyclic subgraph of the underlying undirected graph of G, is another natural lower bound for the weight of an acyclic subgraph. A solution of this weight dominates the random ordering solution on instances where MaxST spans the most of the total edge weight. Our main contribution are two parameterized algorithms that find acyclic subgraphs of total weight larger than the weight of the MaxST of G. Both our algorithms find a solution of total weight at least MaxST(G)+k, for a given integer k ≥ 0, or report that it does not exist, and - First of our algorithms runs in time 2^{k^𝒪(1)}⋅|ℐ|^𝒪(1) and works when all weights are integers; - Our second algorithm handles rational weights not less than 1, and its running time is upper-bounded by n^{k^𝒪(1)}⋅|ℐ|^𝒪(1). This positive result is rather surprising since solving MAS above the random ordering lower bound is NP-hard in the same rational weights scenario, when k = 1. Our findings unravel intricate connections between structure of MaxSTs and directed cycles, use perfect graph theorem to tackle rational weights, and raise graph-theoretic questions that are interesting on their own. Of another importance, this is one of the few examples of positive "above guarantee" results for a weighted problem on directed graphs, especially for rational weights.

The classic theorem of Gallai and Milgram (1960) generalizes several fundamental results in Graph Theory, such as Dilworth’s theorem on posets and Kőnig’s theorem on matchings in bipartite graphs. The theorem asserts that for every graph G, the vertex set of G can be partitioned into at most α(G) vertex-disjoint paths, where α(G) is the maximum size of an independent set in G. The proof of the Gallai-Milgram theorem is constructive and yields a polynomial-time algorithm that computes a covering of G by at most α(G) vertex-disjoint paths. While the Gallai-Milgram theorem is tight—there are graphs where one really needs α(G) paths, not fewer, to cover the vertex set of G—it was not known prior to our work whether deciding if a graph G could be covered by fewer than α(G) vertex-disjoint paths can be done in polynomial time. We resolve this question by proving the following algorithmic extension of the Gallai–Milgram theorem for undirected graphs: There is an algorithm that, for an n-vertex graph G and an integer parameter k ≥ 1, runs in time 22O(k4logk) · nO(1) and outputs a path cover P of G together with either a correct conclusion that P is a minimum-size path cover or an independent set of size |P| + k, certifying that P contains at most α(G) − k paths. Thus, for k ∈ O((loglogn)1/4−ε) our algorithm runs in polynomial time, and either computes a minimum-size path cover of G, or finds a path cover of size at most α(G) − k. We find the existence of such an algorithm quite surprising for the following reason. The problems of computing a path cover and a maximum independent set are both notoriously hard, yet our algorithm either solves one of them or provides meaningful information about the other. The proof of our algorithmic extension of the Gallai–Milgram theorem is non-trivial and builds on several novel algorithmic ideas. One of the key subroutines in our algorithm is an FPT algorithm, parameterized by α(G), for deciding whether G contains a Hamiltonian path. This result is of independent interest—prior to our work, no polynomial-time algorithm for deciding Hamiltonicity was known, even for graphs with independence number at most three. Moreover, the algorithmic techniques we develop apply to a wide array of problems in undirected graphs, including Hamiltonian Cycle, Path Cover, Largest Linkage, and Topological Minor Containment. We show that all these problems are FPT when parameterized by the independence number of the graph. Notably, the independence-number parameterization departs from the typical direction of research in parameterized complexity. First, α(G) measures a graph’s density, whereas most prior work in the area focuses on parameters describing sparsity, such as treewidth or vertex cover. Second, most structural parameters studied in parameterized complexity can be computed exactly or well-approximated in polynomial or even FPT time, whereas computing α(G) is notoriously difficult from almost any computational perspective. The fact that it can nevertheless serve as the basis for efficient parameterization is particularly striking.

According to the classic Chvátal’s Lemma from 1977, a graph \( G \) of minimum degree \(\delta(G)\) contains every tree on \(\delta(G)+1\) vertices. Our main result is the following algorithmic “extension” of Chvátal’s Lemma: For any \( n \) -vertex graph \( G \) , an integer \( k \) , and a tree \( T \) on at most \(\delta(G)+k\) vertices, deciding whether \( G \) contains a subgraph isomorphic to \( T \) can be done in time \(f(k)\cdot n^{\mathcal{O}(1)}\) for some function \( f \) of \( k \) only. The proof is based on an intricate interplay between extremal graph theory and parameterized algorithms.

Covering and partitioning the edges of a graph into cliques are classical problems at the intersection of combinatorial optimization and graph theory, having been studied through a range of algorithmic and complexity-theoretic lenses. Despite the well-known fixed-parameter tractability of these problems when parameterized by the total number of cliques, such a parameterization often fails to be meaningful for sparse graphs. In many real-world instances, on the other hand, the minimum number of cliques in an edge cover or partition can be very close to the size of a maximum independent set α(G). Motivated by this observation, we investigate above αparameterizations of the edge clique cover and partition problems. Concretely, we introduce and study Edge Clique Cover Above Independent Set (ECC/α) and Edge Clique Partition Above Independent Set (ECP/α), where the goal is to cover or partition all edges of a graph using at most α(G) + k cliques, and k is the parameter. Our main results reveal a distinct complexity landscape for the two variants. We show that ECP/αis fixed-parameter tractable, whereas ECC/αis NP-complete for all k \geq 2, yet can be solved in polynomial time for k \in {0,1}. These findings highlight intriguing differences between the two problems when viewed through the lens of parameterization above a natural lower bound. Finally, we demonstrate that ECC/αbecomes fixed-parameter tractable when parameterized by k + ω(G), where ω(G) is the size of a maximum clique of the graph G. This result is particularly relevant for sparse graphs, in which ωis typically small. For H-minor free graphs, we design a subexponential algorithm of running time f(H)^{\sqrt{k}}n^{O(1)}.

According to the classic Chvátal's Lemma from 1977, a graph of minimum degree δ(G) contains every tree on δ(G) + 1 vertices. Our main result is the following algorithmic “extension” of Chvátal's Lemma: For any n-vertex graph G, integer k, and a tree T on at most δ(G) + k vertices, deciding whether G contains a subgraph isomorphic to T, can be done in time f (k) · nO(1) for some function f of k only.

Abstract We initiate the study of theDiverse Pair of (Maximum/ Perfect) Matchingsproblems which given a graphGand an integerk, ask whetherGhas two (maximum/perfect) matchings whose symmetric difference is at leastk.Diverse Pair of Matchings(asking for two not necessarily maximum or perfect matchings) is $$\textsf{NP}$$ NP -complete on general graphs ifkis part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show thatDiverse Pair of Maximum Matchingsis $$\textsf{FPT}$$ FPT parameterized byk. We round off the work by showing thatDiverse Pair of Matchingshas a kernel on $${\mathcal {O}}(k^2)$$ O(k2) vertices.

Abstract Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit “natural” guarantees bringing to algorithmic questions whether a better solution (above the guarantee) could be obtained efficiently. For example, for every boolean CNF formula on m clauses, there is an assignment that satisfies at least m/2 clauses. How difficult is it to decide whether there is an assignment satisfying more than $$m/2 +k$$ m / 2 + k clauses? Or, if an n-vertex graph has a perfect matching, then its vertex cover is at least n/2. Is there a vertex cover of size at least $$n/2 +k$$ n / 2 + k for some $$k\ge 1$$ k ≥ 1 and how difficult is it to find such a vertex cover? The above guarantee paradigm has led to several exciting discoveries in the areas of parameterized algorithms and kernelization. We argue that this paradigm could bring forth fresh perspectives on well-studied problems in approximation algorithms. Our example is the longest cycle problem. One of the oldest results in extremal combinatorics is the celebrated Dirac’s theorem from 1952. Dirac’s theorem provides the following guarantee on the length of the longest cycle: for every 2-connected n-vertex graph G with minimum degree $$\delta (G)\le n/2$$ δ ( G ) ≤ n / 2 , the length of a longest cycle L is at least $$2\delta (G)$$ 2 δ ( G ) . Thus the “essential” part in finding the longest cycle is in approximating the “offset” $$k = L - 2 \delta (G)$$ k = L - 2 δ ( G ) . The main result of this paper is the above-guarantee approximation theorem for k. Informally, the theorem says that approximating the offset k is not harder than approximating the total length L of a cycle. In other words, for any (reasonably well-behaved) function f, a polynomial time algorithm constructing a cycle of length f(L) in an undirected graph with a cycle of length L, yields a polynomial time algorithm constructing a cycle of length $$2\delta (G)+\Omega (f(k))$$ 2 δ ( G ) + Ω ( f ( k ) ) .

Abstract. In 1959, Erdős and Gallai proved that every graph [Formula: see text] with average vertex degree [Formula: see text] contains a cycle of length at least [Formula: see text]. We provide an algorithm that for [Formula: see text], in time [Formula: see text] decides whether a 2-connected [Formula: see text]-vertex graph [Formula: see text] contains a cycle of length at least [Formula: see text]. This resolves an open problem explicitly mentioned in several papers. The main ingredients of our algorithm are new graph-theoretical results interesting on their own.

We present a study of a few graph-based problems motivated by fair allocation of resources in a social network. The central role in the paper is played by the following problem: What is the largest number of items we can allocate to the agents in the given social network so that each agent hides at most one item and overall at most k items are hidden, and no one envies its neighbors? We show that the problem admits an XP algorithm and is W[1]-hard parameterized by k . Moreover, within the running time, we can identify agents that should hide its items and can construct an ordering in which agents should pick items into its bundles to get a desired allocation. Besides this problem, we also consider the existence and verification versions of this problem. In the existence problem, we are given a social network, valuations, a budget, and the goal is to find an allocation without envy. In the verification problem, we are additionally given an allocation, and the goal is to determine if the allocation satisfies the required property.

Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit "natural" guarantees bringing to algorithmic questions whether a better solution (above the guarantee) could be obtained efficiently. For example, for every boolean CNF formula on m clauses, there is an assignment that satisfies at least m/2 clauses. How difficult is it to decide whether there is an assignment satisfying more than m/2 + k clauses? Or, if an n-vertex graph has a perfect matching, then its vertex cover is at least n/2. Is there a vertex cover of size at least n/2 + k for some k ≥ 1 and how difficult is it to find such a vertex cover? The above guarantee paradigm has led to several exciting discoveries in the areas of parameterized algorithms and kernelization. We argue that this paradigm could bring forth fresh perspectives on well-studied problems in approximation algorithms. Our example is the longest cycle problem. One of the oldest results in extremal combinatorics is the celebrated Dirac’s theorem from 1952. Dirac’s theorem provides the following guarantee on the length of the longest cycle: for every 2-connected n-vertex graph G with minimum degree δ(G) ≤ n/2, the length of the longest cycle L is at least 2δ(G). Thus the "essential" part of finding the longest cycle is in approximating the "offset" k = L - 2δ(G). The main result of this paper is the above-guarantee approximation theorem for k. Informally, the theorem says that approximating the offset k is not harder than approximating the total length L of a cycle. In other words, for any (reasonably well-behaved) function f, a polynomial time algorithm constructing a cycle of length f(L) in an undirected graph with a cycle of length L, yields a polynomial time algorithm constructing a cycle of length 2δ(G)+Ω(f(k)).

In this paper we consider the Target Set Selection problem. The problem naturally arises in many fields like economy, sociology, medicine. In the Target Set Selection problem one is given a graph G with a function $${{\,\mathrm{thr}\,}}: V(G) \rightarrow {\mathbb {N}} \cup \{0\}$$ and two integers $$k, \ell $$ . The goal of the problem is to activate at most k vertices initially so that at the end of the activation process there are at least $$\ell $$ activated vertices. The activation process occurs in the following way: (i) once activated, a vertex stays activated forever; (ii) a vertex v becomes activated if at least $${{\,\mathrm{thr}\,}}(v)$$ of its neighbours are activated. The problem and its different special cases were extensively studied from the approximation and parameterized points of view. For example, parameterizations by the following parameters were studied: treewidth, feedback vertex set, diameter, size of target set, vertex cover, cluster editing number and others. Despite the extensive study of the problem it is still unknown whether the problem can be solved in $${\mathcal {O}}^*\left( (2-\epsilon )^n\right) $$ time for some $$\epsilon >0$$ . We partially answer this question by presenting several faster-than-trivial algorithms that work in cases of constant thresholds, constant dual thresholds or when the threshold value of each vertex is bounded by one-third of its degree. Also, we show that the problem parameterized by $$\ell $$ is W[1]-hard even when all thresholds are constant.

We study two “above guarantee” versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, the task is to decide whether a graph has an (s,t)-path of length at least distG(s,t)+k. Bezáková et al. [7] proved that on undirected graphs the problem is fixed-parameter tractable (FPT). Our first main result establishes a connection between Longest Detour on directed graphs and 3- Disjoint Paths on directed graphs. Using these new insights, we design a 2O(k)⋅nO(1) time algorithm for the problem on directed planar graphs. Furthermore, the new approach yields a significantly faster FPT algorithm on undirected graphs. In the second variant of Longest Path, namely Longest Path above Diameter, the task is to decide whether the graph has a path of length at least diam(G)+k. We obtain dichotomy results about Longest Path above Diameter on undirected and directed graphs.

A k-core of a graph G is the maximal induced subgraph in which every vertex has degree at least k. In the Edge k-Core optimization problem, we are given a graph G and integers k, b and p. The task is to ensure that the k-core of G has at least p vertices, by adding at most b edges. While Edge k-Core is known to be computationally hard in general, we show that there are efficient algorithms when the k-core has to be constructed from a sparse graph with some structural properties. Our results are as follows. When the input graph is a forest, Edge k-Core is solvable in polynomial time. Edge k-Core is fixed-parameter tractable (FPT) when parameterized by the minimum size of a vertex cover in the input graph. Edge k-Core is FPT when parameterized by the treewidth of the graph plus k.

In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G)\geq 2 contains a cycle of length at least ad(G). We provide an algorithm that for k\geq 0 in time 2^{O(k)} n^{O(1)} decides whether a 2-connected n-vertex graph G contains a cycle of length at least ad(G)+k. This resolves an open problem explicitly mentioned in several papers. The main ingredients of our algorithm are new graph-theoretical results interesting on their own.

There is a well-known approach to cope with NP-hard problems in practice: reduce the given problem to SAT or MAXSAT and run a SAT or a MaxSAT solver. This method is very efficient since SAT/MaxSAT solvers are extremely well-studied, as well as the complexity of these problems. At AAAI 2011, Li et al. proposed an alternative to this approach and suggested the Partial Minimum Satisfiability problem as a reduction target for NP-hard problems. They developed the MinSatz solver and showed that reducing to Partial Minimum Satisfiability and using MinSatz is in some cases more efficient than reductions to SAT or MaxSAT. Since then many results connected to the Partial Minimum Satisfiability problem were published. However, to the best of our knowledge, the worst-case complexity of Partial Minimum Satisfiability has not been studied up until now. Our goal is to fix the issue and show a O*((2-ɛ)^m) lower bound under the SETH assumption (here m is the total number of clauses), as well as several other lower bounds and parameterized exact algorithms with better-than-trivial running time.

In 1952, Dirac proved the following theorem about long cycles in graphs with large minimum vertex degrees: Every n-vertex 2-connected graph G with minimum vertex degree δ ≥ 2 contains a cycle with at least min{2δ, n} vertices. In particular, if δ ≥ n/2, then G is Hamiltonian. The proof of Dirac's theorem is constructive, and it yields an algorithm computing the corresponding cycle in polynomial time. The combinatorial bound of Dirac's theorem is tight in the following sense. There are 2-connected graphs that do not contain cycles of length more than 2δ + 1. Also, there are non-Hamiltonian graphs with all vertices but one of degree at least n/2. This prompts naturally to the following algorithmic questions. For k ≥ 1, (A) How difficult is to decide whether a 2-connected graph contains a cycle of length at least min{2δ + k, n}? (B) How difficult is to decide whether a graph G is Hamiltonian, when at least n–k vertices of G are of degrees at least n/2–k? The first question was asked by Fomin, Golovach, Lokshtanov, Panolan, Saurabh, and Zehavi. The second question is due to Jansen, Kozma, and Nederlof. Even for a very special case of k = 1, the existence of a polynomial-time algorithm deciding whether G contains a cycle of length at least min{2δ + 1, n} was open. We resolve both questions by proving the following algorithmic generalization of Dirac's theorem: If all but k vertices of a 2-connected graph G are of degree at least δ, then deciding whether G has a cycle of length at least min{2δ + k, n} can be done in time . The proof of the algorithmic generalization of Dirac's theorem builds on new graph-theoretical results that are interesting on their own.

We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, the task is to decide whether a graph has an (s,t)-path of length at least dist_G(s,t)+k (where dist_G(s,t) denotes the length of a shortest path from s to t). Bez\'akov\'a et al. proved that on undirected graphs the problem is fixed-parameter tractable (FPT) by providing an algorithm of running time 2^{O (k)} n. Further, they left the parameterized complexity of the problem on directed graphs open. Our first main result establishes a connection between Longest Detour on directed graphs and 3-Disjoint Paths on directed graphs. Using these new insights, we design a 2^{O(k)} n^{O(1)} time algorithm for the problem on directed planar graphs. Further, the new approach yields a significantly faster FPT algorithm on undirected graphs. In the second variant of Longest Path, namely Longest Path Above Diameter, the task is to decide whether the graph has a path of length at least diam(G)+k (diam(G) denotes the length of a longest shortest path in a graph G). We obtain dichotomy results about Longest Path Above Diameter on undirected and directed graphs. For (un)directed graphs, Longest Path Above Diameter is NP-complete even for k=1. However, if the input undirected graph is 2-connected, then the problem is FPT. On the other hand, for 2-connected directed graphs, we show that Longest Path Above Diameter is solvable in polynomial time for each k\in{1,\dots, 4} and is NP-complete for every k\geq 5. The parameterized complexity of Longest Path Above Diameter on general directed graphs remains an interesting open problem.

We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k. Diverse Pair of Matchings (asking for two not necessarily maximum or perfect matchings) is NP-complete on general graphs if k is part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show that Diverse Pair of Maximum Matchings is FPT parameterized by k. We round off the work by showing that Diverse Pair of Matchings has a kernel on 𝒪(k²) vertices.

A popular model to measure network stability is the k-core, that is the maximal induced subgraph in which every vertex has degree at least k. For example, k-cores are commonly used to model the unraveling phenomena in social networks. In this model, users having less than k connections within the network leave it, so the remaining users form exactly the k-core. In this paper we study the question of whether it is possible to make the network more robust by spending only a limited amount of resources on new connections. A mathematical model for the k-core construction problem is the following Edge k-Core optimization problem. We are given a graph G and integers k, b and p. The task is to ensure that the k-core of G has at least p vertices by adding at most b edges. The previous studies on Edge k-Core demonstrate that the problem is computationally challenging. In particular, it is NP-hard when k = 3, W[1]-hard when parameterized by k+b+p (Chitnis and Talmon, 2018), and APX-hard (Zhou et al, 2019). Nevertheless, we show that there are efficient algorithms with provable guarantee when the k-core has to be constructed from a sparse graph with some additional structural properties. Our results are - When the input graph is a forest, Edge k-Core is solvable in polynomial time; - Edge k-Core is fixed-parameter tractable (FPT) when parameterized by the minimum size of a vertex cover in the input graph. On the other hand, with such parameterization, the problem does not admit a polynomial kernel subject to a widely-believed assumption from complexity theory; - Edge k-Core is FPT parameterized by the treewidth of the graph plus k. This improves upon a result of Chitnis and Talmon by not requiring b to be small. Each of our algorithms is built upon a new graph-theoretical result interesting in its own.