Towards Communication-Efficient Peer-to-Peer Networks (2024)
Conference Proceeding
Hourani, K., Moses Jr., W. K., & Pandurangan, G. (in press). Towards Communication-Efficient Peer-to-Peer Networks. . https://doi.org/10.4230/LIPIcs.ESA.2024.9

We focus on designing Peer-to-Peer (P2P) networks that enable efficient communication. Over the last two decades, there has been substantial algorithmic research on distributed protocols for building P2P networks with various desirable properties suc... Read More about Towards Communication-Efficient Peer-to-Peer Networks.

List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs (2023)
Conference Proceeding
Baklan Sen, B., Diner, Ö. Y., & Erlebach, T. (2023). List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs. In Proceedings of the 29th International Computing and Combinatorics Conference (COCOON 2023) (168-181). https://doi.org/10.1007/978-3-031-49190-0_12

Given a graph G = (V, E) and a list of available colors L(v) for each vertex v ∈ V, where L(v) ⊆ {1, 2, . . . , k}, LIST k-COLORING refers to the problem of assigning colors to the vertices of G so that each vertex receives a color from its own list... Read More about List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs.

Temporal Reachability Dominating Sets: contagion in temporal graphs (2023)
Conference Proceeding
Kutner, D. C., & Larios-Jones, L. (2023). Temporal Reachability Dominating Sets: contagion in temporal graphs. In Algorithmics of Wireless Networks: 19th International Symposium, ALGOWIN 2023, Amsterdam, The Netherlands, September 7–8, 2023, Revised Selected Papers (101-116). https://doi.org/10.1007/978-3-031-48882-5_8

SARS-CoV-2 was independently introduced to the UK at least 1300 times by June 2020. Given a population with dynamic pairwise connections, we ask if the entire population could be (indirectly) infected by a small group of k initially infected individu... Read More about Temporal Reachability Dominating Sets: contagion in temporal graphs.

Computing maximum matchings in temporal graphs (2023)
Journal Article
Mertzios, G., Molter, H., Niedermeier, R., Zamaraev, V., & Zschoche, P. (2023). Computing maximum matchings in temporal graphs. Journal of Computer and System Sciences, https://doi.org/10.1016/j.jcss.2023.04.005

Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G, a temporal graph is represented by assigning a set of integer time-labels to every edge e of G, indicating the discrete time steps... Read More about Computing maximum matchings in temporal graphs.

The Complexity of L(p, q)-Edge-Labelling (2023)
Journal Article
Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2023). The Complexity of L(p, q)-Edge-Labelling. Algorithmica, https://doi.org/10.1007/s00453-023-01120-4

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.

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs (2023)
Journal Article
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2023). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. Algorithmica, 85, 2580–2604. https://doi.org/10.1007/s00453-023-01109-z

Paths P1,…,Pk in a graph G=(V,E) are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices. The INDUCED DISJOINT PATHS problem is to decide if a graph G with k pairs of specified vertices (si,ti) contains k... Read More about Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs.

Topology and adjunction in promise constraint satisfaction (2023)
Journal Article
Krokhin, A., Opršal, J., Wrochna, M., & Živný, S. (2023). Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing, 52(1), 38-79. https://doi.org/10.1137/20m1378223

The approximate graph colouring problem, whose complexity is unresolved in most cases, concerns finding a c-colouring of a graph that is promised to be k-colourable, where c≥k. This problem naturally generalises to promise graph homomorphism problems... Read More about Topology and adjunction in promise constraint satisfaction.

Payment scheduling in the Interval Debt Model (2023)
Conference Proceeding
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.

Finding matching cuts in H-free graphs (2022)
Conference Proceeding
Lucke, F., Paulusma, D., & Ries, B. (2022). Finding matching cuts in H-free graphs. In S. W. Bae, & H. Park (Eds.), 33rd International Symposium on Algorithms and Computation (ISAAC 2022) (22:1-22:16). https://doi.org/10.4230/lipics.isaac.2022.22

