arXiv preprint ·
Colored Interaction-Profile Realization: Complexity of Matching-Match on Spiders
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Network motifs and colored local interaction patterns provide a useful way to describe the structure of complex networks. Motivated by an inverse realization perspective, we study the problem of assigning colors to the vertices of a fixed graph so that its edges realize a prescribed multiset of colored pairwise interactions. This problem is formalized by the Matching-Match Puzzle, introduced by Iburi and Uehara. We investigate how its computational complexity depends on the number of colors and on the structure of the host graph. We first prove that Matching-Match is NP-complete with only two colors, even when no vertex is precolored and the graph has maximum degree three. We then focus on spiders. We show that the problem is W[1]-hard parameterized by the number of colors even on spiders with only the body precolored. In contrast, for spiders whose legs have length at most two, we give a fixed-parameter tractable algorithm parameterized by the number of colors, allowing arbitrary precoloring. Finally, we prove NP-completeness for spiders whose legs all have length exactly three when precoloring is allowed.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Prefix Sharing Is a Sorting Problem
A $(p+q)^{O(pq)}$-approximation for $(p, q)$-Flexible Graph Connectivity
Beyond Kruskal: Polynomial-Time Tensor Decomposition under the Lovitz-Petrov Condition
Sharp Norms from Finite Structure: Graph Matrices and Structured Chaoses
Tight Hardness for Temporal Path Covers at Vertex-Cover Number Two
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.