Como usar uma chave primária incrementada automaticamente como uma chave estrangeira também?

Parece que você tem as tabelas de referência e referenciadas ao contrário. Você pode querer fazer:

ALTER TABLE `child ` ADD FOREIGN KEY (`parent_id`) REFERENCES `parent` (`id`);

Você também pode definir a chave estrangeira no CREATE TABLE declaração, como segue:

CREATE TABLE `parent` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `data` text,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=3 DEFAULT CHARSET=utf8;

CREATE TABLE `child` (
  `parent_id` int(11) DEFAULT NULL,
  `related_ids` int(11) DEFAULT NULL,
  KEY `parent_id` (`parent_id`),
  KEY `related_ids` (`related_ids`),
  FOREIGN KEY (`parent_id`) REFERENCES `parent`(`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Caso de teste:

INSERT INTO parent (`data`) VALUES ('test data 1');
Query OK, 1 row affected (0.01 sec)

INSERT INTO parent (`data`) VALUES ('test data 2');
Query OK, 1 row affected (0.01 sec)

INSERT INTO child (`parent_id`, `related_ids`) VALUES (1, 100);
Query OK, 1 row affected (0.01 sec)

INSERT INTO child (`parent_id`, `related_ids`) VALUES (2, 100);
Query OK, 1 row affected (0.01 sec)

INSERT INTO child (`parent_id`, `related_ids`) VALUES (3, 100);
ERROR 1452 (23000): Cannot add or update a child row: 
  a foreign key constraint fails