The well-known NP-complete problem Matching Cut is to decide if a graph has a matching that is also an edge cut of the graph. We prove new complexity results for Matching Cut restricted to H-free graphs, that is, graphs that do not contain some fixed... Read More about Finding matching cuts in H-free graphs.

The complexity of growing a graph (2022)
Conference Proceeding
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.

Few induced disjoint paths for H-free graphs (2022)
Conference Proceeding
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.

Few induced disjoint paths for H-free graphs (2022)
Journal Article
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2023). Few induced disjoint paths for H-free graphs. Theoretical Computer Science, 939, 182-193. https://doi.org/10.1016/j.tcs.2022.10.024

Paths in a graph are mutually induced if any two distinct and 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 of specified vertices contains k mutu... Read More about Few induced disjoint paths for H-free graphs.

Interference-free walks in time: Temporally disjoint paths (2022)
Journal Article
Klobas, N., Mertzios, G., Molter, H., Niedermeier, R., & Zschoche, P. (2022). Interference-free walks in time: Temporally disjoint paths. Autonomous Agents and Multi-Agent Systems, 37, Article 1. https://doi.org/10.1007/s10458-022-09583-5

We investigate the computational complexity of finding temporally disjoint paths or walks in temporal graphs. There, the edge set changes over discrete time steps and a temporal path (resp. walk) uses edges that appear at monotonically increasing tim... Read More about Interference-free walks in time: Temporally disjoint paths.

The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation (2022)
Journal Article
Carvalho, C., Madelaine, F., Martin, B., & Zhuk, D. (2023). The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation. ACM Transactions on Computational Logic, 24(1), Article 5. https://doi.org/10.1145/3568397

Let A be an idempotent algebra on a finite domain. By mediating between results of Chen [1] and Zhuk [2], we argue that if A satisfies the polynomially generated powers property (PGP) and B is a constraint language invariant under A (that is, in Inv(... Read More about The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation.

Feedback Vertex Set and Even Cycle Transversal for H-free graphs: Finding large block graphs (2022)
Journal Article
Paesani, G., Paulusma, D., & Rzążwski, P. (2022). Feedback Vertex Set and Even Cycle Transversal for H-free graphs: Finding large block graphs. SIAM Journal on Discrete Mathematics, 36(4), 2453-2472. https://doi.org/10.1137/22m1468864

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 for every s \geq 1, both problems are pol... Read More about Feedback Vertex Set and Even Cycle Transversal for H-free graphs: Finding large block graphs.

Classifying Subset Feedback Vertex Set for H-free graphs (2022)
Conference Proceeding
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.

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs (2022)
Conference Proceeding
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. In Graph-Theoretic Concepts in Computer Science. 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022, Revised Selected Papers (398-411). https://doi.org/10.1007/978-3-031-15914-5_29

Paths P1,…,Pk in a graph G=(V,E) are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices. The INDUCED DISJOINT PATHS problem is to decide if a graph G with k pairs of specified vertices (si,ti) contains k... Read More about Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs.

An algorithmic framework for locally constrained homomorphisms (2022)
Conference Proceeding
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.

On the complexity of matching cut for graphs of bounded radius and H-free graphs (2022)
Journal Article
Lucke, F., Paulusma, D., & Ries, B. (2022). On the complexity of matching cut for graphs of bounded radius and H-free graphs. Theoretical Computer Science, 936, 33-42. https://doi.org/10.1016/j.tcs.2022.09.014

For a connected graph G = (V , E), a matching M ⊆ E is a matching cut of G if G − M is disconnected. It is known that for an integer d, the corresponding decision problem Matching Cut is polynomial-time solvable for graphs of diameter at most d if d... Read More about On the complexity of matching cut for graphs of bounded radius and H-free graphs.

Equitable scheduling on a single machine (2022)
Journal Article
Heeger, K., Hermelin, D., Mertzios, G., Molter, H., Niedermeier, R., & Shabtay, D. (2023). Equitable scheduling on a single machine. Journal of Scheduling, 26(2), 209-225. https://doi.org/10.1007/s10951-022-00754-6

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