Skip to main content

Research Repository

Advanced Search

Outputs (659)

Classifying Subset Feedback Vertex Set for H-free graphs (2022)
Presentation / Conference Contribution
Paesani, G., Paulusma, D., & Rzążewski, P. (2022). Classifying Subset Feedback Vertex Set for H-free graphs. In M. A. Bekos, & M. Kaufmann (Eds.), Graph-Theoretic Concepts in Computer Science. WG 2022 (412-424). https://doi.org/10.1007/978-3-031-15914-5_30

In the FEEDBACK VERTEX SET problem, we aim to find a small set S of vertices in a graph intersecting every cycle. The SUBSET FEEDBACK VERTEX SET problem requires S to intersect only those cycles that include a vertex of some specified set T. We also... Read More about Classifying Subset Feedback Vertex Set for H-free graphs.

Few induced disjoint paths for H-free graphs (2022)
Presentation / Conference Contribution
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Few induced disjoint paths for H-free graphs. In I. Ljubić, F. Barahona, S. S. Dey, & A. Ridha Mahjoub (Eds.), Combinatorial Optimization 7th International Symposium, ISCO 2022 (89-101). https://doi.org/10.1007/978-3-031-18530-4_7

Paths P 1 , . . . , P k in a graph G = (V, E) are mutually induced if any two distinct P i and P j have neither common vertices nor adjacent vertices. For a fixed integer k, the k-Induced Disjoint Paths problem is to decide if a graph G with k pairs... Read More about Few induced disjoint paths for H-free graphs.

An algorithmic framework for locally constrained homomorphisms (2022)
Presentation / Conference Contribution
Bulteau, L., Dabrowski, K., Köhler, N., Ordyniak, S., & Paulusma, D. (2022). An algorithmic framework for locally constrained homomorphisms. In M. A. Bekos, & M. Kaufmann (Eds.), Graph-Theoretic Concepts in Computer Science. WG 2022 (114-128). https://doi.org/10.1007/978-3-031-15914-5_9

A homomorphism ϕ from a guest graph G to a host graph H is locally bijective, injective or surjective if for every u∈V(G), the restriction of ϕ to the neighbourhood of u is bijective, injective or surjective, respectively. The corresponding decision... Read More about An algorithmic framework for locally constrained homomorphisms.

The complexity of growing a graph (2022)
Presentation / Conference Contribution
Mertzios, G., Michail, O., Skretas, G., Spirakis, P., & Theofilatos, M. (2022). The complexity of growing a graph. In ALGOSENSORS 2022: Algorithmics of Wireless Networks (123-137). https://doi.org/10.1007/978-3-031-22050-0_9

We study a new algorithmic process of graph growth. The process starts from a single initial vertex u0 and operates in discrete timesteps, called slots. In every slot t ≥ 1, the process updates the current graph instance to generate the next graph in... Read More about The complexity of growing a graph.

Payment scheduling in the Interval Debt Model (2023)
Presentation / Conference Contribution
Friedetzky, T., Kutner, D., Mertzios, G., Stewart, I., & Trehan, A. (2023). Payment scheduling in the Interval Debt Model. . https://doi.org/10.1007/978-3-031-23101-8_18

The networks-based study of financial systems has received considerable attention in recent years, but seldom explicitly incorporated the dynamic aspects of such systems. We consider this problem setting from the temporal point of view, and we introd... Read More about Payment scheduling in the Interval Debt Model.

Evaluating Gaussian Grasp Maps for Generative Grasping Models (2022)
Presentation / Conference Contribution
Prew, W., Breckon, T., Bordewich, M., & Beierholm, U. (2022). Evaluating Gaussian Grasp Maps for Generative Grasping Models.

Generalising robotic grasping to previously unseen objects is a key task in general robotic manipulation. The current method for training many antipodal generative grasping models rely on a binary ground truth grasp map generated from the centre thir... Read More about Evaluating Gaussian Grasp Maps for Generative Grasping Models.

The complexity of computing optimum labelings for temporal connectivity (2022)
Presentation / Conference Contribution
Klobas, N., Mertzios, G., Molter, H., & Spirakis, P. (2022). The complexity of computing optimum labelings for temporal connectivity. . https://doi.org/10.4230/lipics.mfcs.2022.62

A graph is temporally connected if there exists a strict temporal path, i.e., a path whose edges have strictly increasing labels, from every vertex u to every other vertex v. In this paper we study temporal design problems for undirected temporally c... Read More about The complexity of computing optimum labelings for temporal connectivity.

The Complexity of L(p,q)-Edge-Labelling (2022)
Presentation / Conference Contribution
Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2022). The Complexity of L(p,q)-Edge-Labelling. In P. Mutzel, M. . S. Rahman, & Slamin (Eds.), WALCOM: Algorithms and Computation: 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24-26, 2022, Proceedings (175-186). https://doi.org/10.1007/978-3-030-96731-4_15

The L(p, q)-Edge-Labelling problem is the edge variant of the well-known L(p, q)-Labelling problem. It is equivalent to the L(p, q)-Labelling problem itself if we restrict the input of the latter problem to line graphs. So far, the complexity of L(p,... Read More about The Complexity of L(p,q)-Edge-Labelling.

Computing Balanced Solutions for Large International Kidney Exchange Schemes (2022)
Presentation / Conference Contribution
Benedek, M., Biró, P., Kern, W., & Paulusma, D. (2022). Computing Balanced Solutions for Large International Kidney Exchange Schemes. In AAMAS '22: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (82-90)

To overcome incompatibility issues, kidney patients may swap their donors. In international kidney exchange programmes (IKEPs), countries merge their national patient–donor pools. We consider a recently introduced credit system. In each round, countr... Read More about Computing Balanced Solutions for Large International Kidney Exchange Schemes.

The complexity of temporal vertex cover in small-degree graphs (2022)
Presentation / Conference Contribution
Hamm, T., Klobas, N., Mertzios, G., & Spirakis, P. (2022). The complexity of temporal vertex cover in small-degree graphs. . https://doi.org/10.1609/aaai.v36i9.21259

Temporal graphs naturally model graphs whose underlying topology changes over time. Recently, the problems Temporal Vertex Cover (or TVC) and Sliding-Window Temporal Vertex Cover (or ∆- TVC for time-windows of a fixed-length ∆) have been established... Read More about The complexity of temporal vertex cover in small-degree graphs.

Partitioning H-free graphs of bounded diameter (2021)
Presentation / Conference Contribution
Brause, C., Golovach, P. A., Martin, B., Paulusma, D., & Smith, S. (2021). Partitioning H-free graphs of bounded diameter. In H. Ahn, & K. Sadakane (Eds.), . https://doi.org/10.4230/lipics.isaac.2021.21

A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of H-free graphs, that is, graphs that do not contain some graph H as an induced subgraph, have proven to be an ide... Read More about Partitioning H-free graphs of bounded diameter.

QCSP on reflexive tournaments (2021)
Presentation / Conference Contribution
Larose, B., Markovic, P., Martin, B., Paulusma, D., Smith, S., & Zivny, S. (2021). QCSP on reflexive tournaments. In P. Mutzel, R. Pagh, & G. Herman (Eds.), . https://doi.org/10.4230/lipics.esa.2021.58

We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well-known that reflexive tournaments can be split into a sequence of strongly connected components H1, . . . , Hn so th... Read More about QCSP on reflexive tournaments.

Infinite Balanced Allocation via Finite Capacities (2021)
Presentation / Conference Contribution
Berenbrink, P., Friedetzky, T., Hahn, C., Hintze, L., Kaaser, D., Kling, P., & Nagel, L. (2021). Infinite Balanced Allocation via Finite Capacities. . https://doi.org/10.1109/icdcs51616.2021.00096

We analyze the following infinite load balancing process, modeled as a classical balls-into-bins game: There are n bins (servers) with a limited capacity (buffer) of size c=c(n)∈N . Given a fixed arrival rate λ=λ(n)∈(0,1) , in every round λn new ball... Read More about Infinite Balanced Allocation via Finite Capacities.

Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs (2021)
Presentation / Conference Contribution
Paesani, G., Paulusma, D., & Rzążewski, P. (2021). Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs. In F. Bonchi, & S. J. Puglisi (Eds.), . https://doi.org/10.4230/lipics.mfcs.2021.82

We prove new complexity results for Feedback Vertex Set and Even Cycle Transversal on H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. In particular, we prove that both problems are polynomial-time solvabl... Read More about Feedback Vertex Set and Even Cycle Transversal for H-free graphs: finding large block graphs.

Bounding the mim-width of hereditary graph classes (2020)
Presentation / Conference Contribution
Brettell, N., Horsfield, J., Munaro, A., Paesani, G., & Paulusma, D. (2020). Bounding the mim-width of hereditary graph classes. In Y. Cao, & M. Pilipczuk (Eds.), 15th International Symposium on Parameterized and Exact Computation (187-199). https://doi.org/10.4230/lipics.ipec.2020.6

A large number of NP-hard graph problems are solvable in XP time when parameterized by some width parameter. Hence, when solving problems on special graph classes, it is helpful to know if the graph class under consideration has bounded width. In thi... Read More about Bounding the mim-width of hereditary graph classes.

The complexity of transitively orienting temporal graphs (2021)
Presentation / Conference Contribution
Mertzios, G., Molter, H., Renken, M., Spirakis, P., & Zschoche, P. (2021). The complexity of transitively orienting temporal graphs. In F. Bonchi, & S. J. Puglisi (Eds.), . https://doi.org/10.4230/lipics.mfcs.2021.75

In a temporal network with discrete time-labels on its edges, entities and information can only “flow” along sequences of edges whose time-labels are non-decreasing (resp. increasing), i.e. along temporal (resp. strict temporal) paths. Nevertheless,... Read More about The complexity of transitively orienting temporal graphs.

Equitable scheduling on a single machine (2021)
Presentation / Conference Contribution
Heeger, K., Hermelin, D., Mertzios, G., Molter, H., Niedermeier, R., & Shabtay, D. (2021). Equitable scheduling on a single machine. . https://doi.org/10.1609/aaai.v35i13.17404

We introduce a natural but seemingly yet unstudied generalization of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. Our generalization lies in simultaneously considering several instances of the problem... Read More about Equitable scheduling on a single machine.

Computing weighted subset transversals in H-free graphs (2021)
Presentation / Conference Contribution
Brettell, N., Johnson, M., & Paulusma, D. (2021). Computing weighted subset transversals in H-free graphs. In A. Lubiw, M. Salavatipour, & M. He (Eds.), Algorithms and Data Structures 17th International Symposium, WADS 2021, Virtual Event, August 9–11, 2021, Proceedings (229-242). https://doi.org/10.1007/978-3-030-83508-8_17

For the Odd Cycle Transversal problem, the task is to nd a small set S of vertices in a graph that intersects every cycle of odd length. The Subset Odd Cycle Transversal requires S to intersect only those odd cycles that include a vertex of a disting... Read More about Computing weighted subset transversals in H-free graphs.

Injective colouring for H-free graphs (2021)
Presentation / Conference Contribution
Bok, J., Jedličková, N., Martin, B., Paulusma, D., & Smith, S. (2021). Injective colouring for H-free graphs.

A function c : V (G) → {1, 2, . . . , k} is a k-colouring of a graph G if c(u) 6= c(v) whenever u and v are adjacent. If any two colour classes induce the disjoint union of vertices and edges, then c is called injective. Injective colourings are also... Read More about Injective colouring for H-free graphs.