22
$\begingroup$

everybody knows there exist many decision problems which are NP-hard on general graphs, but I'm interested in problems that are even NP-hard when the underlying graph is a path. So, can you help me to collect such problems?

I've already found a related question about NP-hard problems on trees.

$\endgroup$
2
  • 21
    $\begingroup$ If you see that question you should also carefully read the accepted answer: "Take any NP-hard problem related to supersequences, superstrings, substrings, etc. Then re-interpret a string as a labelled path graph. " $\endgroup$
    – Saeed
    Feb 4 '14 at 10:25
  • 2
    $\begingroup$ Just a note: if the paths are not labeled, they are obviously highly compressible and the compact representation is a reasonable choice ($\log n$ bits to represent a path of $n$ nodes) ... so you can also "convert" hard problems that don't use unary encoding; e.g. subset sum: given $n$ unlabeled paths of length $a_1,...,a_n$, does there exist a subset of them that can be joined to form a path of length $b$? $\endgroup$ Feb 5 '14 at 11:30
25
$\begingroup$

A rainbow matching in an edge-colored graph is a matching whose edges have distinct colors. The problem is: given an edge-colored graph $G$ and an integer $k$, does $G$ have a rainbow matching with at least $k$ edges? This is known as rainbow matching problem, and its NP-complete even for properly edge-colored paths. The authors even note that prior to this result, no unweighted graph problem is known to be NP-hard for simple paths to the best of their knowledge.

See Le, Van Bang, and Florian Pfender. "Complexity results for rainbow matchings." Theoretical Computer Science (2013), or the arXiv version.

$\endgroup$
8
$\begingroup$

Here are some simple observations.

  • An uncolored path graph basically encodes an integer, so you can take any NP-hard problem involving unary-encoded integers and reinterpret it as a path graph problem. If you allow multiple integers encoded in unary (= a disjoint union of path graphs), then you can use some strongly NP-complete problems like 3-Partition.

  • A colored path graph encodes a word on a fixed alphabet, so again you can take a NP-hard problem on words. An example that I'm aware of is the Disjoint Factors problem introduced in Bodlaender, Thomassé and Yeo.

$\endgroup$
2
  • 3
    $\begingroup$ That's basically @Saeed's comment.. $\endgroup$
    – R B
    Feb 4 '14 at 15:16
  • $\begingroup$ Right, then feel free to downvote my reply. As for NP-hard problems on trees, I can mention the well-known Bandwidth problem; it was actually shown to be hard for the W-hierarchy in a research report by Bodlaender, which I couldn't find online. $\endgroup$
    – Super0
    Feb 4 '14 at 15:27
6
$\begingroup$

MinCC Graph Motif is NP-hard when the graph is a path (even APX-hard). Given a graph with colors on the vertices and a set of colors, find a subgraph matching the set of colors and minimizing the number of connected comp. See Complexity issues in vertex-colored graph pattern matching, JDA 2011.

$\endgroup$
5
$\begingroup$

Given a path with $n$ nodes and weighted edges $1 \leq \text{weight}(u,v) < n$, find if the nodes can be labeled using numbers in $[1..n]$ (avoiding duplicate labels) in such a way that the absolute difference of the labels of two adjacent nodes is equal to the weight of the edge:

$$| \text{lab}(u) - \text{lab}(v)| = \text{weight}(u,v)$$

This is equivalent to the Permutation Reconstruction from Differences problem which is NPC (one of my "unofficial" results :-).

$\endgroup$
3
$\begingroup$

A trivial answer which is close to some of what appears above but, I think, distinct.

Fix any polynomial-time computable coding $f\colon\mathbb{N}^3\to\mathbb{N}$ of triples $\langle k,m,w\rangle$ as natural numbers. The set of values $f(k,m,w)$ such that the $m$th nondeterministic Turing machine accepts its $w$th input in at most $n^{\log k}$ steps (where $n$ is the length of that input) is NP-complete. ($\log k$ so that we're effectively coding $k$ in unary.) That set of values can be represented as a set of paths.

$\endgroup$
3
$\begingroup$

The Unsplittable Flow Problem (UFP) remains NP-hard on a path. Indeed, UFP is NP-hard even on a single edge, as it is equivalent to the Knapsack problem.

$\endgroup$
3
$\begingroup$

The Rainbow Dominating Set (RDS) remains NP-hard on paths. Given a vertex-colored graph, a RDS is a DS where each color of the graph appears at least once.

Tropical dominating sets in vertex-coloured graphs, JDA'18

$\endgroup$
2
$\begingroup$

Dominating Set and Independent Dominating Set are NP-hard on paths if there is also in the input a "conflict graph", where an edge in this graph is a pair of vertices which cannot be both in the solution.

Cornet, Alexis; Laforest, Christian, Domination problems with no conflicts, Discrete Appl. Math. 244, 78-88 (2018). ZBL1387.05181.

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .